Problem overview
The method isValidSudoku receives a 9 x 9 board: a list of 9 rows, each a list of 9 one-character strings. A cell holds '1' to '9' or '.' when it is empty. The method returns True when no digit appears twice in the same row, the same column or the same 3 x 3 box, and False otherwise.
Only the digits already on the board are checked. The task is not to solve the puzzle. A board with 12345678. as its first row and a 9 at the end of row 4 is valid, even though the empty cell at the end of row 0 can then never be filled: no digit repeats.
The classic first example, the board starting with 53..7...., is valid and returns True. Replace its top-left 5 with an 8 and column 0 holds two 8s (rows 0 and 3), and so does the top-left box, so the result is False.
Approach: remember what each row, column and box has seen
You could rescan the row, the column and the box of every cell, which works on a board this small but looks at each cell many times. A cleaner way visits each cell once and keeps a set of the digits seen so far for every row, every column and every box. That makes 27 sets. For a filled cell, if its digit is already in any of the three sets that belong to it, the digit appears twice and the board is invalid. Otherwise the digit goes into the three sets.
A set is the right tool because in on a set takes constant time on average, so each cell costs a constant amount of work. The board has a fixed size of 81 cells, so the time and the space are both bounded by that size.
The only tricky part is the box number. The nine boxes are numbered 0 to 8, left to right and then top to bottom. For the cell at row r and column c, r // 3 is the box's row (0, 1 or 2) and c // 3 its column, so the number is (r // 3) * 3 + c // 3. The cell at row 4, column 7 gives (4 // 3) * 3 + 7 // 3, which is 5, the right box of the middle band.
Step by step
- Create
rowswith the list comprehension[set() for _ in range(9)].rows[r]holds the digits seen in rowr. - Create
colsandboxesthe same way: nine empty sets each. - Loop over the rows with
rinrange(9). - Loop over the columns of that row with
cinrange(9). - Read the cell into
digit. - Skip empty cells. If
digitis'.',continuewith the next cell: empty cells never break a rule. - Compute the box number and store it in
box. - Check for a repeat. If the digit is already in
rows[r],cols[c]orboxes[box], returnFalse. - Record the digit by adding it to
rows[r]. - Add it to
cols[c]andboxes[box]too. - Return
Trueafter both loops: every filled cell was compared with the cells before it and none repeated.
The solution in Python
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
digit = board[r][c]
if digit == '.':
continue
box = (r // 3) * 3 + c // 3
if digit in rows[r] or digit in cols[c] or digit in boxes[box]:
return False
rows[r].add(digit)
cols[c].add(digit)
boxes[box].add(digit)
return True
Python details worth knowing:
- Why the comprehension.
[set()] * 9would put the same set object in all nine places. Afterl = [set()] * 3andl[0].add('1'), the list prints as[{'1'}, {'1'}, {'1'}]. With[set() for _ in range(3)]the same steps give[{'1'}, set(), set()], because the expression runs once per element and builds a separate set each time. The name_marks a loop variable you don't use. - Digits stay strings. The cells are characters such as
'5', and the sets store them as they are. Nothing needs converting to numbers, and comparingdigit == '.'is a plain string comparison. - Floor division.
//divides and rounds down, so7 // 3is 2. Here both operands are never negative, so the floor is the same as dropping the fraction. - Empty sets. A set is created with
set(), not{}, which is an empty dictionary.
Complexity
Time: O(81), a constant. The two loops visit 81 cells, and each visit does a few set lookups and insertions that take constant time on average. For an n x n board the work would grow with the number of cells.
Space: O(81), also a constant. Each of the 81 cells adds at most one digit to each of three sets, so the sets hold at most 243 entries in total.
Edge cases and common mistakes
- A wrong box formula.
r // 3 + c // 3sends the cells (0, 3) and (3, 0) to the same box, number 1, although they belong to different boxes. The correct(r // 3) * 3 + c // 3gives 1 and 3. The row part must be multiplied by 3 so that the nine boxes get nine different numbers. - Treating
'.'as a digit. Without thecontinue, the second empty cell in a row would look like a repeat: an entirely empty board would returnFalse. With it, an entirely empty board returnsTrue. - Checking only one kind of unit. A board with two 5s in the same row only, with the digits in different columns and boxes, is caught by the row set alone. The same goes for a repeat in a column only (rows 0 and 8 of column 0) and for a box only (cells (0, 0) and (2, 2)). Each of the three tests is needed, and all three of these boards return
False. - The same digit in unrelated places. Two 5s at (0, 0) and (3, 3) share no row, column or box, so the board is valid.
- Solving instead of checking. The function never tries to complete the board, and a board with no solution can still be valid.
Testing
- The board
53..7..../6..195.../.98....6./8...6...3/4..8.3..1/7...2...6/.6....28./...419..5/....8..79returnsTrue. - The same board with an 8 in place of the top-left 5 returns
False. - A board that is all
'.'except12345678.in row 0 and a9at the end of row 4 returnsTrue. - A board with a 5 at (0, 0) and another at (0, 8) returns
False. - A board with a 5 at (0, 0) and another at (8, 0) returns
False. - A board with a 5 at (0, 0) and another at (2, 2) returns
False. - A board with a 5 at (0, 0) and another at (3, 3) returns
True. - An empty board returns
True.
