Valid Sudoku
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Check that a partly filled 9x9 board breaks no Sudoku rule (no repeats in any row, column or 3x3 box).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many groups must each cell belong to?
- Hint 2Which of the nine boxes a cell is in: (row // 3) * 3 + (column // 3).
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A class sits in a 9x9 grid. The rule: in every row, every column and every 3x3 block of desks no two students may have the same lucky number. The monitor keeps 27 attendance slips, one per row, per column and per block. When a student with lucky number 5 sits down, he checks his row slip, column slip and block slip. If 5 is already on any of them, the seating is invalid.
- The obvious way
Re-scan the row, column and box for every cell. Fine for 9x9 but clumsy.
- The key insight
Make nine slips (sets) for rows, nine for columns, nine for boxes. Visit each filled cell once: if its digit is already on its row slip, column slip or box slip the board is invalid; otherwise write it on all three.
- The algorithm
- Prepare nine empty row slips, nine column slips and nine box slips.
- For each cell with a digit, work out its box number.
- Is the digit already on its row, column or box slip? Answer False.
- Otherwise write the digit on all three slips. At the end answer True.
Watch it run
Exampleone row of the board: 5 3 . . 7 . . . 5
First cell 5: row slip is empty, so write 5 on the row, column and box slips.
row 0 slip: {5}Where people slip
- Only the filled cells are checked; the puzzle need not be solvable.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def is_valid_sudoku(board):
row_slips = [set() for _ in range(9)]
col_slips = [set() for _ in range(9)]
box_slips = [set() for _ in range(9)]
for row in range(9):
for col in range(9):
digit = board[row][col]
if digit == ".":
continue
box = (row // 3) * 3 + col // 3
if digit in row_slips[row] or digit in col_slips[col] or digit in box_slips[box]:
return False
row_slips[row].add(digit)
col_slips[col].add(digit)
box_slips[box].add(digit)
return TrueNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.