You get a partly filled Sudoku board. It is a 9 x 9 grid. Each cell holds a digit from '1' to '9', or '.' if it is empty.
Return True if no digit is repeated so far, and False otherwise. A digit is repeated when it shows up twice:
- in one row,
- in one column,
- or in one 3 x 3 box.
Thick lines split the grid into nine 3 x 3 boxes. They come after rows 2 and 5 and after columns 2 and 5.
Check only the digits on the board. Empty cells don't matter. You don't solve the puzzle. A board can pass this check even if it has no solution.
Rows are counted from 0 at the top, columns from 0 at the left. In the examples, each line is one row of the board.
Example 1:
Input: board = 5..4.7... 47.9..68. .1...6.34 ....7.4.. .5....... ...8..5.3 ....4.29. 62....341 .34.92... Output: True Explanation: No row, column or box holds the same digit twice.
Example 2:
Input: board = 5..4.7... 47.9..68. .1...6.34 ....7.4.. .5.....9. ...8..5.3 ....4.29. 62....341 .34.92... Output: False Explanation: This is the board of Example 1 with one more 9. The new 9 is in row 4, column 7. Column 7 already has a 9, in row 6.
Example 3:
Input: board = .......5. .2....... ......... 1....8... ....6.... ..1...... ......... ......3.. .9....... Output: False Explanation: The two 1s are in different rows, 3 and 5. They are in different columns, 0 and 2. But they are in the same box: rows 3 to 5, columns 0 to 2.
Constraints:
- The board always has 9 rows of 9 cells.
- Every cell is a digit from
'1'to'9'or'.'.
Note:
Your algorithm should look at each cell once and check it in constant time: O(81) time and O(81) extra space for the 81 cells. Scanning the row, the column and the box of every cell again would also work on a board this small, but it looks at each cell many times.
Free plan: 30 tutor messages. PRO is unlimited.
