Dancing Sudoku_Hans Hurvig

[Len_Nguyen1]

Introduction
The Dancing Sudoku program solves Sudoku puzzles. It tries hard to break the solution down into steps
that can easily be comprehended by a human. At each step of the way you’ll see why this path leads to the
unique solution, which is much more satisfying that just being shown the solution.
No matter what, though, the program will always find the solution if there is one; if there are more than
one solution it will find them all, and either show you each one of them or just count how many there are.
So what’s the Dancing all about? The program is based on a technique called Dancing Links, described in
a paper by the grand master of software engineering Donald Knuth. It is very elegant and efficient, and
applies to a broad class of problems. Sudoku puzzles happen to be one of them.
*
I won’t explain the internals of the algorithm, but I’ll give you the overall framework so that you can
make effective use of the program.
But before we get to the heart of the matter, the Solver, let’s just take a quick look at the Sudoku editor:

This is about as straightforward as it gets: a Sudoku board on the left, and a vertical bar of the possible
values on the right. Here we see the normal 3x3 board, but the program also supports other sizes, from
3x2 up to 4x4, sometimes called Super Sudoku.
You can see that the cells of the board have coordinates like the squares of a chessboard. In the picture the
value 3 has been placed in cells c4, f2, and g6.
You build up a puzzle by selecting a value from the bar, and then placing that value in the appropriate
cells of the board; and continue doing so until the puzzle is ready.
The editor will only allow you to put a particular value in a particular cell if it doesn’t conflict with the
values you’ve already placed. In this way the editor can be used on its own when solving puzzles
manually.
But here we assume that you want the program to solve it for you, and you do that by bringing up a
separate window containing the Solver.Trích từ: http://www.kilobooks.com