Fill the empty cells of a 9 by 9 Sudoku board. Each row, column and 3 by 3 box must contain the digits 1 to 9 exactly once.
DSA Animator › DSA Revision › Backtracking › Sudoku Solver
Remember: find an empty cell, try valid digits, undo on failure. Returning true stops the search at the first solution. The video solves Sudoku Solver (LeetCode 37, Hard) with the Backtracking on a Board pattern from the Backtracking topic, and you can replay every step in the interactive Sudoku Solver animation.
Fill the empty cells of a 9 by 9 Sudoku board. Each row, column and 3 by 3 box must contain the digits 1 to 9 exactly once.
This is the standard example board, and it has exactly one solution.
Trying all digits in all empty cells means 9 to the power of about 50 boards. Backtracking stops a branch the moment a rule is broken.
Find the next empty cell. Try each digit from 1 to 9 that is not already in its row, column or box. Place it and recurse, and if that fails, erase it and try the next digit.
The first empty cell is row 0, column 2, and its valid digits are 1, 2 and 4. Place 1, then 2, 4, 8 and 9 in the next empty cells of row 0. Now row 0, column 8 has no valid digit, so erase 9 and 8, and try other values. The search keeps choosing and undoing, about 4200 placements in total. It ends with the only valid board, with 4 in row 0, column 2.
In code, loop over cells, and stop at the first empty one. For each digit that is valid there, place it and recurse. If the recursion returns true, pass it up, otherwise reset the cell. Return false when no digit works, which makes the caller backtrack.
Remember: find an empty cell, try valid digits, undo on failure. Returning true stops the search at the first solution.