Monday, July 20, 2015

This post is all about sudoku, the venerable Japanese puzzle. Even though the hype lies far behind us, every once in a while I get bored and return to solving a few puzzles. But then one day I was given an exceptionally hard to beat sudoku puzzle. Even after hours of staring it down, I wasn’t getting anywhere. Hmmm… I was not going to be belittled by some stupid puzzle! And so I decided to cheat a little and crack it by writing a sudoku solver.

Sudoku is a numbers game, but there is no calculation involved whatsoever. The ‘game board’ is a set of 9×9 tiles, each containing a number from 1 to 9. The numbers in a row must be unique, however, as well as the numbers in each column, and the numbers in each 3×3 sub block.
Some numbers are given; it is up to you (the player) to fill in the gaps. Once all the numbers are filled in according to the given rules, the puzzle is solved. In general, a sudoku puzzle has one, and only one, unique solution.

First of all, let me mention that brute-forcing it is a definitive no-no. There are countless possibilities that do not lead to the solution. I figured that the total number of permutations would be around 9×9! (over 3 million), but two researchers have calculated that there are 5,472,730,538 (almost 5.5 billion) essentially different sudoku grids. The number of raw permutations is much larger however, in the range 6.67×10²¹.
Trying them all is going to take forever, even on the fastest computer available today. We need to be smarter than that—why not simply play the game and see where it gets us?

In order to let the computer play, we are going to need a couple of routines:

1. load a given sudoku puzzle
2. check whether puzzle is correct
3. find cell with only one possibility left

It’s easy enough to store the puzzle into a 9×9 array of cells. Each cell holds a number, but also has a property saying whether it’s a ‘solid’ cell, or can be filled in by the player.
Checking the correctness of the puzzle is a three-step process: check all the rows, columns, and 3×3 blocks. Finding a cell with only one possibile solution also checks all the rows, columns, and 3×3 blocks.

This is a reasonable start for a solver program, but note that it will only solve the most naive beginner-level sudoku puzzles. The problem is, there will be cells that have more than just one option, and this solver is just not good enough. For the super evil sudoku, we are going to have to do better than this.

Rather than finding a cell with only one possible solution left, let’s take a look at what possible solutions there are for a blank cell. A blank cell may have any number between 1 and 9, unless that number is already present in that row, column, or 3×3 block. Any already filled-in numbers are removed from the set of possible solutions for the cell. The remaining set holds a number of possiblities, of which one is the solution for this cell. Let’s try them all, but because we want to have the solution as quickly as possible, start with the cell that has the smallest set. So if there is a cell with only one or two possible solutions, try that one first before moving on to harder to crack cells.

As you are trying out possible solutions, the numbers lock into place and they can no longer be part of solution sets in other cells that are in the same row, column or block. Slowly, the puzzle is being solved. But we may still hit a wall and have to go back to the point where we tried a wrong possibilty; this happens because not all attempts lead to a perfect puzzle. Many configurations are invalid, and need to be discarded.

Going back is easily done by means of backtracking. Backtracking works by recursion. I find it easy to think about in terms of functional programming; in functional programming, objects are immutable, they can not be changed. If you wish to change the state of an object, then that is a new object, albeit a modified clone of the object.
So whenever trying a solution to a cell, clone the whole puzzle. Put that puzzle object onto a stack. Now recurse, and try solving the next cell. If the puzzle is invalid, backtrack: pop the stack and return. As the recursive function is returning, it will continue trying the next solution to the cell. Notice how cells that ‘work’ are followed-up on and lead to the next step in solving the puzzle, and solutions that don’t work tend to cut off excess work.

I implemented this solver in Python. Detail: cloning is done with copy.deepcopy(). My aging computer solves the evil sudoku in under half a second. On the Raspberry Pi 2 it takes 3.5 seconds. Remember that brute-forcing would take forever. You don’t need a fast computer (nor a low-level programming language) to pull this off. What’s important is choosing the right algorithm.

Backtracking is the algorithm for this kind of puzzles, where a partial list of candidates could lead to a solution. In fact, after finding a solution, the algorithm may continue to run and find all solutions. In a bold move, I handed it a completely blank 9×9 grid. It started spewing out all solutions to sudoku … each and every sudoku there is, ever was, or ever will be. And after a while, I hit Ctrl-C.