Standardizing the Uniqueness descriptions...

Advanced methods and approaches for solving Sudoku puzzles
You might find it interesting that the 2-digit uniqueness patterns correspond with the POM solution patterns sets that have only 2 candidate patterns. This may provide a means of extending to 3 digit uniqueness patterns. For example, noting that
Code: Select all
`X  X  X | X  X  X X  .  X | .  .  X X  .  X | .  X  X --------+---------X  X  X | X  X  X X  X  X | X  X  X X  X  X | .  .  X `

leads us to the following POM solution patterns
Code: Select all
`X  X  X | X  X  X X  a  X | b  c  X X  bc X | a  X  X --------+---------X  X  X | X  X  X X  X  X | X  X  X X  X  X | c  ab X `

could then lead us to the following 3-digit uniqueness pattern
Code: Select all
`X  X  X | X  X  X X  12 X | 23 13 X X  12 X | 12 X  X --------+---------X  X  X | X  X  X X  X  X | X  X  X X  X  X | 13 13 X `

The above candidate pattern would have multiple solutions, and so would be untennable with a single solution puzzle. Of course there are a ton of these, but they might even be more prevalent that the 2-digit cases.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Generalized uniqueness NxN

Interesting, MJ, although the case you presented is incomplete. That 23 cell has to be a 123 because of the two other uniqueness patterns in there; there's no way you can eliminate that 1 without T&E, which presumably you'd use uniqueness to avoid. (And in any case, uniqueness tests for a rectangular form can still be run if you're missing a candidate from one cell; the rules change only slightly.) So really, you have this situation:
Code: Select all
`12 |123 1312 |12  .-----------.  |13  13`

But to use this pattern, we need extra candidates in some of the cells.

All things considered, I'd call this a warped 3x3. In a normal 3x3 you have 3 rows, 3 columns, 3 boxes, and 3 candidates per box for 9 cells total. Here the latter restriction (3 candidates per box) is gone, but the rest of it holds up. This suggests that for higher-order uniqueness tests, the N candidates per box/column/row rule is not strictly necessary.

That being the case, you can apply all four known uniqueness tests using modified rules. I present here the generalized NxN uniqueness test:

Generalized NxN unique grid test:
Requires N candidates in exactly N columns, N rows, and N boxes. The N candidates will be called set S. Any unfilled cell in the NxN grid which contains members of S is a pattern cell. Roof cells are any cells in the pattern which contain only members of S, at least 2 candidates. Floor cells are pattern cells that contain at least one member of S, along with other candidates. For the uniqueness test to apply, all of the floor cells (F) must occupy the same box and/or line, which we'll call G (their common group). It is not necessary for all members of S to appear in F, as Myth Jellies' pattern demonstrates in the very first box and column, so the candidates from S that do appear in F are set T; Tn is its size, which is also the size of F. It is also possible for two G's to exist; run tests 2-4 separately for each.

Test 1: Only one floor cell exists. Eliminate S from its candidates.

Test 2: All floor cells share the same candidate X, but no others except members of S. Eliminate X from all cells in G-F.

Test 3: The set of all floor cell candidates combined is T+E, where E represents the extra candidates. If a partial naked subset size M is found with all the members of E, in M-1 cells in G-F, or a complementary hidden subset size M is found with all the members of T, in M-Tn+1 cells in G-F, perform eliminations within G-F as if a full subset was found. (Subset solvers: Pretend all F are T+E, except one cell which is just E. Then look for subsets accordingly.)

Test 4: Within G, all members of T except for one candidate, X, are constrained to F. Eliminate X in F.

Note that the loop form currently under discussion can also be generalized in this way. In the loop form, each row or column or box in the pattern will have N or fewer pattern cells. It's a lot trickier to spot such pattern cells, however.
Lummox JR

Posts: 125
Joined: 22 September 2005

Lummox JR wrote:I think you're about right, Nick, although it's a little hairy to follow. I believe though that you're mixing up the terms "roof" and "floor", since by my understanding the roof cells are the ones with just the naked pair.

No, the floor squares are the initial naked pair. The roof squares are the ones that cap off the unique rectangle/loop and have the extra values.

Negatory! We treat them as a quantum pair of 123456 and 3456. It is important not to remove extra candidates from the 12 cell; at the very least the 12 cell must have one of the extras just to prevent a subset solver from finding a naked 12 that doesn't exist.

This is a bit apples-and-oranges. In my implementation, for efficiency, I make an array of the squares that can possibly be part of the naked or hidden set (which will never be more than 8, including an entry for the "quantum" square), then search on that. If you are searching on a full 9-square group, then Lummox's way of describing it is correct.

All that boiils down to a simple (but slippery to grasp) statement: If a partial subset exists when removing 12 from one floor cell, it proves 12 exists in the other.

This is probably a good way of saying it - if we can find the naked/hidden set, it means that one of the squares is <12>.

But, turning it around, can we say that if no naked set is possible, then neither of the squares is <12>? I'm still wondering if there is leverage there.

I've implemented Unique Loops in the Susser and have run about 100 "tough" puzzles through the rating system. It's found 2-3 Unique Loops so far, all either type -1 or -1B. Once I've run all my puzzles through the rater I'll post some example loops.

Posts: 81
Joined: 10 June 2005

Re: Generalized uniqueness NxN

Lummox JR wrote:But to use this pattern, we need extra candidates in some of the cells.

It's hard to tell without seeing an actual complete example, but this looks to me like an intersection of two Unique Rectangles -- wouldn't it just decompose into solving each individually?

Posts: 81
Joined: 10 June 2005

DanO wrote:
Code: Select all
`+-------------+-------------+-------------+| .   .   .   | .   .   .   | .   .   .   | | .   .   .   | 123 12  .   | .   .   .   | | .   .   .   | .   .   .   | .   .   .   | +-------------+-------------+-------------+| .   .   .   | 123 .   .   | .   12  .   | | 12  .   .   | .   12  .   | .   .   .   | | 123 .   .   | 34  .   .   | .   123 .   | +-------------+-------------+-------------+| .   .   .   | .   .   .   | .   .   .   | | .   .   .   | .   .   .   | .   .   .   | | .   .   .   | .   .   .   | .   .   .   | +-------------+-------------+-------------+`
Good luck
DanO, your example does not qualify as an Unique Loop; what are you trying to say?

If R6C4=3 a deadly pattern on <12> will emerge.

It is however unclear if this could ever occur because the <3> had to somehow be removed from R4C8. while leaving the others at R4C4 and R6C8 in place. Perhaps a unique rectangle could have removed it.
DanO

Posts: 40
Joined: 18 October 2005

[EDIT -- this post is erroneous but I'm leaving it has been pointed to more than once.]

Have these been covered?

Code: Select all
`  .  . 12  |  . 23  .  |  . 134 .   .  .  .  |  .  .  .  |  .  .  .   .  .  .  |  .  .  .  |  .  .  .   ---------+-----------+---------  .  . 12  |  . 23  .  |  . 13  .   .  .  .  |  .  .  .  |  .  .  .   .  .  .  |  .  .  .  |  .  .  .   ---------+-----------+---------  .  .  .  |  .  .  .  |  .  .  .   .  .  .  |  .  .  .  |  .  .  .   .  .  .  |  .  .  .  |  .  .  .   .  . 12  |  . 23  .  |  . 134 .   .  .  .  |  .  .  .  |  .  .  .   .  .  .  |  .  .  .  |  .  .  .   ---------+-----------+---------  .  . 23  |  . 13  .  |  . 12  .   .  .  .  |  .  .  .  |  .  .  .   .  .  .  |  .  .  .  |  .  .  .   ---------+-----------+---------  .  . 13  |  . 12  .  |  . 23  .   .  .  .  |  .  .  .  |  .  .  .   .  .  .  |  .  .  .  |  .  .  . `

r1c8 must be 4 [No such deduction can be made.]
Last edited by tso on Sat Nov 26, 2005 6:15 pm, edited 1 time in total.
tso

Posts: 798
Joined: 22 June 2005

I found this pattern buried in Menneske.no Super Hard #6678464:
Code: Select all
`+ - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .  489 489  |   + - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   + - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .  48   |   |   .   .   .   |   .   .   .   |   .  489 489  |   |   .   .   .   |   .   .   .   |   .   .   .   |   + - - - - - - - + - - - - - - - + - - - - - - - +`
R3C8<>9
Is it a new uniqueness type or just a variant?
DanO

Posts: 40
Joined: 18 October 2005

I just ran about 1600 tough puzzles through my automated solver/rater, and found 13 Unique Loops (as compared to 406 Unique Rectangles). Here are some samples:

* = floor
+ = loop
# = roof
- = reduction

Type-1 Unique Loop
Code: Select all
`+-------------------+-------------------+-------------------+| 5     189   89    | 69    1246  24    | 3     7     246   | | 19    3     2     | 569   1456  7     | 456   456   8     | |*46   *46    7     | 8     25    3     | 9     25    1     | +-------------------+-------------------+-------------------+| 28    5     38    | 4     9     6     | 7     1     23    | | 29   +46    39    | 7     8     1     | 2456  246  -23456 | |+46    7     1     | 2     3     5     | 8     9    #46    | +-------------------+-------------------+-------------------+| 3     12    4     | 56    7     9     | 1256  8     256   | | 7     28    5     | 1     246   248   | 246   3     9     | | 189   1289  6     | 3     245   248   | 1245  245   7     | +-------------------+-------------------+-------------------+`

Type-2 Unique Loop
Code: Select all
`+-------------------+-------------------+-------------------+| 3    #569  #569   | 7    -4569  2     | 8     1    -4569  | | 479   8    -15679 | 3     14569 469   | 2469  25    45679 | | 479   2    -15679 | 8     14569 469   | 469   3     45679 | +-------------------+-------------------+-------------------+| 5     4    +69    |*69    3     1     | 7     8     2     | | 1    +69    8     |*69    2     7     | 5     4     3     | | 2     7     3     | 4     8     5     | 16    9     16    | +-------------------+-------------------+-------------------+| 6     3     4     | 1     7     8     | 29    25    59    | | 79    159   579   | 2     49    3     | 14    6     8     | | 8     19    2     | 5     469   469   | 3     7     14    | +-------------------+-------------------+-------------------+`

Type-3 Unique Loop
Code: Select all
`+----------------+----------------+----------------+| 1    2    3    | 4    5    7    | 6    8    9    | |-456  45   56   | 18   18   9    | 2    3    7    | | 7    8    9    |*23  *23   6    | 4    5    1    | +----------------+----------------+----------------+|#235  6    7    |-23   4    1    | 358  9    2358 | |-234 -14   8    | 9    6    5    | 13   7    23   | |#2359 159  15   | 7   -23   8    | 135  6    4    | +----------------+----------------+----------------+| 59   3    2    | 6    89   4    | 7    1    58   | |-569  159  156  | 58   7    2    | 3589 4    358  | | 8    7    4    | 15   19   3    | 59   2    6    | +----------------+----------------+----------------+`

Type-4 Unique Loop
Code: Select all
`+-------------+-------------+-------------+| 12  29  3   | 4   5  +78  | 6  *78  19  | | 45  56  46  | 1  +78  9   | 3  *78  2   | | 7   8   19  | 2   6   3   | 5   4   19  | +-------------+-------------+-------------+| 23  4   5   | 39  27  6   | 79  1   8   | | 13  79  8   | 39  4   17  | 2   6   5   | | 6   279 19  | 5  -278-178 | 79  3   4   | +-------------+-------------+-------------+| 458 56  7   | 68  9   245 | 1   25  3   | | 58  3   26  | 68  1   25  | 4   9   7   | | 9   1   24  | 7   3   245 | 8   25  6   | +-------------+-------------+-------------+`

Note that this last one is a "crossed loop" that forms a figure-8.

I have not found any -B variants other than -1B's, which can be looked at as -1s, it just depends on what starting pair gets picked as the floor. I have also not found any loops longer that 6 squares.

Share and Enjoy!

Posts: 81
Joined: 10 June 2005

DanO wrote:I found this pattern buried in Menneske.no Super Hard #6678464:
Code: Select all
`+ - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .  489 489  |   + - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   + - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .  48   |   |   .   .   .   |   .   .   .   |   .  489 489  |   |   .   .   .   |   .   .   .   |   .   .   .   |   + - - - - - - - + - - - - - - - + - - - - - - - +`
R3C8<>9
Is it a new uniqueness type or just a variant?

I don't follow, DanO. If R3C8=9, no deadly pattern emerges with these cells.
Lummox JR

Posts: 125
Joined: 22 September 2005

If R7C9=4 there is a deadly pattern on 89 and R3C8 must be 4. If R7C9=8 there is a deadly pattern on 49 and R3C8 must be 8. Therefore R3C8 cannot be 9.
DanO

Posts: 40
Joined: 18 October 2005

Lummox JR wrote:I think you're about right, Nick, although it's a little hairy to follow. I believe though that you're mixing up the terms "roof" and "floor", since by my understanding the roof cells are the ones with just the naked pair.

No, the floor squares are the initial naked pair. The roof squares are the ones that cap off the unique rectangle/loop and have the extra values.

Doh! Then I'll have to switch around floor and roof in all my descriptions. Perhaps it's better if we can think of a clearer terminology.
All that boiils down to a simple (but slippery to grasp) statement: If a partial subset exists when removing 12 from one floor cell, it proves 12 exists in the other.

This is probably a good way of saying it - if we can find the naked/hidden set, it means that one of the squares is <12>.

But, turning it around, can we say that if no naked set is possible, then neither of the squares is <12>? I'm still wondering if there is leverage there.

Not at all, because of the logic I stated above. If f exists, there is not enough information to tell if it translates to F. That is, if the opportunity for a fractional subset is there, nothing proves it actually is there. Failure to prove A (elimination from one cell only) does not imply B (elimination from both cells). Failure to find a partial subset does not imply that a fractional subset must be the answer, even if the opportunity is apparently there. It is possible that both 12's will ultimately be eliminated, but it is not possible for a variant of uniqueness 3, or any other uniqueness test, to do so. Uniqueness 3 only uncovers a partial subset by proving that eliminating 12 from both cells is impossible. There is no related proof that insists 12 must be eliminated from both under different circumstances.

To put this in simplest possible terms:

Uniqueness: I see that at least one cell can have 12 eliminated.
Partial subset: You can't eliminate 12 from both cells, because the result will be impossible.
Uniqueness: Oh, then 12 can come out of only one cell.

Contrast with:

Uniqueness: I see that at least one cell can have 12 eliminated.
Fractional subset: If you could eliminate 12 from both cells, I could do something. Can you?
Uniqueness: Gosh, I don't know.

In the partial subset case there is pressure from the puzzle to retain one of the 12's, therefore giving us the information we need to make eliminations. In a fractional subset case there is absolutely no pressure from the rest of the puzzle to either retain or delete the 12's; the only pressure comes from uniqueness, which says at least one must be deleted. If the puzzle has pressure to delete both 12's, it already exists independently of the uniqueness test. Therefore, nothing can ever push a uniqueness test to eliminate from both cells.

From that perspective, I can now say affirmatively that eliminating both 12's via an undiscovered uniqueness test is impossible. All 2-digit uniqueness tests will, if they find anything, prove the base candidates exist in one and only one cell. Anything that could prove otherwise could do so without uniqueness.
Lummox JR

Posts: 125
Joined: 22 September 2005

I have a suggestion: I think we should change
the name "Uniqueness Test" to "Uniqueness Rule".
The main reason for my suggestion is that there really is no "test"
involved in the uniqueness approach. We recognize some
key patterns, apply logic, and eliminate candidates.

In fact, the name Uniqueness Test might easily lead some
to believe that we are somehow testing the puzzle to see if
it has a unique solution (which of course is not right).

I realize the name is already "out there" and popular ....
but since people are now coming up with these great new ideas
related to uniqueness, why not introduce a new name at the same time?
Maybe in the next version of the (very helpful) Ultimate Guide?

So ... that's my idea. Clearly not a super-important issue ... but
maybe something to consider?

[edit: just improved the wording]
Nick67

Posts: 113
Joined: 24 August 2007

I must have overlooked tso's post on the 5th. That pattern doesn't work because there are more boxes than candidates. Something else in box 5 in the first pattern could, for example, force the 23 to be either a 2 or a 3. This doesn't fit the NxN generalized pattern or any loop pattern.
Lummox JR

Posts: 125
Joined: 22 September 2005

I think I've managed to implement Uniqueness types 1-4, in both A and B flavours. I've run my generator lots of times but have only come up with samples that will test type 1 and type 3. Does anybody have any examples of puzzles requiring types 2 and 4?

I've also found that A and B puzzles can be handled the same, simply by working on the intersection of the houses of the roof cells, C and D. If they're in the same block (Type A) you get a block and a row or column. If it's a type B, you only get a row or column. Just testing for the intersection of C and D seems to cover both types.
gaby

Posts: 15
Joined: 25 October 2005

Gaby wrote:Does anybody have any examples of puzzles requiring types 2 and 4?

This one has a type 2 (these are very rare):

Code: Select all
`8 9 6|. 4 .|. . .. . .|. . .|7 . 2. . .|9 . .|. 6 .-----+-----+-----. 1 8|. . 9|. 2 46 . .|3 . .|. 8 .. 3 .|. 1 .|. . .-----+-----+-----. . .|4 . .|2 . .3 . .|. . 6|. . .. . 5|. 3 .|. 1 .`

This one has a type 4:

Code: Select all
`. . .|. 7 .|. 8 6. 2 .|5 . .|. . .. . .|. . .|. . .-----+-----+-----. . .|. 6 3|. . 7. 5 .|. . .|3 . .. . .|. 1 .|. . .-----+-----+-----. . .|4 . .|2 5 .6 . .|2 . .|. . .1 . .|. . .|. . .`

Type 2 and 4 are more common in combination with tabling, but I guess that's not what you're looking for.

Ruud.
Ruud

Posts: 664
Joined: 28 October 2005

PreviousNext