Solving sudoku with C#

[dhilipkumar]

  Introduction
I have to thank my mother for always complaining about sudoku programs you can download from the net. This pushed me to build a sudoku program tailored on her preferences and doing this I discovered the DLX algorithm.
Bear in mind that I'm not giving here a complete explanation of the DLX algorithm, since it took Knuth 26 pages to explain that. If you want to understand the DLX just download Knuth's paper from his site. Here's a link

Topics
What is a sudoku?
What is the DLX algorithm?
How can I apply the DLX algorithm to sudoku problems?
How the C# code for all this may look like?


Part I: Let's play Sudoku!
Sudoku is a japanese game based on numbers and logic. If you want to learn more about it's origins and details in general, I suggest you to visit the sudoku page on WikiPedia.
The aim of the game is to fill in a 9x9 square grid with numbers from 1 to 9 starting from an incomplete grid.
The 9x9 square grid is also partitioned into 9 3x3 grids (boxes from now on).

You must follow these rules:
# Each row must contain all the numbers from 1 to 9 in some order.
# Each column must contain all the numers from 1 to 9 in some order.
# Each 3x3 box must contain all the numbers from 1 to 9 in some order.

# Also, the purists of this game are very picky on these rules too:
# The starting grid must present numbers with some simmetry (center simmetry)
# The solution must be unique.
It should be possible to solve the sudoku using just logic (no guessing)

In sudoku jargon the numbers that you already have when you start playing sudoku are called "givens".

Here you can see an example of an evil sudoku starting grid and its unique solution.

You can notice the symmetry of the starting grid. This sudoku was taken from the www.websudoku.com site, where you can play to 4 different difficulties sudokus. I chose an evil one for my example.

I'm not going long with an explanation about how to play sudoku here. That's not the aim of this article.
If you're not familiar with sudoku please take your time to surf the net a while and become familiar with it before reading the rest of this article. To become familiar with sudoku is a matter a 5 minutes. The rules are simple and few and you need no math skills to play it.

osix

[dhilipkumar]

Part II: Thank you Donald Knuth!
Man, if you're a programmer or simply an addicted to i.t. you must get yourself a copy of Knuth works. On my bookshelf I'm proud to expose his "The art of computer programming" entire collection and I must tell you, reading those books gives you an understanding of this subject that really goes beyond any aspectation.
So, what is this DLX algorithm? Basically is a very cool algorithm used to quickly solve the "Exact cover" problem. A problem which is well known to be NP-complete. Basically the exact cover problem is simple to understand, but not so simple to solve as the problem size grows up a little.
You have a matrix, filled with 0's and 1's and you want to know if there is a subset of it's rows that leads to have just one single 1 for each column.
A very small example:

Row 1 : 0 1 0 0
Row 2 : 1 0 0 0
Row 3 : 1 1 1 0
Row 4 : 0 0 1 1

As you can see, rows 1,2,4 summed altogether present a 1 in each column, representing a solution to this particular matrix.

The algorithm that solves the exact cover problem is described in knuth papers so I'll just quickly report it here with no explanation.

Algorithm X on Matrix A:

If A is empty the problem is solved; terminate successfully.
Otherwise choose a column, c (deterministically)
Choose a row, r, such that A[r,c]=1 (nondeterministically)
Include r in the partial solution
foreach j such that A[r,j]=1
   delete column j from matrix A;
   foreach i such that A[i,j]=1
      delete row i from matrix A
Repeat this algorithm recursively on the reduced matrix A

Let me just tell you a couple of things:
It's best to choose deterministically the column c using the minimum search. I mean, it's better to choose the column c such that the number of 1's un that column is the minimum you can find for every column. This way you'll reduce to the min the number of branches the algorithm has to do.

So what we do is: we pick a column, choose a row where there is an 1 in correspondence of the column and delete that row (after including it in the partial solution), then we delete each column that present a 1 on the row we are deleting. We also delete all other rows that have one 1 on column c.
After these deletions we have a reduced matrix on which we run this algo recursively again and again, until we have a null matrix or an impossible to solve matrix.

Algorithm X on our small example would yield:

Row 1 : 0 1 0 0
Row 2 : 1 0 0 0
Row 3 : 1 1 1 0
Row 4 : 0 0 1 1

I choose column 4 (since it has just one 1), this provokes the deletion of column 3 and row 3 leaving me with this reduced matrix (first 2 rows, first 2 columns).

Row 1 : 0 1
Row 2 : 1 0

So now I just pick the first column and I remain with just a 1x1 matrix with a 1 inside. I pick it and I have got my solution: Rows 4,2,1 or in order if you prefer, 1,2,4, since the order has no particular meanings.

