36. Valid Sudoku
On LeetCode ->Reformulated question¶
Given a partially filled 9x9 Sudoku board, return True iff every filled cell respects Sudoku rules:
- no duplicate digit in its row
- no duplicate digit in its column
- no duplicate digit in its
3x3box
Example:
Key trick¶
Track constraints, not solving.
- For each filled cell, check whether its digit was already seen in:
- its row
- its column
- its
3x3box
- The box id is:
(r // 3) * 3 + (c // 3)
Trap¶
- Treating
"."like a real value and accidentally detecting duplicate dots. - Trying to solve the Sudoku instead of only validating current constraints.
- Computing box membership incorrectly, especially the
3x3index.
Why this question is interesting?¶
It tests clean constraint modeling.
- simple problem
- easy to overcomplicate
- good signal for sets, indexing, and careful iteration
Solution with idiomatic 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):
val = board[r][c]
if val == ".":
continue
box = (r // 3) * 3 + (c // 3)
# If already seen in any constraint bucket, board is invalid.
if val in rows[r] or val in cols[c] or val in boxes[box]:
return False
rows[r].add(val)
cols[c].add(val)
boxes[box].add(val)
return True
Pytest test¶
import pytest
@pytest.mark.parametrize(
("board", "expected"),
[
(
[
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
],
True,
),
(
[
["8", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
],
False,
),
(
[
["5", "3", "5", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
],
False,
),
(
[
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
["5", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
],
False,
),
(
[["."] * 9 for _ in range(9)],
True,
),
],
)
def test_is_valid_sudoku(board, expected):
assert Solution().isValidSudoku(board) is expected
Comment my solution¶
Your solution is correct and interview-good.
-
Good:
- clear separation of rows, columns, boxes
- correct skipping of
"." - easy to explain
-
Small improvement:
- do all checks in one pass instead of three passes
- generate box id with arithmetic instead of hardcoding box starts
-
Minor style note:
- in row checks,
if elt in seenruns beforeelt != ".", so duplicate dots would falsely fail if a row had multiple dots and dots were added, but you do not add dots, so it is safe; still, checking"."first is clearer
- in row checks,
import pytest
class Solution:
def isValidSudoku(self, board: list[list[str]]) -> bool:
# check lines
for line in board:
seen = set()
for elt in line:
if elt in seen:
return False
elif elt != ".":
seen.add(elt)
# check columns
for j in range(9):
seen = set()
for i in range(9):
elt = board[i][j]
if elt in seen:
return False
elif elt != ".":
seen.add(elt)
# check squares
for i, j in [
(0, 0),
(0, 3),
(0, 6),
(3, 0),
(3, 3),
(3, 6),
(6, 0),
(6, 3),
(6, 6),
]:
seen = set()
for i1 in range(i, i + 3):
for j1 in range(j, j + 3):
elt = board[i1][j1]
if elt in seen:
return False
elif elt != ".":
seen.add(elt)
return True
class SolutionOnePass:
def isValidSudoku(self, board: list[list[str]]) -> bool:
# Implemented after reading comments from AI
lines = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
squares = {}
for i in [0, 3, 6]:
for j in [0, 3, 6]:
squares[(i, j)] = set()
for i in range(9):
for j in range(9):
n = board[i][j]
if board[i][j] == ".":
continue
# check row
if n in lines[i]:
return False
lines[i].add(n)
# check column
if n in cols[j]:
return False
cols[j].add(n)
# check square
for key in squares.keys():
if (key[0] <= i < key[0] + 3) and (key[1] <= j < key[1] + 3):
square_key = key
break
if n in squares[square_key]:
return False
squares[square_key].add(n)
return True
@pytest.mark.parametrize(
("board", "is_valid_sudoku"),
[
(
[
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
],
True,
),
(
[
["8", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
],
False,
),
(
[
[".", ".", "4", ".", ".", ".", "6", "3", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
["5", ".", ".", ".", ".", ".", ".", "9", "."],
[".", ".", ".", "5", "6", ".", ".", ".", "."],
["4", ".", "3", ".", ".", ".", ".", ".", "1"],
[".", ".", ".", "7", ".", ".", ".", ".", "."],
[".", ".", ".", "5", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
],
False,
),
],
)
def test_isValidSudoku(board, is_valid_sudoku):
assert SolutionOnePass().isValidSudoku(board) == is_valid_sudoku
# assert Solution().isValidSudoku(board) == is_valid_sudoku
# a = [set() for _ in range(2)]
# a[0] is a[1] # False
# a = [set()] * 2
# a[0] is a[1] # True