Uniqueness tests

noeldillabough · Posted: Fri Oct 21, 2005 9:33 pm Post subject: Uniqueness tests

I would like to add uniqueness tests to my solver; it already checks if a puzzle has more than one solution so I can safely use this technique's extra assumption of having one solution.

As far as I know there are 4 forms of this pattern, I understand the basic ones but I definately don't have an overall understanding especially to be able to write a generalized search for this technique.

As a human I can see using

12|1234
12|1234

to remove 34 from the remainder of the right hand box but I"m unsure if this is right.

Can someone list off the forms of this test and how to spot them? For example they need a naked pair in a box that share the same row and col and a matching row/col set containing this naked pair in a neighboring box.

Lummox JR · Posted: Sat Oct 22, 2005 7:27 am Post subject:

For all of the A forms you need to look for a naked pair in the same box which also share a common line (column/row). Call these cells a and b, and their candidates we'll call X and Y. You then need to look for cell c which shares a common line with cell a (but not b) and has at least XY as candidates. (For the B forms, the pair ab need only occupy the same line, but a and c must share a box as well as a line.) Cell d, which also has the XY candidates and at least one more, is the 4th corner of the rectangle.

Test 1: Cell c must have exactly the same candidates as a and b, no extras. XY may be eliminated from cell d.

Test 2 and 2b: Cells c and d each have exactly three candidates XYZ, Z being the same for both cells. In the common box (2a only) and line shared by c and d, eliminate Z from all other cells. This is a special case of test 3.

Test 3 and 3b: Cells c and d both have extra candidates, which may be different and/or shared between the two cells. Those extra candidates make up set S, which has size N. (E.g., if c=126 and d=129, S=69 and N=2.) In each house (box or line) shared by c and d, look for a partial naked subset in N-1 cells which only includes the members of S, or a partial hidden subset (not including c and d) for XY and any members of S. (If the partial hidden subset is just XY, you need just one other cell. For XYZ, 2 cells, WXYZ 3 cells, and so on.) For naked subsets, eliminate S's members from all other cells in that house (except c and d). For hidden subsets, remove all other candidates from those cells. Do not eliminate anything from c or d. (Note: Partial naked and partial hidden subsets are complementary. If there are 6 unfilled cells in a row including c and d, and you have a partial naked pair, you also have a partial hidden triple. c and d together act as one cell instead of two in each subset.)

Test 4 and 4b: In the box and/or line shared by c and d, X may only appear in c and d. Eliminate Y from c and d. (If this case doesn't occur, switch X and Y in the previous sentences and check again.)

Of course none of this covers higher-order uniqueness cases 3x3, 4x4, or 6x6, but those are rare and not worth the effort.

noeldillabough · Posted: Sat Oct 22, 2005 9:21 am Post subject: Ok just to be sure

Thank you! I think I understand, here's an example of each so you can tell me if I'm on the right track:

Test 1: bottom right must be 3 since 12 can be eliminated

12|12
12|123

can 12 be eliminated from the bottom right cell here?

12|12
12|1234

Test2:

12|123
12|123

3s in other cells in the same two houses may be eliminated.

Test3:

12|123
12|124

Look for 34 in one other cell of its house and if found you can remove 34 from the rest of the cells in that house

12|1234
12|1234

Same as above

12|1234
12|1235

Look for 345 in 2 cells of its house and if found remove 345 from the rest of the cells in that house.

Case 4:

Sorry I don't understand case 4. It seems like a guess?

Lummox JR · Posted: Sat Oct 22, 2005 5:03 pm Post subject: Re: Ok just to be sure

noeldillabough · Posted: Sat Oct 22, 2005 8:29 pm Post subject: Re: Ok just to be sure

Lummox JR · Posted: Sun Oct 23, 2005 3:13 am Post subject: Re: Ok just to be sure

noeldillabough · Posted: Mon Oct 24, 2005 1:25 pm Post subject:

I understand now, I mentally pictured both scenarios (ab or ac being the nodes sharing the same box) and labelled them the same way so that a and b were the naked pair.

I have enough to write the code now thank you!