So, what about a 1000x1000 matrix? or 100000x100000? Hehe, having a problem of that size leads to a non negligible computation time and size too. (Please note that it's not required for the matrix to be a square one)
What can we do? Well, we can read Knuth papers and implement the Dancin Links Algorithm (DLX).
Basically the DLX is the transposition of the exact cover problem matrix on a double linked list.
A double linked list is a two-dimensional list where each element is linked to it's neighbours and also wraps around horizontally and vertically.
To give you a small letter example:

A B C D
E F G
H I

Let's examine node F.
It has B as Up neighbour, I as Down neighbour, G as Right neighbour and E as Left neighbour.
What about B though?
Since the double linked list wraps around it has I as Up neighbour, A as Left neighbour, C as Right neighbour and F as Down neighbour.
Last we examine node I:
It has F as Up neighbour, B as Down neighbour, H as Left neighbour and H also as Right neighbour, since the list wraps also horizontally.
This should be clear enough.

So, we build a list like this with some Node objects, and we put a Node where in the matrix we find a 1. We don't put anything where we find a 0.
This would yield a sparse matrix made up by Node objects where 0's are not represented. This surely brings down the load of the problem since we have less data to keep alive.
This also let's us using the DLX to manipulate very quickly this structure in order to solve the exact cover problem.
The DLX is basically the using pointers version of the X algorithm.
Nobody can explain it better than Knuth obviously, so I suggest you to run read his paper before continuing here.

[dhilipkumar]

Part III : Making the trick
To solve sudoku using DLX we have to map the sudoku problem to an equivalent exact cover problem.
To do this, let's see what meaning the matrix columns and rows will have.
Each row represents a placement. I mean, when you decide to write e.g. 7 in cell (3,5) you have made a placement. This decision has some effects on the game since now in row 3, column 5 and box 2 (boxes are counted from 1 to 9 from top left to bottom right reading in row major order) you can't put another 7. Also, putting a 7 in (3,5) means that in (3,5) you can't put another number.
This is pretty everything you have to consider. Hence we have 4 conditions to respect:

You can't put more than one number in each cell (row,column condition)
You can't put the same number twice or more in a row (row,digit condition)
You can't put the same number twice or more in a column (column,digit condition)
You can't put the same number twice or more in a box (box,digit condition)

Our matrix columns will represent these four conditions and our matrix rows will represent each different placement you can do on the 9x9 grid.

Ok, since there are 9x9=81 cells in the grid and there are 9 different numbers you can place in each cell, the number of the possible placements you can do is 81x9 = 9^3 = 729.
For the columns let's check each condition (1 to 4):

Condition 1: Cell taken
The are 9x9 = 81 possible cells that can be taken (a cell is "taken" after you place a number in it) so first condition yields 81 (matrix)columns of (r,c) kind. R will be the major index for this condition.
So, (matrix)columns from 1 to 9 will represent putting a number in row 1, columns 1 to 9.
(Matrix)columns from 10 to 18 will represent putting a number in row 2, columns 1 to 9 and so on...
Basically if you want to place a number in row r, column c you will place a 1 in column r*9+c.

Condition 2: Row, digit condition
There are 9 rows and 9 possible different numbers you can place in each row so, 9x9 = 81 and we have again 81 (matrix)columns for condition 2. Also this time r is being the major index so placing digit d in row r will place a 1 in (matrix)column r*9+d +[81].
81 are the first condition related columns.

Condition 3: Column, digit condition
As for the rows, there are 9 columns with 9 possible different numbers you can place each one of them.
Again, 9x9 = 81 (matrix)columns and this time the column index is the major one, so placing digit d in column c will place a 1 at (matrix)column c*9+d +[81]+[81].
81+81 are the first + second condition related columns.

Condition 4: Box, digit condition
As for rows and columns, same for the boxes. 9 boxes, 9 digits, 81 more (matrix)columns. Box index is the major one, so placing a number d in box b will place a 1 in (matrix)column b*9+d +[81]+[81]+[81].
81+81+81 are the first + second + third condition related columns.

We have 81x4 = 324 condition columns at all.
Hence, a 729x324 matrix is enough to transpose a sudoku problem into an exact cover one:

This is something you must have clear in mind in order to understand what's coming now.
After struggling with this transposition I found out in WikiPedia a page that explains these concepts in a similar way I did. I don't remember the url so please search on your own (keywords: sudoku, DLX).

Let's examine a couple of rows to give you an example.
Say you want to place number 7 in cell (3,5).
So, d=7, r=3, c=5 and b=2.
Our row will have 4 1's placed in each correspondent condition column.
Placing number 7 in cell (3,5) will make this cell unavailable for other numbers hence we put a 1 in (matrix)column 3*9+5=32.
Also, we have put a 7 in row 3 so we'll have to put a 1 in (matrix)column [81] + 3*9+7=115.
Notice that [81] I summed. Those are the first 81 (r,c) conditions.
Let's check third condition:
I'll place a 1 in (matrix)column [81]+[81] + 5*9+7=214.
First 81 + 81 (matrix)columns are cell taken conditions and row-digit conditions.
Last 1 is at column [81]+[81]+[81] + 2*9+7=268.
Obviously first 81 is cell taken conditions, then row-digit conditions, then column-digit conditions.

Another quick example:
Say you want to place number 1 in cell (5,2).
So, d=1, r=5, c=2 and b=4.
Our row will have four 1's again and they will be:
(Matrix)Column 5*9+2 for cell taken condition.
(Matrix)Column [81] + 5*9+1 for row-digit condition.
(Matrix)Column [81]+[81] + 2*9+1 for column-digit condition
(Matrix)Column [81]+[81]+[81] + 4*9+1 for box-digit condition.

So we have placed four 1's and we'll place four 1's for each row (in different columns), not less, not more, in fact there will be a 1 for each condition that that placement has to satisfy.
Now, having 729*4=2916 1's instead of 729*(320 zeros + 4 ones)=236196 is a little better isn't it? Indeed.

Please notice that (matrix)column I wrote. That's not a cast! I used this notation to distinguish between an exact cover matrix column and a sudoku grid column. Anyway, once you understand the whole trick you shouldn't have problems recognizing what I am talking about.

Solving a sudoku is then simply a matter of making a translation.
You pick a sudoku exact cover matrix placing all 729 rows with some ordering. For example you can place every digit for cell (1,1), then every digit for cell (1,2) and so on until you're at cell (9,9).
You then have to select some rows using the givens. Selecting some rows (with the X algo I mean) means you cover those rows and relative columns as you were choosing that row at run-time with algo X. This will simulate the choice of the givens. When you have all the givens selected you run the real algorithm on the matrix you have left.
For example, placing number 2 in cell (1,1) as you see in my example image, yields the selection of the row # 2.
Selecting this row will make impossible to select other rows where for example cell (1,1) is taken. Or where there is a 2 in first row or column or box.

Shortly resuming:
1-Build a sudoku matrix
2-Select the rows that correspond to the givens
3-Solve the matrix with DLX algorithm.

You're now ready to see how to do this with C#.

[dhilipkumar]

Part IV: Let's code!
Note: I'm not one of those guys that like to reinvent hot water. If I find some useful code somewhere I just grab it and use it (giving credits to the author obviously). Searching for a decent DLX sudoku implementation was painful. I found tons of code in java, C/C++, javascript, etc. but none of them was enough clear for me. The only one implementation in C# I found was for a palm and implemented DLX using arrays, not objects.
After a week spent on researching I chose to code my own application following Knuth's guidelines as close as possible. So, the code you're about to read it's been written by me line by line.

Ok. We have some classes here (5 classes to be precise):

Node class: this class represents a Node in the matrix. It's the representation of the Knuth's DLX Nodes.
NodePointer class: an helper class I used to quickly retrieve the first node in a row.
Header class: derived by the Node class. It's a head node, and has a Name (the column index) and the size (the number of 1's in the column it is the head of)
DLX class: the main class. This class solves an exact cover problem.
SudokuSolveDLX class: derived by DLX class, this class extends it's base class methods in order to quickly adapt a sudoku to an exact cover problem and solve it.

