The problem
Check whether a partly filled 9×9 Sudoku board is valid so far: no digit may repeat in any row, any column, or any of the nine 3×3 boxes. You don’t have to solve it.
Input: the board shown in the picture Output: true
Picture it
Imagine three sets of checklists: one per row, one per column and one per 3×3 box. We visit every filled cell and tick its digit off on its row’s list, its column’s list and its box’s list. If a digit is already ticked on any of those lists, that digit is repeated, so the board is invalid.
How to recognise it
- You must check that no value repeats inside several groups at once (here rows, columns and 3×3 boxes).
- Every cell belongs to exactly one group of each kind, and you can compute which one from its row and column.
- "Has this group already seen this value?" is a set question, one set per group.
- You only check the filled cells. You do not need to solve the puzzle.
Start with brute force
Compare every filled cell with every other filled cell. If two hold the same digit and share a row, a column or a box, the board is invalid.
def is_valid_sudoku_brute(board):
cells = [(r, c) for r in range(9) for c in range(9) if board[r][c] != "."]
for r1, c1 in cells:
for r2, c2 in cells:
if (r1, c1) < (r2, c2) and board[r1][c1] == board[r2][c2]:
if r1 == r2 or c1 == c2 or (r1 // 3, c1 // 3) == (r2 // 3, c2 // 3):
return False
return True
The board is always 9 × 9, so even this is a fixed amount of work: at most 81 × 81 = 6,561 pairs, which is instant. The reason to do better is the pattern: on a general n × n board with n² cells, comparing every pair costs O(n⁴), while one set per group costs O(n²).
From brute force to the idea
- Find the waste. The brute force compares cells that cannot clash, such as two cells in different rows, columns and boxes.
- One checklist per group. Keep a set of digits already seen for each of the 9 rows, 9 columns and 9 boxes: 27 sets in all.
- Name the box. Cell (r, c) is in box
(r // 3, c // 3). Integer division by 3 maps rows 0 to 2 to box row 0, rows 3 to 5 to box row 1, and so on. - Check, then record. For each filled cell, if its digit is already in its row set, column set or box set, return
False. Otherwise add it to all three. - Skip the dots. Empty cells (
".") take part in nothing.
This is the key idea: one set per row, column and box, with the box named by (r // 3, c // 3).
The key idea
Each cell belongs to exactly one row, one column and one box (box = (row//3, col//3)). Three families of sets catch every repeat in one pass.
Python solution
def is_valid_sudoku(board):
rows, cols, boxes = defaultdict(set), defaultdict(set), defaultdict(set)
for r in range(9):
for c in range(9):
v = board[r][c]
if v == ".":
continue
b = (r // 3, c // 3)
if v in rows[r] or v in cols[c] or v in boxes[b]:
return False
rows[r].add(v); cols[c].add(v); boxes[b].add(v)
return TrueLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n⁴) on an n × n board, so at most 6,561 pairs on 9 × 9: every pair of filled cells is compared | O(n²): the list of filled cells |
| One set per group (shown code) | O(n²), so 81 cells on 9 × 9: three average O(1) set checks per cell | O(n²): 3n sets holding at most n digits each |
For the real 9 × 9 board both are constant time; the table shows how they grow.
Edge cases
- Empty board (all
"."): returnsTrue. - Valid so far but unsolvable: a board with 1 to 8 across the top row and a 9 at row 1, column 8 returns
True, even though the top-right cell can never be filled. The problem only asks about repeats. - Same digit in the same box but different row and column (5 at (0, 0) and (1, 1)): returns
False, caught only by the box set. - Digits are strings: the board holds
"5", not5. The code compares them as given, so that is fine as long as you do not mix the two. - Missing import: the code needs
from collections import defaultdict; without it the call raisesNameError.
Common mistakes
- Naming the box
r // 3 + c // 3. Different boxes share a number (box (0, 1) and box (1, 0) both give 1), so a valid board with a 5 at (0, 4) and a 5 at (4, 0) is rejected. - Checking the digit against the sets but forgetting to add it to all three, so a later repeat in that column or box is missed.
- Trying to solve the puzzle or check that it can be solved, which the problem does not ask for.
- Treating
"."as a value, so every board with two empty cells in a row looks invalid.
In a diagonal Sudoku, the two main diagonals must also have no repeated digit: the cells where r == c, and the cells where r + c == 8. Change the check so it also enforces this. Describe your approach, then write it if you like.
Compare with our answer
Add two more groups. A cell on a diagonal belongs to that diagonal's group as well as its row, column and box. Keying every group by a tuple keeps the code to one dictionary of sets.
from collections import defaultdict
def is_valid_diagonal_sudoku(board):
seen = defaultdict(set)
for r in range(9):
for c in range(9):
v = board[r][c]
if v == ".":
continue
units = [("row", r), ("col", c), ("box", r // 3, c // 3)]
if r == c:
units.append(("diag",))
if r + c == 8:
units.append(("anti",))
for u in units:
if v in seen[u]:
return False
seen[u].add(v)
return True
The centre cell (4, 4) is on both diagonals. Time and space are still O(1) for a 9 × 9 board.
A strong answer mentions: treating each diagonal as one more group, the test for each diagonal, and that the centre cell is checked against both.
1. You must check that an n × n grid is a Latin square: no value repeats in any row or any column. Which approach fits best?
Two families of groups, one set each, gives O(n²) for the whole grid. Sorting every row and column also works but costs O(n² log n). Equal sums do not rule out repeats: 1 + 3 = 2 + 2.
2. Why does the shown code catch a repeated digit in a box with only one set lookup per cell?
Integer division by 3 sends every cell of a box to the same key, so all nine cells share one set. Rows, columns and boxes are separate dictionaries, checked as each cell is read.
3. A learner names the box with b = r // 3 + c // 3. Which board is now judged wrongly?
(0, 4) is in box (0, 1) and (4, 0) is in box (1, 0); both give 0 + 1 = 1, so they share a set and the valid board is rejected. The two invalid boards are still caught, and (0, 0) and (8, 8) give the different keys 0 and 4.
Score 60% or more and the lesson is marked complete.