Prologue
(This is a sllighly expanded version of a note posted in the Programmer's Forum.)
In July of 2005 the Washington Post began publishing a daily Soduko puzzle.
After doing a few by hand, I became interested writing a program to solve such
puzzles. Only then did I become aware of the great number of people who also
had that inclination.
My modus operandi has been to mimic existing approaches routine-by-routine, doing
the easier ones first. I finished the “Remote Pairs Test” and started on the
“X-Wing Test” and “Swordfish Test”, having been alerted that these two tests
are related. After a short exposure to the literature, I realized these tests
can be embedded in a more general framework that addresses the reason why
eliminations can be made.
An Example
Some terminology:
Grid :: A 9 x9 set of cells.
Box :: A 3 x 3 set of cells.
Clue Set :: A set 9 cells (a complete row, column, or box).
Conjugate Pair :: A pair of cells in the same clue set which contain the same
candidate clue, where the first is “true” and the second is “false,” or where
the first is “false” and the second is “true.”
The following example is taken from www.scanraid.com (Andrew Stuart) and is
identified as “Swordfish Example.”
- Code: Select all
(1) (2) (3) (4) (5) (6) (7) (8) (9)
(A) 267 1 2679 257 45 247 8 579 3
(B) 5 378 278 237 9 6 1 47 24
(C) 237 379 4 2357 8 1 579 6 29
(D) 9 578 1578 4 12 3 2 58 6
(E) 348 2 58 79 6 79 35 1 48
(F) 346 34 16 8 12 5 239 49 7
(G) 278 6 25789 259 3 289 4 789 1
(H) 248 489 289 1 7 2489 6 3 5
(J) 1 45789 3 6 45 489 79 2 89
Let’s concentrate on a specific clue candidate, say the digit `5’. From this
grid, only candidate 5’s (where there exist two or more choices in a cell)
are transferred to:
- Code: Select all
(1) (2) (3) (4) (5) (6) (7) (8) (9)
(A) - - - 5 5 - - 5 -
(B) - - - - - - - - -
(C) - - - 5 - - 5 - -
(D) - 5 5 - - - - 5 -
(E) - - 5 - - - 5 - -
(F) - - - - - - - - -
(G) - - 5 5 - - - - -
(H) - - - - - - - - -
(J) - 5 - - 5 - - - -
In row (C), we find only two choices for digit 5. Clearly, one choice is right
and the other choice is wrong; equivalently, we one cell is true and the other
is false. Cells at C4 and C7 form a conjugate pair.
Conjugate row pairs: {(C4,C7), (E3,E7), (G3,G4), (J2,J5)}
Conjugate column pairs: {(D2,J2), (A5,J5), (C7,E7), (A8,D8)}
Conjugate box pairs: {(A5,C4), (A8,C7), (D2,E3), (D8,E7), (G3,J2), (G4,J5)}
Cells A4 and D3 are free of any conjugate pair involvement.
We can make graphs of conjugate pair chains by labeling each node in a chain
with alternating letters:
- Code: Select all
1 2 3 4 5 6 7 8 9
(A) X Q T
(B) | /|
(C) T--+-----U/ |
(D) P Y | | /U
(E) | U-----+-----T/
(F) | |
(G) | P--Q |
(H) | / \|
(J) Q--------P
Graph #1 :: The six cells marked either P or Q.
Graph #2 :: The six cells marked either T or U.
Unlinked cell #1 :: The single cell marked X.
Unlinked cell #2 :: The single cell marked Y.
Can we relate graph #1 to graph #2? Examine cells marked Q and T in row (A).
Certainly, both Q and T cannot be “true” since they are in the same row.
Suppose both Q and T to be “false.” If so, then the cells marked P and U are
all true. But this is not possible since both P and U are both in row (D).
So, if cells A5 and A8 cannot both be true and they cannot both be false,
one must be true and the other must be false. We have just identified a hidden
conjugate pair.
We now conclude that X is false because it falls in the same clue set (row A)
as the conjugate pair in cells A5 and A8. With similar reasoning, we conclude
that Y is also false. Both X and Y may be eliminated from further consideration.
Eliminations - If True or if False
An alternate view (just follow the logic):
When A5 is True
---------------------
A4, A8 are false
C7, D8, E3 are true
C4, E7 are false
J5, G3, D2 are false
G4, J2 are true
D3 is false (since E3 is true)
When A5 is False
----------------------
J5, G3, D2 are true
G4, J2 are false
D3, E3 are false (since G3 is true)
E7 is true (since E3 is false)
C4, A8 are true
C7, D8 are false
A4 is false (since A8 is true)
Note: In either case, A4 and D3 are false, and my be eliminated.
Hidden Conjugate Singletons Algorithm
1. For a particular clue candidate ‘x’, identify all of the conjugate pairs.
2. Link pairs together to form a graph or graphs.
If there is only one graph, quit.
3. Loop over clue set choices which have at least two cells from different graphs.
4. In turn, pairwise select two cells from the clue set which are members of
different graphs. Temporarily, assign those two cells the value “false”.
5. Make the forced true/false assignments to the remainder of the two graphs.
Each time you make an assignment of “true”, this means that all other candidates
in row, column and box clue sets must be “false”; if one of these “false”
assignments happens to fall on yet another graph, alternating false and true
assignments can begin anew.
6. Check for conflicts. Once a conflict is found, establish a new conjugate
pair for the two cells selected in step four.
7. Make eliminations.
X-Wing Example
Suppose we have only six candidate cells, arranged as follows:
X - - - - A - - B
- - - - - | - - |
- - - - - | - - |
- Y - - - C - - D
(A,C) and (B,D) are conjugate pairs. A and B cannot both be true; also, they
cannot both be false (since B and D would both be true). Therefore, (A,C) is a
hidden conjugate pair, and X may be removed from the grid. Likewise for Y.
Prediction
Using this method, some puzzles that currently need guessing to finish will
finish without guessing.
Michael A. Deverin (holdout)
devfam47@vtisp.com
10/13/2005