I'm not going to show them completely here since it would be too much to read. I'll just highlight the most important things but don't fear, I'll provide you a link where you can download the complete source code and a compiled assembly to test the application.

So, let's jump the first 3 classes. Basically they are just obect classes, with references for the neighbours and the column headers. Column headers nodes also have a name (the index of that column) and a size which represents the number of 1's in that column. As I told you before choosing the column that has the minimum number of 1's reduces the number of branches that DLX does, so we need the size field in order to achieve the minimum at each step.
To quickly find rows and columns I have wrapped my double linked list within a couple of arrays. One of Header objects to retrieve columns and one of NodePointer objects, to retrieve rows.
For example NodePointer[200] points directly to the first Node object of 200th row.
It's a bit of space required but helps with time. Ok, let's have a look to some DLX methods:

This is the BuildSkeleton method. It builds up the arrays that wrap the matrix.

public void BuildSkeleton(int r , int c) {
            columns = new Header[c];
            rows = new NodePointer[r];
            // columns
            for (int i=0; i<c; i++) {
                columns=new Header(i);
                columns.Left=h.Left;
                columns.Right=h;
                h.Left.Right=columns;
                h.Left=columns;
            }

            // rows
            for (int i=0; i<r; i++) {
                rows=new NodePointer();
            }   
        }

