Sudoku is a fun logic-based puzzle in which the objective is to fill a 9×9 grid with digits from 1-9 in such a way that no digit is repeated in the same row, column or 3×3 box.
In this post, I will show you how we can solve sudoku using a backtracking algorithm.
What is Backtracking?
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems,Donald E. Knuth (1968). The Art of Computer Programming. Addison-Wesley.
that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
A backtracking approach is a step better than a naive brute force search algorithm. In a brute force search, we would have to generate all possible variations of a sudoku board and then choose a valid solution. With backtracking, we only keep valid boards so at any given time the sudoku grid is always correct.
- Find the first empty square
- If there are no empty square that means that the board is full and since we only keep valid solutions, the sudoku is solved and we are done! Return True.
- If an empty square exists – try filling it with a number from [1-9]
- Check to see if the board is valid (the number is not repeated in the same row, column or 3×3 box)
- If we have a valid board from step 4, Goto Step 1
- If we don’t have a valid board from step 4, un-assign the number from the square and backtrack to step 3, trying with a different number
- If you have reached this step- there is no solution. Return False.
Let’s begin coding. First, we need a way to represent the sudoku board, we can do this using a 2D array, we will also need some helper functions to check if a board is valid and another function to print the solved board for us.
This is just one way of solving sudoku, for a more efficient algorithm be sure to check out this essay by Peter Norvig. It uses constraint propagation and search, to solve the worlds hardest sudoku puzzles in a tenth of a second!