Hidden Conjugate Singletons Test

Advanced methods and approaches for solving Sudoku puzzles

Hidden Conjugate Singletons Test

Postby holdout » Sat Oct 15, 2005 7:55 pm

Hidden Conjugate Singletons Test

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
holdout
 
Posts: 35
Joined: 30 August 2005
Location: Bowie, Maryland USA

Postby Lummox JR » Sat Oct 15, 2005 10:03 pm

The method you've just described is simple coloring. You've found that the P=T and Q=U based on the fact that P and U coincide, and Q and T also coincide. In coloring terminology, P excludes U, or P!U, and similarly Q!T.

In coloring you don't necessarily have to prove that PQ=TU, but instead you can make eliminations other ways. For example, knowing that P!U, you know that P and U cannot both be true. Therefore at least Q or T, if not both, are true. As the X cell at 4A appears at a place where Q and T intersect, it must be false. You can use the same deductions based on Q!T to eliminate Y.

This method I refer to as complete simple coloring, because it seems most people don't take the logic of coloring far enough to find eliminations in this way. Finding that two colors are equivalent as you did is useful, but naturally won't always prove to be possible.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby Hanyou Hottie » Sat Oct 15, 2005 10:05 pm

Hi there. I'd like to first say that I'm somewhat new to sudoku, so I may not have the greatest understanding of the subject, but I'd just like to point out that I was able to get the same results that you did by using the Complete Simple Colors method (as defined by Lummox JR here). Because one member from each graph resides in group 4 (P at D2 and U at E3), transitivity is established between the two graphs (P!U). This all boils down to meaning you can eliminate any candidates on an intersection of T and Q, which removes A4. After that you can clear all your colors and re-color (this time only needing two colors) to eliminate D3.

I don't know if this means that Complete Simple Colors is a superset of your Hidden Conjugate method or not, but I thought I'd point it out.
Hanyou Hottie
 
Posts: 8
Joined: 15 October 2005

Postby Hanyou Hottie » Sat Oct 15, 2005 10:16 pm

Wow, look at that. You beat me to it by two minutes, although your explination was much clearer (I didn't even notice that Q and T conincided /swt).
Hanyou Hottie
 
Posts: 8
Joined: 15 October 2005

Postby Lummox JR » Sun Oct 16, 2005 12:32 am

Yep, it is a superset. Essentially the method holdout presented here is what's shown on Sadman Software's page which has a section on finding equivalent colors.

If you're coloring--and especially supercoloring--by hand, finding equivalent colors can save you a lot of time.
Lummox JR
 
Posts: 125
Joined: 22 September 2005


Return to Advanced solving techniques