After this I have a couple of AppendRow methods, that simply append a row putting a Node object where it should go a 1 in the matrix.


Here there is the CoverColumn method as suggested by Knuth.

protected void CoverColumn(Header c) {
            // header unplugging
            c.Left.Right=c.Right;
            c.Right.Left=c.Left;
             
            // nodes unplugging
            Node i=c.Down;
            Node j=null;
            while (i!=c) {
                j=i.Right;
                while (j!=i) {
                    j.Up.Down=j.Down;
                    j.Down.Up=j.Up;
                    j.Head.Size--;
                    j=j.Right;
                }
                i=i.Down;
            }
        }

Covering a column means we're selecting it and we have to unplug all the nodes related to that and also related to the rows that have a 1 in the column we're covering. The unplugging takes places always in vertical direction since we need to keep at least the horizontal structure to reconstruct the whole thing.

[dhilipkumar]

Let's check the most important method of this class: SolveRecurse().
As you can see I don't like to use variables like a,b,c and I give proper names to fields so it's quite intuitive to imagine what the SolveRecurse method does. It solves the DLX problem recursively.

protected virtual void SolveRecurse() {
            if (h.Right==h) {
                totSolutions++;
                return;
            }
            Header c=FindMin();
             
            if (c.Size==0) return; // not a good solution

            CoverColumn(c);
            Node r=c.Down;
            Node j=null;
            while (r!=c) {
                sol.Push(r);
                j=r.Right;
                while (j!=r) {
                    CoverColumn(j.Head);
                    j=j.Right;
                }
                SolveRecurse();
                r=(Node)sol.Pop();
                c=r.Head;
                j=r.Left;
                while (j!=r) {
                    UncoverColumn(j.Head);
                    j=j.Left;
                }
                r=r.Down;
            }
            UncoverColumn(c);
        }

The method is declared protected virtual since I want it to be accessible in any derived class and I want to be able to override it. This let me create classes that solve any kind of problem using the DLX class structure.
I could have used Stack<Node> from System.Collections.Generic namespace in my code, but some of you are probably not familiar with these new features of C# 2.0 yet and I preferred not to go too hard with this code.
Anyway, the algorithm calls itself recursively. It covers the column it has chosen using the FindMin method and then executes the DLX algorithm using the CoverColumn and UncoverColumn methods. When it selects a row to be included in the solution, it pushes it's first Node into a Stack. From these nodes you can easily take out the solution when the algo is done with it's job.

After testing this class and seeing it worked well, I derived from this the SudokuSolveDLX class. I added some methods to this class to easily format a sudoku into an exact cover problem style and solve it. Let's see some code snippets:

This is the foremost method which you'll always call. It builds the sudoku matrix ready to be manipulated with your grid of givens:

public void BuildSudokuMatrix() {
            // skeleton first
            BuildSkeleton(dim*dim*dim , 4*dim*dim);

            //appending all the rows then
            int b=0;
            for (int r=0; r<dim; r++) {
                for (int c=0; c<dim; c++) {
                    // set the block
                    b=(r/bDim)*bDim+(c/bDim);
                    for (int d=0; d<dim; d++) {
                        AppendRow(new int[] {r*dim+c, dim*(dim+r)+d, dim*(c+2*dim)+d, dim*(b+3*dim)+d }, r*dim*dim+c*dim+d);
                    }
                }
            }
        }

[dhilipkumar]

After building the matrix you have to select the rows corresponding to the givens you have:

public void SetStartingGrid(int[,] grid) {
            try {
                for (int r=0; r<dim; r++) {
                    for (int c=0; c<dim; c++) {
                        if (grid[r , c]!=0) {
                            SelectRow(r*dim*dim+c*dim+(grid[r , c]-1));
                        }
                    }
                }
            } catch (Exception ex) {
                System.Diagnostics.Trace.WriteLine("From SetStartingGrid(int[,]):n"+ex.Message);
            }
        }

You can pass a 2D array with the givens (and 0's where you have empty cells) or you can pass a string[] array for I provided a useful overload to this method.

When you have selected the rows corresponding to the givens, you have your ready-to-be-solved exact cover problem. So you just have to call the base class Solve method.
I have provided 4 different ways to call it based on an enumeration. It's all very easy to understand so I'll let this task up to you.
All the code is commented and shouldn't be too hard to understand it.

The complete source code is HERE.
I provided also an assembly that lets you test the whole thing. Please do care about the fact that you must install version 2.0 of the .Net framework (search in the download section of Microsoft's site).


So, this is the end.
I really hope you enjoyed the trip and I hope that my code will help you build your own sudoku programs if you like to.


Osix
BY sfabriz