Code Kata: SuDoKu Solver

This week I am interested in the Sudoku puzzle, I am thinking how to use program to solve the SuDoKu. I almost spent a week for it. At first I was inspired the a book called “Wicked Cool Ruby Scripts”in chapter 5, it provides a ruby source code for the SuDoKu solver. I spent two days to understand the code. The problem is the book does not describe the algorithm in details, and I don’t know how to debug the ruby code in TextMate. So it took me a longer time to finally understand the whole logic.

Actually it uses the brutal backtrack method. Try fill a number in one cell, then recursively call itself, if it works, continue, then return, try another, until it fills all the 81 cells. I made some changes based on the original code, the major changes once the solver find the solution then exit the loop, while in the original code the program will continue loop until the end, I compare my changes with the original code, the total times executed and execution time both drops about 50%.

Here is my modified code:


The logic is really simple: first reads the puzzle, construct the one dimension array.
The key is in Solver method:
From 81 cells, pick one empty cell, calculate the candidate numbers of this cell,
Pick one number, fill the cell,
Recusively call itself, continue try to fill another empty cell.
If the program could not find the candidate for the cell, or the program iterate all the cell’s candidate number, then erase the number, backtrack;
If the program fills all the 81 cells, return true

The algorithm of getCanidates(j) is easy:
Build an array of 1-9
Find each cell with the same row, erase the number in the cell from the array;
Find each cell with the same column, erase the number in the cell from the array;
Find each cell with the same sub block, erase the number in the cell from the array.
The left in the array are candidates


From this code, I understand more about the backtrack and recursive method. This code belongs to the depth-first backtrack search.

Donald Knuth’s Dancing Link algorithm is quite interesting, there are lots of articles and blog about using it solving the SuDoKu. But right now for me it is really hard to understand.

For SuDoKu, there are following thins to do in future:
1. Implement the SuDoKu solver using Dancing Link algorithm
2. Find out the algorithm of SuDoKu Generator, like how to generate a puzzle based on difficulty, and how to find out there is only one solution.
3. How to implement an algorithm that simulate human's solving logic?

Here are several link about dancing link and SoDuKu:
Dancing Link C implementation
Dancing link for Java
Donald Knuth Home page
Donald Knuth's Dancing links paper(pdf)