TwiddleLab / Code / Recursion: Functions That Call Themselves
Sudoku Solver
What you will learn
- A constraint is a rule every answer must keep: no digit twice in a row, column or box.
- A constraint check like is_ok tests one move against the rules before it's made.
- The solver is backtracking: place a digit that passes the check, go deeper, undo when stuck.
- Picking the most constrained cell first (fewest options) cuts the tries a lot. Timetables are solved the same way.
How the lesson goes
Every newspaper sudoku can be cracked by a short program. Try a small one first.
Digits 1 to 4: once in every row, every column and every 2 x 2 box.
How many tries will the solver need on this board?
It tries 1, 2, 3, 4 in each empty cell, in reading order. Every digit it checks counts.
Watch the solver: try, check, go deeper, undo.
Red is a clash. When no digit fits, it steps back and changes an earlier one.
Each empty cell is a recursive call. It tries digits in order; a digit that passes the check is placed and the next call starts. If a later call finds no digit at all, it returns False and this call undoes its digit and tries the next one.
Constraints and the constraint check.
A constraint is a rule the answer must keep. Sudoku has three: each digit once per row, once per column, once per box.
A constraint check tests one move: is_ok(board, r, c, d) says whether digit d can go at row r, column c right now.
The solver is backtracking with a check: try a digit, keep it only if is_ok says True, undo it when the search below fails.
Be is_ok. What blocks the violet digit?
Tap every cell that blocks it, or Fits if nothing does.
Classic, part 1: write is_ok(board, r, c, d).
Check the row and column in one loop, then the 2 x 2 box. Any match means False.
Any clash is enough to reject the digit, so each check can return False at once. Only when no loop found the digit can the function return True, so that line comes last.
Classic, part 2: write solve().
Find the first empty cell, try 1 to 4 with is_ok, go deeper, undo if that fails. No empty cell left means solved.
return False sits after the digit loop, still inside the empty-cell branch: it runs only when all four digits failed. return True at the very end runs only when the loops found no empty cell, so the board is full.
Classic, part 3: your solver on the board you solved by hand.
Your is_ok and your solve. Press Run.
Challenge: a 9 x 9 newspaper sudoku. Which order needs fewer tries?
Same backtracking, two ways to pick the next cell. Tap one, then Check.
Reading order often starts on a cell where many digits fit, and the wrong guess is only discovered many levels deeper. Filling the most constrained cell first makes fewer wrong guesses, so there's less to undo.
Same idea, real problem: an exam timetable.
Six exams, three time slots. Exams that share students can't be at the same time. Undo when stuck.
Where will the solver get stuck?
One empty cell has no digit that fits. Tap it, then Check.
A cell is a dead end when each of 1, 2, 3 and 4 already appears in its row, its column or its box. The solver discovers that by four failed checks, then backtracks.
Make it harder, then let your solver crack it.
Remove given digits, then press Crack it. Your card shows how many tries it took.
Previous lesson: Backtracking: Solving a Maze · Part of the course: Recursion: Functions That Call Themselves
Lessons are interactive and need JavaScript. Turn it on to play them.
