Tag Archives: algorithms

Solving Sudoku and the n-Queens problem

I’ve put together a solver for Sudoku , as well as one for the n-Queens problem. This was inspired and informed by some ideas and algorithms in the book Artificial Intelligence: A Modern Approach by Stuart Russel and Peter Norvig. The solvers were quite fun to write and surprisingly easy to put together, both done in an afternoon.

The approaches taken for these two problems are different, so I’ll highlight the key aspects and compare them at the end.

A typical sudoku puzzle
A typical sudoku puzzle (source: wikipedia)

The sudoku solver first uses the AC-3 algorithm to infer reductions in the domain (possible values) of variables before the search. If this reduces the domains to one value per cell, the puzzle is effectively solved. If some variable’s domain becomes the empty set (no value for a cell that can satisfy all constraints), the puzzle is unsolvable. Otherwise, a search is done to find a solution.

The search uses backtracking. It is a depth-first search (DFS), going deep down one path before checking others, with in-place modification of the puzzle board as it goes, and undoing the changes when it has gotten stuck and needs to backtrack. Order of solutions tried in the DFS matters, as some orders can prune large parts of the tree. The following heuristics are used to sort variables and values:

  • Minimum value remaining heuristic — prioritizes cells that have few legal values
  • Least constraining value heuristic — after choosing a cell, this prioritizes the value option that least inhibits other cells

Forward checking is used to maintain arc consistency for a variable after a value is chosen for it. This infers domain reductions in neighbouring variables. The the search proceeds until it finds a solution or fails (not solvable). If the puzzle is solvable, a solution is returned. Here is an example, using an “evil difficulty” puzzle found online:

import sudoku 

# Taken from https://www.websudoku.com/
evil = [
0,0,7,0,0,5,0,9,0,
6,2,0,1,0,7,0,0,8,
0,1,0,0,0,0,0,0,0,
0,0,0,0,0,3,5,0,0,
0,8,0,0,6,0,0,3,0,
0,0,5,4,0,0,0,0,0,
0,0,0,0,0,0,0,6,0,
9,0,0,6,0,1,0,2,4,
0,6,0,8,0,0,1,0,0
]

solved = sudoku.search(evil)
if solved: sudoku.print_solution(solved)

>>>
8 3 7 | 2 4 5 | 6 9 1 
6 2 4 | 1 9 7 | 3 5 8 
5 1 9 | 3 8 6 | 7 4 2 
- - - - - - - - - - - 
2 4 6 | 9 1 3 | 5 8 7 
7 8 1 | 5 6 2 | 4 3 9 
3 9 5 | 4 7 8 | 2 1 6 
- - - - - - - - - - - 
1 5 8 | 7 2 4 | 9 6 3 
9 7 3 | 6 5 1 | 8 2 4 
4 6 2 | 8 3 9 | 1 7 5 

The algorithm used for solving sudoku is systematic and exhaustive. In contrast, different algorithms are best suited for the n-Queens problem, another well known puzzle. The challenge is to place n queens on an nxn board, such that no two queens attack each other.

My n-Queens solver uses the local beam search algorithm, an adaptation of another algorithm named beam search. It starts off with some randomly generated configurations and does greedy stochastic hill climbing search on each one. If one of them finds a solution, that’s returned. Otherwise, the k best results are used for the next search. This algorithm requires parallel searches, so the solver utilizes multiprocessing. The idea behind hill climbing algorithms is to follow the steepest path up locally. As the nearest hill may not be the highest hill, it is prone to get stuck in local minimums (dead ends). Randomization is the trick used to solve this, by restarting the search in different places. The randomization also ensures that a solution is eventually found if one exists.

The solution for an 8×8 board is instantaneous, but it took a few minutes on 4 cores to find a solution for 128×128. Supposedly, this algorithm has been used to solve the millions queens problem in under 2 seconds, but it was probably a more optimized solution, and written in a language like C++.

Can the backtracking algorithm used for the sudoku solver be used for the n-Queens problem? It can, but it turns out that it requires much more computation time. It was the approach taken before hill climbing blew it out of the water. When stochastic hill climbing with restarts (a similar algorithm that does not utilize parallelization) was found to work so quickly for the n-Queens problem (in the 1990s), it resurged interest in this algorithm for a host of other problems. For example, it is used by airlines for flight scheduling due to its efficiency and its online property of being able to incorporate new data easily.

On the other hand, while it would also work for sudoku, the solution for sudoku appears to be solved with much less computation when using backtracking search. In the n-Queens problem, the solutions are densely distributed in the search space, whereas for sudoku, they are not. The answer to the question, “which algorithm should I use for this problem?” is not an easy one, and according to the no free lunch theorem, there is no one algorithm that is best for all problems.

You can check out the solvers at n-queens-solver and sudoku-solver.