Algorithm to Solve Sudoku
Sudoku is a logic-based number-placement puzzle. In classic sudoku, the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called “boxes”, “blocks”, or “regions”) contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution [1].
As the nature of the logic, we may fill empty cells with numbers and have many solution candidates. Trying to solve this problem with a brute force approach is feasible since it has a complexity of O(9^m) (m demonstrates empty cells).
When you think about the brute force solution, one can realize that some of the solution attempts have unnecessary branching i.e. when we place a number in a row, we don’t need to derive new solution attempts which has the same number twice at the same row since it will not be a valid solution.
So, the key point is we are looking for an algorithm trying to solve a problem with pruning unnecessary branching. At this point, backtracking can help us.
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, 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 [2].
Backtracking algorithms work like that:
- Iterate to construct solution attempts.
- Do not construct a candidate if it is not valid.
- Branch to next candidate with moving ahead
- Recursively follow step 1.
- Return if the solution is found.
- Take one step back and try moving ahead with the next.
This means that we will try to put numbers to the empty cells and continue if it is valid sudoku with existing numbers. We will recursively follow these steps until we hit an invalid solution. If so, we will take one step back and try the next number.
Assume that we have given sudoku as a 2d char array with empty cells are defined with ‘.’ (dot) character. The algorithm that solves sudoku with backtracking is as follows:
This article is a part of my solutions for the classical algorithm problems series. Check my profile to read existing articles and stay in tune with new ones.
You can follow me on Twitter: https://twitter.com/kamaci_furkan
[1] https://en.wikipedia.org/wiki/Sudoku
[2] Gurari, Eitan (1999). “CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms”. Archived from the original on 17 March 2007.
