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