All problems

Valid Sudoku

Medium · hash set

A Sudoku board is a 9 x 9 grid split into nine 3 x 3 boxes. You are given a partly filled board as a list of 9 rows, each with 9 characters. A character is either a digit from "1" to "9" or "." for an empty cell.

A board breaks the rules if some digit appears twice in the same row, twice in the same column, or twice in the same 3 x 3 box. Empty cells are ignored.

Return true if the digits already on the board break none of these rules, and false otherwise. You are only checking what is written: the board does not have to be solvable.

Examples

Example 1

Input: board = [["1", "2", ".", ".", "5", ".", ".", "8", "9"], [".", "5", "6", ".", ".", "9", ".", ".", "3"], [".", ".", "9", "1", ".", ".", "4", ".", "."], ["2", ".", ".", "5", "6", ".", ".", "9", "."], [".", "6", ".", ".", "9", "1", ".", ".", "4"], [".", ".", "1", ".", ".", "4", "5", ".", "."], ["3", ".", ".", "6", ".", ".", "9", "1", "."], ["6", "7", ".", ".", "1", ".", ".", "4", "5"], [".", "1", "2", ".", ".", "5", ".", ".", "8"]]

Output: true

No digit repeats within any row, column or box.

Example 2

Input: board = [["1", "2", "8", ".", "5", ".", ".", "8", "9"], [".", "5", "6", ".", ".", "9", ".", ".", "3"], [".", ".", "9", "1", ".", ".", "4", ".", "."], ["2", ".", ".", "5", "6", ".", ".", "9", "."], [".", "6", ".", ".", "9", "1", ".", ".", "4"], [".", ".", "1", ".", ".", "4", "5", ".", "."], ["3", ".", ".", "6", ".", ".", "9", "1", "."], ["6", "7", ".", ".", "1", ".", ".", "4", "5"], [".", "1", "2", ".", ".", "5", ".", ".", "8"]]

Output: false

Row 0 now holds an 8 in column 2 and another 8 in column 7.

Example 3

Input: board = [["1", "2", ".", ".", "5", ".", "3", "8", "9"], [".", "5", "6", ".", ".", "9", ".", ".", "3"], [".", ".", "9", "1", ".", ".", "4", ".", "."], ["2", ".", ".", "5", "6", ".", ".", "9", "."], [".", "6", ".", ".", "9", "1", ".", ".", "4"], [".", ".", "1", ".", ".", "4", "5", ".", "."], ["3", ".", ".", "6", ".", ".", "9", "1", "."], ["6", "7", ".", ".", "1", ".", ".", "4", "5"], [".", "1", "2", ".", ".", "5", ".", ".", "8"]]

Output: false

The top-right box holds a 3 at row 0, column 6 and another 3 at row 1, column 8. They share neither a row nor a column, but they share a box.

Constraints