Solving Sudoku by Heuristic Search
Introduction
I’ve recently become interested in solving Sudoku puzzles, realizing that I’m really bad in it. I can handle the easy ones, however, puzzles marked as medium or difficult are two complicated for me. I guess my main weak-spots are the heavy book-keeping required, and that it is almost impossible to recover from an error done during the solution process.
Sudoku, meaning “singular number” in Japanese, consists of an N X N grid, divided into BxB blocks (e.g. a 3×3 block corresponds to a 9×9 puzzle, as presented in Figure 1). Each puzzle has some cells that have already been filled in (called clues). We have to fill in the rest of the cells with numbers in the range [1.. N] such that in all rows, all columns and all blocks, every number appears exactly once. The puzzle at the right of Figure 1 is a solution to the puzzle on the left.
As a lazy scientist who hates hard work but also can’t stand unsolved puzzles, I decided to write a Sudoku solver program based on searching over all legal assignments for a given puzzle. Unfortunately, Sudoku is an NP-complete problem [1], when generalized to N × N grids, in the sense that all known solvable algorithms do so inefficiently; in spite of the fact that if a candidate solution is given, it takes only polynomial time to check its correctness. Therefore, a naive search approach is unlikely to be efficient so we need some domain knowledge (called heuristics in AI terminology [5]) to direct our problem solver.
There are many approaches for solving Sudoku puzzles, including CSP-based solutions [6], genetic algorithms [7], and modeling Sudoku as an exact cover problem while using the dancing links techniques [8]. Peter Norvig [2], the famous AI pioneer, published an elegant Python code for a Sudoku solver based on integrating CSP with search. In this study I follow Norvig approach by integrating common Sudoku strategies, popular among Sudoku fans, into the search process.
Heuristic search is one of my favorite AI techniques. Realizing the difficulty in searching over huge spaces, it is inspired from the ways humans solve the problem and how human strategies can be applied to improve our solver performance. This is especially useful for (the few) tasks for which humans are still superior to machines. In the following I will describe the HS-solver that is based on backtracking search, integrated with such human strategies. I’ll begin with the search algorithm, and then describe the heuristics. I’ll also report the results of some experiments I conducted on a popular benchmark of 95 9×9 puzzles which had already been used in Norvig study [2].
2. Backtracking
We represent a Sudoku puzzle by an NxN matrix holding all values that have already been set on the grid. At the beginning, only clue cells are set with their values, while all other cells are set to zero. In addition, we manage an auxiliary NxN matrix of BitSet objects. BitSet is a Java class that can be used to efficiently maintain a set of values, including adding, removing, and querying the membership of a specific value. Any constraint entry (i,j) represents all candidates that can be legally assigned to cell (i,j). In addition we keep for each row/column/block (a unit for short) a BitSet that maintains all values that have already been set in this unit. Finally, we also maintain a list of non-assigned cells in the puzzle.
The following Java code includes some important methods of the Sudoku class. The full Java code of the Sudoku HS-solver is available on https://github.com/davidcarmel/SudokuSolver.
Our first trial for solving the puzzle is by a naive backtracking algorithm. Backtracking is a classical depth-first search. It first examines if the puzzle already been solved. If not, it collects all non assigned cells and sort them by their cardinality (preferring cells with fewer candidates). It then traverses over the sorted list, inspecting the cell’s candidates. If a value is legal in this cell, it sets it and the method applies itself recursively on the modified puzzle. If all values fail we back up to a higher level seeking for an alternative track. As already been mentioned, while this algorithm is guaranteed to find a solution, if exists, this process is inefficient and may take forever to run. Here is the code for the backtracking algorithm.
We ran this function over the 95 puzzles, when limiting the search to 100M calls. 93 out of the 95 puzzles can be solved, with an average of 1.7M calls per puzzle, in 18.2 seconds per puzzle on my laptop. Well, this takes too much time and certainly is not satisfying.
3. Heuristics
Can we do better? hopefully — this is what we would like to explore. Our hypothesis is that having some domain knowledge on the problem space can help our solver to navigate the vast domain and save us a lot of precious time. We will apply some common Sudoku strategies [3] in order to improve our backtracking algorithm. It turns out that all strategies are closely related to CSP, focusing on reducing the number of legal candidates per cell (the constraints). The goal is that any cell will have only one legal candidate and hence the puzzle is solved. The difference is that while in CSP, constraints are given and we look for a solution that obey them, in our case our strategy is to reduce the number of constraints by eliminating inconsistent ones. The less constraints we have on legal assignments, the smaller the search domain to explore.
Strategy I: Candidate Reduction
If a value is being set to a cell, then it can’t be set to any other cells of its units. Therefore, we can safely remove any cell candidate if it is already being set in one of its units. Furthermore, when only one candidate is left for a cell, it can be safely set thus entailing additional candidate reduction.
Calling this strategy by the HS-solver, prior to running the search process, enables solving all puzzles, including P5, and P41, the two puzzles for which backtracking failed. The results reveals significant reduction in the search efforts. On average, search is reduced to 23.8K calls per puzzle (98.6% improvement with respect to naive search) while the maximum calls over all puzzles is reduced from 22.M to 377K. In particular, the problematic puzzles P5 and P41 are now being solved in a reasonable number of calls (and run-time) by invoking this strategy.
Strategy II: Uniqueness in Unit:
The 2nd strategy also applies a very simple rule: If a candidate is legal in only one of the unit cells, then it can be safely nailed to this cell. Of course, any new cell setting entails further reduction in candidate number for the other cells of its units.
We apply this strategy, together with candidate reduction, as part of the backtracking search. The average number of calls per puzzle is reduced to 100 (98% improvement) and the maximum calls over all puzzles to 1403, in 25ms per puzzle. Solving P5 and P41 is a piece of cake. It seems that we have cracked this benchmark.
Strategy III: Hidden pairs
A pair of candidates is called hidden if it occurs in exactly two unit cells, and none of its members is a candidate in the other unit cells. Then, it follows that the two unit’s cells holding this pair must be assigned with one of the pair members, therefore all other candidates for these two cells can be dropped. Note that we do not know which pair member should be set in which cell, however any candidate reduction is blessed.
Well, the average number of calls is reduced to 40.8, and the maximum number of calls over all puzzles is only 331. The number of calls continues to drop for the P5 and P4 tricky puzzles.
Strategy IV: Naked pairs:
A pair is called naked if it is lonely in a cell. If a pair is naked in two unit cells, then it can be dropped from all the other unit cells. following the same logic of hidden pairs.
Table 2 presents the results of backtracking, and after adding each of the strategies. The average number of calls is reduced to 26.2 and the maximum calls over all puzzles to 252. The problematic tricky puzzles are also solved smoothly. The average run-time per puzzle is 29 ms. The two right columns relate to difficult puzzles described in the following. We can conclude that our code is robust to handle quite complicated 9×9 puzzles.
4. Man vs Machine
What about really hard puzzles? Norvig [2], mentioned a Finnish mathematician, Arto Inkala, who proposed the (Inkala-2006 puzzle) as “the most difficult Sudoku-puzzle known so far” and the Inkala-2010 puzzle as “the most difficult puzzle I’ve ever created.” Looking at the right columns in Table 2, we can see that these two puzzles can be solved with a few calls, in a few milliseconds . Norvig also provided a benchmark of 11 “difficult” puzzles (eleven puzzles). None of them really challenges the HS-solver (10.4 calls on average, 25ms). This is not surprising, problems seem difficult to humans are not necessarily difficult to machines and vice versa. Norvig also generated artificial puzzles by shuffling existing ones, looking for a “killer puzzle” that will challenge his own solver. The puzzle shown in Figure 2 is such a killer. This is not an “official” Sudoku puzzle (you will not find it in a Newspaper) because it has multiple solutions (Norvig reported 13 different solutions). Interestingly, it only takes 19 calls, in 195ms, for the HS-solver to converge to the solution shown on the right.
5. Conclusions
It turns out that Sudoku, considered by many as a great challenge for human intellect, (and in particular, a great challenge for myself), does not provide a real challenge to naive search program plus some basic strategies. Are there puzzles out there that our HS-solver will not be able to solve in a reasonable time? It is very likely that the answer is yes; it would be great if we can find such examples. One direction is to move to larger puzzles of 16×16 or even 25×25, unfortunately, I could not find any reliable benchmark for such puzzles. If you are familiar with, please let me know. There are many more complicated Sudoku strategies in the arsenal such as X-wing, Y-wing, Sword-fish and more [3]. At present, I was unable to find any evidence that they are really needed, but hopefully they will be helpful for really difficult puzzles to be found in the future.
References
[1] Ercsey-Ravasz, Mária, and Zoltán Toroczkai. “The chaos within Sudoku.”Scientific reports 2.1 (2012): 1–8.
[2] Peter Norvig. Solving Every Sudoku Puzzle.
[3] Tip on Solving Sudoku puzzles. https://www.kristanix.com/sudokuepic/sudoku-solving-techniques.php
[4] Mathematics_of_Sudoku. https://en.wikipedia.org/wiki/Mathematics_of_Sudoku
[5] Heuristics: Intelligent Search Strategies for Computer Problem Solving. Judea Pearl
[6] Simonis, Helmut. Sudoku as a Constraint Problem. Eleventh International Conference on Principles and Practice of Constraint Programming. (2005)
[7] Mantere, Timo, and Janne Koljonen. “Solving, rating and generating Sudoku puzzles with GA.” IEEE congress on evolutionary computation. 2007.
[8] Donald Knuth. Dancing links, arXiv (2000).