Forcing Chains implementation

Ruud · Site Admin

I will try...

The problem definition:

In a standard 9x9 Sudoku, there are 81 cells x 9 digits = 729 candidates. Only 81 of these candidates belong to the solution.

The puzzle also has 4 rules:
1. Each cell must contain 1 digit (81 cells = 81 constraints)
2. Each row must contain 1 of each digit (alldifferent, 9 rows x 9 digits = 81 constraints)
3. Each column must contain 1 of each digit (alldifferent, 9 columns x 9 digits = 81 constraints)
4. Each box must contain 1 of each digit (alldifferent, 9 boxes x 9 digits = 81 constraints)

These 4 rules produce a total of 81 x 4 = 324 constraints.

The data structures:

Now imagine a matrix where all 324 constraints are lined up on the X axis, and the 729 candidates are lined up at the Y axis.

In the cells of this grid, we can place nodes, which have a link to the candidate (a row in DLX terms) and to the constraint (a column in DLX terms).

When all cells are empty and all 729 candidates are still in the race, there will be 4 nodes placed for each of these candidates, one for each constraint that it competes in.

A total of 729 x 4 = 2916 nodes are placed.
Each Y column contains 9 nodes. (x 324 columns, that's also 2916, check)

For each column, a header node is placed on top. These allow us to address the columns.

Now we build 2 linked lists for all the nodes, connecting all nodes within a column (up and down), including the header node. This groups all the candidates that are competing within a constraint. The last and first node close the loop, creating 2 cycles.

Next we build 2 linked lists for all the nodes, connecting all the nodes within a row (left and right). Here too, the last and first node close the loop.

Each header node has a counter for the number of connected nodes (= remaining candidates within that constraint). To be able to access this counter, each node also has a direct link to its header node.

Finally, the header nodes are linked together (left & right) with a double linked list. This double list connects at both ends with a root node, from where we can access all headers.

The principles:

To solve the puzzle, we need a mechanism that reduces the grid to a situation where each constraint has 1 node left. This situation is called a solution. There can be more than 1, or this situation is never found (unsolvable grid)

A node can remove itself from the list, by connecting its UP and DOWN node to each other. Since it still has the links to these 2 nodes, it can rejoin the list, by restoring the old links. This only works when nodes are restored in the reverse order in which they were removed. A recursive process can do this. When a node removes/rejoins the list, it updates the counter in the header, so each header 'knows' how many candidates it has left.

Since there are 4 nodes for each candidate, linked with the Right & Left links, it is possible to perform this remove-rejoin trick for all 4 nodes, regardless of which node is the starter.

Tuning the orchestra:

First, all clues to the puzzle are processed. For each clue, a digit in a cell, there are 8 digits that no longer go into this cell. We find these candidates in the Y axis, and remove (disable) all 4 nodes for these candidates.

With a minimal Sudoku of 17 clues, there are 8 x 17 = 136 candidates (rows) out of the race.

At this point, I have optimized the code. All deductions made by the human-style solver, resulting in further eliminations, are also removing rows from the list.

There are 2 types of deductions in a solver:

1. Disable (simply remove all 4 nodes from their constraint list)
2. Select (step sideways through the 4 constraint nodes, for each of them, step down to each competing node, and for each of those, step sideways and remove the 4 nodes from their constraint lists)

I think that's where the links really start dancing.

All reinserts (due to backtracking) are done in the reverse order, so where you step down to Cover, you step up to uncover.

Start the music

First you select the constraint with the lowest candidate count.
This constraint is 'covered', by removing it temporarily from the header list. All candidate nodes beneath it are also covered, but are still accessible from the header itself. For each of the nodes, all associated headers are also covered, again by dancing sideways to process each header. This dancing is exactly the same thing you would do when following a lookahead-1 implication chain. The 'covered' candidates are in fact the FALSE implications that you would make, whereas the selected candidates are the assertions.

The selected candidate is added to a stack, and the dancing continues at the next recursion level. The recursion reaches an end when no more headers are left, because they're all covered. At this point it reports that a solution has been found. It is also possible that it reaches a header with no more candidates, because the recursion relies on the presence of candidates, recursion also starts backtracking at this point.

When returning from recursion, all damage is restored and the next candidate it tried, until all candidates had their turn.

The finale

When all paths are searched, the rows that were disabled for the clues are reenabled, and the grid is back in its original state, ready to dance with the next puzzle.

I'm afraid I cannot explain it any easier that this. But it may have helped that I am NOT a mathematician, but a programmer.

(corrected a few row-column mixups)

Ruud.

Bob Hanson · Posted: Fri Nov 11, 2005 9:39 pm Post subject:

wow! Thank you for that explanation. Quite the conceptualization. And I thought Tchaikovsky's Nutcracker was beautiful. Whew. I suppose this is a general solution to any NP-complete problem (differing in details and specific constraints, of course). Amazing.

And this is FAST?
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

It is fast because in each recursion the number of nodes reduces. With the way the headers are selected, it always picks the strong chains first, without even knowing what a strong chain is.

When you use arrays or even bit-arrays, you still need to go through the entire list, even though at greater depth, there may only be 2 or 3 candidates left. This algorithm uses exactly as many iterations as it needs at each level.

And, personally, I think it's beautiful in its simplicity!

Ruud.

P.S. thanks for the link to my site. I've returned the honor.

Ruud · Site Admin