Contents

1 Download and install the code

Before I even explain how I tried to solve Suodku, you can download and install the code from my bitbucket Sudoku repository.

After you have tried a few unsolved Sudoku boards, and are convinced that this application does really solve Sudokos, you may continue reading to find out the design and implemenation details.

2 Representing the board

Here I describe my attempt at solving Sudoku using Lisp. Since Lisp is my favorite programming language, it is but natural that I choose to use it to solve Sudokus. Enough lisp adulation and before I digress too much, let us find out what the solution looks like. Please note that the code is tested only on SBCL.

Since a Sudoku is a 9 * 9 grid, I decided to use 2D array to represent the sudoku board. Of course sometimes such natural choice of a data structure could be wrong, but if we follow the rule of ”write code fast, then write fast code” (by PG of course) and naturally supported by Lisp; it should not be very difficult to change the underlying data structure if we get to atleast a reasonable approach initially to solve the problem at hand.

3 The Sudoku Concepts

When I am bored and naturally procrastinating, I indulge in mindless activities like Sudoku. And I am no expert at solving it with pencil and paper. But over a period of time, we pick up some concepts/terms from the problem without even realizing them. The most important such concept in the Sudoku problem for me was that a square could not have any number that appeared in any other square of the row, column or the box to which the square belonged. We could call these other squares as ’friends’ of the square s; though the quality of not sharing seems hardly friendly!

It was then obvious that I would need to find out the squares of a given square s. Since our sudoku is a 2D array, the subscripts (i j) of the array would represent each sudoku square. So given the square in the first column, first row the subscripts of which would be (0 0) what would be the friends of the square?

In the process of finding the friends of a square; I ended up with the constant friends. It should be noted that this is a refined (after write fast code stage) code; intially all of what you see as constants were functions. Later while optimizing, it was evident that it would be prudent to compute them at compile time and do lookups via hash tables where keys are the subscripts of a square on the 2D array’ed sudoku.

This also leads to other 2 corollary concepts of filled and unfilled square. A filled square is that which has a single value assigned to it. An unfilled square is that which has no value assigned to it yet or has one among many possible values none of which are those assigned to any of its friends.

4 Filling up the input board

While solving a given partially filled Sudoku (the most natural case; I treat fully unfilled sudoku as a special case) I decided to first fill every unfilled square with the possible choices for it by not considering the values that any of its friends has. Natuarlly here I consider only those friends which have been filled. At this point, we could end up with a few unfilled squares with only one possible choice. Thus it would make sense to update the board. We update the board till no more updates are possible or a contradiction is found.

Here comes the rule/concept/constraints of the Sudoku game into play again. The rule states that every row, every column and every box must be filled with each of the digits 1 to 9 without being repeated. So if a square on a row has 1, the column and the box to which the square belongs cannot have any other square with a value 1. If there is a square with value 1; it means there is a contradiction.

Aha, now we can write some code to figure out a contradiciton on a sudoku board. This code checks that for every filled square of the sudoku board, none of its friends has the value that it has.

The code for checking contradictions is shown here.

The fact that a sudoku is solved implies there are no contradicitions on the board or the number of squares counted by contradictions should be 81. The function which checks if the board is solved is shown here.

Now you can see how we can update the board.

At this stage I choose to call the sudoku board as initialized board. The code which initializes the input board is here.

With an initailized board we are in a position to find a solution to the sudoku. But how?

We know that on the initialized board, every unfilled square has been assigned valid possible choices. So one of the choice for any such unfilled square has to be true. Otherwise, there is a bug in the code which is assigning incorrect possible values to an unfilled square.

Thus we could choose at random an unfilled square and assign it one of the possible choices. If we could find whether this assignment is true or false, we could find a solution!

5 How do we find if the attempted assignment is correct?

By now it is clear that if the attempted assignment is correct, it will lead to no contradictions and finally to a solution. Otherwise it will be false and lead to a contradiction, so we drop that from the possible values and assign the next possible value and try again to find a solution.

Now, can we make use of the discared values as well? Yes. If an assignment is valid; then the rest of the choices are invalid. But each of this choice does exist as a value in some friend. So we find if there exists only a single friend which has among its possible choices; any of the ones we just discarded. Then obviously that discarded choice is the value for that unfilled friend. Similary for a invalid assignment, we check it the value we just discarded can be assigned to any unfilled friend. The code to use discarded values is shown here.

So what unfilled square do we choose? Naturally we want to find a solution as fast as possible. Hence it makes sense to choose an unfilled square with the minimum number of choices. In the worst case, we will find a solution when the last possible choice

6 Algorithm

The heart of the algorithm can be now described: Assign the next possible choice to the unfilled square with minimum possible choices till we find a solution. After assigning a value, update the board which returns a new board if no contradictions are found.For both valid and invalid assignments, make use of discared values. All this is captured in a function called as try.

7 Using the cl-utilities

I use this package in order to copy the 2D array’ed sudoku board as I need to revert back to the old board in case of invalid assignments.

8 Writing Fast Code

After writing a first version of the sudoku solver, I used the time macros and sbcl deterministic profiler as explained here. The most important changes made were the conversion to constants of functions dealing with finding friends. That resulted in friends as a hash table with the key being the subscripts for each square of the 2D Sudoku.

9 Some Test Runs

I used the following as samples from Web Sudoku.

9.1 Easy Sudoku

The test run for an Easy Sudoku.

Thus it took 0.01 sec to solve an easy Sudoku.

9.2 Medium Sudoku

The test run for a Medium Sudoku.

Thus a medium sudoku was solved in 0.016 seconds.

9.3 Hard Sudoku

The test run for a Hard Sudoku.

Thus it took 0.046 seconds to solve a hard sudoku.

9.4 Evil Sudoku

The test run for an Evil Sudoku.

Thus it took 0.29 seconds to solve an evil sudoku.

9.5 Empty Sudoku

In addition, I also tested for an empty sudoku. It should be fast enough to solve this sudoku as there are no existing constraints to be met!

As expected, the empty sudoku got solved in 0.117 seconds.

This code seems to have a reasonable performance without any compiler optimization declarations.

The entire code can be found here. At the end of the file is code for using sbcl profiler which has been commented. If you test this on SBCL, you can use this profiler or use the profiler available on your lisp implementation.

10 Observations

This code is a great fit for using the non deterministic choose and fail operators along with continuations so that I will not have to maintain the copies of the board. I will try updating this code using PG’s macros that add continuations and non-deterministic opeators to CL. That will make the code only more elegant (and may be slower). But all this can be surely concluded only after writing that code!

Further I have not done the algorithmic analysis. Here the candiate would be the try function and as it is recursive, I would have to use recurrence relations.

Ideally the path should have been writing a solution using continuations and choose, fail operators and then move to the solution above based upon profiling results! I will update the post when I follow up on the above observations. Feel free to try to solve a sudoku with this code and kindly let me know in case of any comments/suggestions.