|
Have you ever wondered what could be the fastest method to solve a Sudoku?
There is a name for it. The Dancing Links algorithm devised by
Don Knuth has so far outrun every other method that has competed
against it.
It is elegant, simple, but very elusive. Programmers speak in terms of Nodes Visited, double Linked Lists and more of that jargon. Although I've got it implemented in SudoCue for some time now, I did not really grasp the concept of it. That is the good fortune for us programmers, being able to build something that we do not understand, but making it work just the same. The latest release of SudoCue includes a visualizer for the algorithm. You can actually see the links perform their dance. To open the viewer, select DLX in the View menu. What do you see? There are 4 constraint types for a Sudoku puzzle. - Each cell can contain only a single digit; - Each row must contain one of each digit; - Each column must contain one of each digit; - Each 3x3 box must contain one of each digit. The viewer shows all 324 constraints that must be met. In terms of Dancing Links, these are the columns. With an empty grid, there are 9 candidates competing in each of these constraints. A candidate is a particular digit assigned to a cell. Each candidate must fight for its existence in each of the 4 major areas. When it loses in one of them, it is removed from all 4 areas. The candidates are represented by a blue rectangle in each of the 4 areas. When a constraint has declared a winner, that candidate will be shown in green. The visualizer is automalically updated when the program eliminates candidates, even when it is done by human-style solving techniques. As soon as the Dancing Links algorithm kicks into action, you will notice that the links actually start dancing. The DLX (Dancing Links) main code will select each candidate and Cover the constraints it competes in. This covering can be seen in the visualizer. Each covered constraint shows the header in a pushed state (like a button). When you use the visualizer, the algorithm is deliberately slowed down, so you can see the effects. Without the viewer, this process happens in only a few microseconds. |
