My Attempt to Solve Sudoku in Common Lisp

Before I even explain how I tried to solve Suodku, you can download and install the code from my 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.

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.

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.

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!

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

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.

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.

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.

Some test runs

I used the following as samples from  Web Sudoku .

Easy Sudoku

* (setf easy #2A( (7 0 2 0 0 0 0 4 0) (0 8 0 0 7 1 0 0 6) (5 0 4 9 0 0 0 0 3) (6 0 8 0 3 0 5 0 7) (0 0 1 0 0 0 3 0 0) (4 0 5 0 8 0 9 0 1) (1 0 0 0 0 9 6 0 5) (3 0 0 6 2 0 0 1 0) (0 5 0 0 0 0 4 0 2))) * (time (solve easy)) The solution is #2A((7 6 2 3 5 8 1 4 9) (9 8 3 4 7 1 2 5 6) (5 1 4 9 6 2 8 7 3) (6 9 8 1 3 4 5 2 7) (2 7 1 5 9 6 3 8 4) (4 3 5 2 8 7 9 6 1) (1 2 7 8 4 9 6 3 5) (3 4 9 6 2 5 7 1 8) (8 5 6 7 1 3 4 9 2)) Evaluation took:

0.010 seconds of real time

0.009091 seconds of total run time (0.008759 user, 0.000332 system) 90.00% CPU 21,240,869 processor cycles 278,160 bytes consed

Medium Sudoku

0.016041 seconds of total run time (0.015904 user, 0.000137 system) 100.00% CPU 35,307,818 processor cycles 609,712 bytes consed

Hard Sudoku

0.045322 seconds of total run time (0.045076 user, 0.000246 system) 97.83% CPU 99,184,111 processor cycles 1,833,440 bytes consed

Evil Sudoku

0.290481 seconds of total run time (0.271850 user, 0.018631 system)

[ Run times consist of 0.027 seconds GC time, and 0.264 seconds non-GC time. ]

99.66% CPU 629,978,518 processor cycles 11,207,760 bytes consed

Empty Sudoku

0.116159 seconds of total run time (0.113484 user, 0.002675 system) [ Run times consist of 0.007 seconds GC time, and 0.110 seconds non-GC time. ] 99.15% CPU 253,827,691 processor cycles 4,548,560 bytes consed

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.

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.