The New Sudoku Players' Forum

[PaulIQ164]

The deduction-from-uniqueness trick that's been posted a few times, where you have a candidate structure like this:

Code: Select all

23 | 23
23 | 236

and you set the lower-right cell to 6 to avoid a duplicate solution. Well, in today's Times Fiendish, I used a slight variation on this. I'd got this far:

Code: Select all

761|824|   
 38|6  |2 1
29 | 31|  8
-----------
34 |   |9 
 8 |  3|   
 56|  2|387
-----------
813|2  |75
629|  7|   
 7 |31 |  2

There's a pretty obvious pair of 19 in r5c1/r6c1 which I'd noted. Then I saw that the 9 in column 4 had to be in rows 5 or 6. I figured that if the 1 was also in column 5 or 6, you'd have one of those bad situations that imply 2 solutions. So I checked, and there was only one other place for the 1 to go in box 5 (in r4c4). This is, I think, slightly different than the 'usual' way of applying this trick, as you don't have to remember any candidates to use it.

[Heuresement]

When I was doing this same one yesterday evening, I, too had a similar thought, but couldn't find a way of using it. I moved my attention to other cells, and was able to complete it, albeit slightly slowly.

I can see that if I had come to the same conclusion, the rest would have become much more straightforward.

Thank you for pointing this out. Hopefully I will add it to my box of tricks and hopefully will be able to use it soon.

[Lummox JR]

At first I was thinking that your deduction may not actually work, but upon seeing the result I get what's going on now. Since the 9 can only be on those two cells, the 1 being there also would be equivalent to another naked pair identical to the first, and would cause multiple solutions. Note though that in this case you really don't have to worry; the first variant of the uniqueness test works just fine here, elminating both 1 and 9 from (4,5) leaving candidates 57. (And actually, there's a hidden 4 in row 7 that busts the puzzle wide open.)

At any rate I think this does qualify as a fourth variant, and a very interesting one at that because it can be applied to cases where the third and fourth cells do not have the same extra candidates. So to formalize it:

If:
- Cells a and b in the same block and the same coloumn/row share only the candidates AB,
- two cells c and d in another block form a rectangle with ab,
- c and d also have AB as candidates
- candidate A is constrained to cells c and d within one of their common houses,
then B may be eliminated from both c and d.

[Pat]

in today's Times Fiendish,

I'd got this far:

Code: Select all

761|824|   
 38|6  |2 1
29 | 31|  8
-----------
34 |   |9 
 8 |  3|   
 56|  2|387
-----------
813|2  |75
629|  7|   
 7 |31 |  2

I saw that the 9 in column 4 had to be in rows 5 or 6.

well, i too saw that the 9 in column 4 had to be in the central box

this eliminates 9 elsewhere in that box

hence r6c5 = 4

- Pat

[PaulIQ164]

Oh yes. I never doubted that there must be some simpler move I'd missed somewhere, since Pappocom sudokus never require this sort of technique. I guess that was it.

[Lummox JR]

Pondering the uniqueness test I've had another insight that I think extends its usefulness slightly. This applies to forms 2, 3, and 4.

Normally, the uniqueness tests are set up as follows:

Code: Select all

. . a|. c .
. . .|. . .
. . b|. d .

...where a and b are a naked pair, and c and d have those same candidates. In the original test, c or d will also have only those two candidates. The other forms all operate differently and will eliminate candidates from c and d's common houses.

You can turn this test 90 degrees, for flavors 2, 3, and 4, to this structure instead:

Code: Select all

. . a|. b .
. . .|. . .
. . c|. d .

Obviously in the first case this makes no difference, but it's with the other styles that it matters.

Uniqueness test format 2: If c and d each have only one additional candidate, which is the same for both cells, that candidate may be eliminated in any cells share a house with both c and d. With the alternate "turned" format, you can still eliminate candidates in the row that c and d share.

Uniqueness test format 3: If c and d each have the same extra N candidates, and N-1 cells in one of their common houses have no candidates except those extras, all other cells in that house may have those candidates eliminated. The same logic works in the turned form, where you can do this elimination in c and d's row.

Uniqueness test format 4: If one of the candidates from a and b is constrained to cells c and d within any of their common houses, the other candidate may not appear in c or d. Since c and d still share a row here, the same logic still applies.

That should give this test some extra legs, to work in situations where previously it couldn't be spotted.

[Lummox JR]

After some exhaustive searching I've found that uniqueness "format B", in which the naked pair is not in the same box, is not only less common than the original A form but also rarely useful. It tends to make eliminations that would be found anyway via another technique, or that would be totally irrelevant because other techniques crack the puzzle just fine. I did however find one puzzle where uniqueness B helps a lot:

Code: Select all

. 8 .|. . .|7 . .
. 1 .|6 2 .|. . .
5 3 .|. . .|. 9 .
-----------------
. . .|8 . .|. 3 .
. . 9|. . .|. 2 8
. . .|9 . .|. . 6
-----------------
. 7 .|. . 5|. . 1
1 . 6|. 7 .|. 8 .
. 2 .|. . .|. 7 .

The first part of the puzzle can be done with basic techniques and subsets alone. After that, uniqueness B comes into play. If you don't use it, you can still find an XYZ-wing, but after that you're pretty well stuck short of using supercoloring, or T&E methods like Trebor's tables.

If you do use the uniqueness B test here, as well as the XYZ-wing, you can then do coloring on the 4's that opens up an XY-wing, and that in turn will crack the puzzle when it eliminates yet another 4.

I had also thought there was a "C format" to be found, in which the a and b cells would alternate like so:

Code: Select all

. . a|c . .
. . .|. . .
. . d|b . .

However the constraints required for the logic to work will ultimately force C to degenerate into form 1A. The reason is that the C format could only apply to this 4th test where one of the candidates is constrained to all 4 cells. The logic of the uniqueness tests relies on a and b being a naked pair, or at least some pair existing in one of the rows or columns. To force that you'd have to constrain the second candidate to one of the columns or rows. However at that point, you'd have a hidden pair in either ac, ad, bc, or bd, and after elimination you have 3 identical cells with 2 candidates, and a third with extras, just as in the original test.

[MadOverlord]

well, i too saw that the 9 in column 4 had to be in the central box

this eliminates 9 elsewhere in that box

hence r6c5 = 4

- Pat

Yes, and also, squares R5C1 and R6C1 in column 1 and R5C4 and R6C4 in column 4 form a Simple X-Wing pattern on possibility <9>, which cracks the puzzle.

I am considering adding the Uniqueness heuristic to the Sudoku Susser. It will be interesting to see how useful it is in actual practice.

One matter for discussion would be: where do you think Uniqueness ranks in terms of difficulty (and thus, order of application when trying to solve a puzzle?)

My current order of operations is:

Pinned Squares 0
Simple Locked Sets 1
Simple Hidden Sets
Intersection Removal
Remote Locked Pairs
Comprehensive Locked Sets
Comprehensive Hidden Sets
Simple X-Wing
Swordfish
Jellyfish
Squirmbag
XY-Wing
XYZ-Wing
Forcing Chains
Fishy Cycles
Nishio
Trebor's Tables
Bowman Bingo

(I have Bowman listed after Tabling because its the closest to guessing, and tabling generates a more realistic solution path).

I'm thinking to slot in Uniqueness between XYZ-Wing and Forcing Chains.

[Lummox JR]

Since uniqueness is a pairwise test, I rate it somewhere close to remote pairs. I think it's easier to spot than an X-wing, but subsets (that is, non-positional subsets anyway) should still go first.

Of course uniqueness is more of a family of tests at this point, in forms 1-4, and 2b-4b. (Only twice now have I found the B form to be very useful, but it's worth having around for sure.) As I mentioned in the programmer's forum there's also the mythical 3x3 uniqueness test, which may as well be bigfoot for anyone's chances of ever running across it; it should have analogs of all the existing tests in forms 1-4, and it too should have A and B variants. I haven't bothered to program the 3x3 into my solver. "Full" 3x3 swordfish (all 9 cells have the candidate) are rare enough, and here 3 of them have to coexist.

[Lummox JR]

For those who've been learning the uniqueness tests, or already use them, I thought I'd post an update here. MadOverlord had some questions about form 3 which revealed that my initial definition falls short of the test's potential.I will illustrate.

This is the layout of the test, where in my examples ab=12, and cd=1234.

Code: Select all

. a .|. c .
. . .|. . .
. b .|. d .

At least c or d must contain 3 or 4. One could be 3 and the other 4, as far as we know at this point. This is a corollary of the fact that these two cells cannot hold both 1 and 2.

It is important first to find all other subsets common to c and d's common box and column/row. If you've done that already, you can find other things. The simplest example of test 3 is this one:

Code: Select all

. a .|. c .
. . .|. e .
. b .|. d .

If e=34, then the other cell with 3 or 4 must appear in c or d. This is a simple naked pair. Try this more complex naked subset:

Code: Select all

. a .|. c .
. . .|. e f
. b .|. d .

If e=35 and f=45, we have a naked subset 345. At least one of the cells c or d must be 3 or 4, so we essentially have the subset defined as 34,35,45. Any other 3's, 4's, and 5's in the unlabled cells in that box can be eliminated. Originally, I thought this sort of test was only possible if cd=12345, having all the extra candidates. I was way off.

Here's one of the cool things: You can also find hidden subsets with 12.

Code: Select all

. a .|. c .
. . .|. e .
. b .|. d .

If e=126, and no other cells common with cde in their box or column can be 1 or 2, we have a hidden pair 12; 6 can be eliminated from e.

It is possible to find hidden subsets with the 34, or naked subsets with the 12. However to do this you must first be able to prove that one of the cd cells is 12. If you have a naked subset that includes the 34, even if the eliminations were already made, it proves either c or d is 12 so you can then look for naked subsets with the 12. If you have a hidden subset that includes the 12, it proves one of the c or d cells is 12 so you can look for hidden subsets with the 34.

And I've finally realized there's also more general form of uniqueness 3, in which c and d need not have the same candidates. As long as you can form a naked subset with the extra candidates combined and N-1 other cells, or if you can still form a hidden subset with the original candidates and N-1 other cells, you still have a valid test. Example:

Code: Select all

. a .|. c .
. . .|. e f
. b .|. d .

If ab=12, c=123, d=124, and e=34, an N-1 set has still been found: The c and d cells cannot be both 3 and 4, because then e has no value. But either c=3 or d=4, because they cannot both be 12. Likewise if f=126, and no cells in that box can be 1 or 2 except c, d, and f, you still have a hidden pair because only one of the cd cells can be 12, so f is not 6.

[Sue De Coq]

I appreciate that this post is slightly off-topic as it doesn't specifically address the issue of Uniqueness but the puzzle given by Lummox JR is solved very quickly by Tabling (as I've implemented it).

The puzzle is straightforward to here:

Code: Select all

 6 8 . | . . 9 | 7 1 .
 9 1 . | 6 2 . | 8 . .
 5 3 . | . . . | 6 9 .
-------+-------+------
 2 . 1 | 8 . . | 9 3 7
 3 . 9 | . . . | . 2 8
 7 . 8 | 9 3 2 | 1 . 6
-------+-------+------
 8 7 3 | . 9 5 | . 6 1
 1 9 6 | . 7 . | . 8 .
 4 2 5 | 1 . . | 3 7 9


whereupon we note:

The values 1 and 8 occupy the cells r3c5 and r3c6 in some order.
- The moves r3c5:=4, r3c6:=4 and r3c6:=7 have been eliminated.
Consider the chains r2c9-5-r8c9~4~r8c6 and r2c9-3-r2c6-3-r8c6.
Whichever of the 2 candidate values fills the cell r8c6, the cell r2c9 does not contain the value 5.
- The move r2c9:=5 has been eliminated.
The cell r2c8 is the only candidate for the value 5 in Row 2.

With that move in place, it's straightforward to complete the puzzle.

[Lummox JR]

Well tabling seems to crack pretty much any puzzle, but the relative difficulty is much much higher.

[MadOverlord]

Code: Select all

. a .|. c .
. . .|. . .
. b .|. d .

At least c or d must contain 3 or 4. One could be 3 and the other 4, as far as we know at this point. This is a corollary of the fact that these two cells cannot hold both 1 and 2.

Okay, this may sound stupid, but I want to absolutely nail down my understanding of this pattern before I start a lot of coding.

I am a bit confused by your use of the word "or". I appear to have the same problem with it as Bill Clinton had with "is".

For example, when you say:

if e=34, then the other cell with 3 or 4 must appear in c or d

it is unclear to me exactly what you are saying. I think I understand it, but it is a bit ambiguous.

Let's look at the possible values for c and what they imply for d (the same applies in reverse, of course).

Code: Select all

 c | d
1 | 34 (because 2 would be a multisolution pattern)
2 | 34 (ditto on 1)
3 | 124
4 | 123


In the case where we are trying to find the 345 naked subset, no matter what the distribution is, we can always find a square in c|d that completes the subset,

ie: if c=1 or 2, use d=34 to make 34,35,45; if c=3, use c=3 to make 3,35,45, and likewise for c=4.

Am I on the right track here? I am pretty sure I understand and agree with the first example, but the ambiguity of your definition makes it hard to follow the later arguments. Please don't take this as criticism; it's just that the logical arguments are much more difficult for me than the coding of the heuristics once I understand them! I really would appreciate more explicit explanations.

For example, when you say:

At least c or d must contain 3 or 4

Do you mean:

1) at least c or d must contain the possibility 3 or 4?

2) one of the squares c or d must have actual final value 3 or 4?

From my analysis above, I expect that (2) is the case.

Moving on to the 12 hidden subset situation; am I correct in restating the logic as follows:

If e=126 (for example), and no other squares in the group have possibilities 12, then we can eliminate 6 because if e=6, then the only places for 1 and 2 are in c and d, and we know that at best, only one of them can contain a 1 or 2. So e must be either 1 or 2.

and (more subtly)

Knowing that e is 12 tells us that cd cannot be 34 or 43, just as they cannot be 12 or 21.

I'll leave it at that point for tonight. I again apologise for being so pedantic, but I really need to lock this down in my mind well enough that I can write an explanation that my 10-year-old son can follow. I find that if I can do that, the programming becomes much easier, and I tend to find implications and "edges" that I can feed back to you logicmeisters.

Oh yeah, in that regard, here's a question: are there higher-order variants of this pattern, like a 3-row,3-column,3-block,9-cell triple?

Or how about something that looks like this?

Code: Select all

. a b | e f .
. c d | g h .

[Lummox JR]

For example, when you say:

if e=34, then the other cell with 3 or 4 must appear in c or d

it is unclear to me exactly what you are saying. I think I understand it, but it is a bit ambiguous.

At least one of the cells c or d must contain either the value 3 or 4. If e=34 and e coincides with cd, then only one of those cells (c or d) can be either 3 or 4, and the other will be neither.

For example, when you say:

At least c or d must contain 3 or 4

Do you mean:

1) at least c or d must contain the possibility 3 or 4?

2) one of the squares c or d must have actual final value 3 or 4?

From my analysis above, I expect that (2) is the case.

Yes, #2 is what I meant.

Moving on to the 12 hidden subset situation; am I correct in restating the logic as follows:

If e=126 (for example), and no other squares in the group have possibilities 12, then we can eliminate 6 because if e=6, then the only places for 1 and 2 are in c and d, and we know that at best, only one of them can contain a 1 or 2. So e must be either 1 or 2.

Exactly.

and (more subtly)

Knowing that e is 12 tells us that cd cannot be 34 or 43, just as they cannot be 12 or 21.

Yep. Because e can only be one value or the other, the other value has to appear in either c or d because all other possibilities have already been eliminated.

Oh yeah, in that regard, here's a question: are there higher-order variants of this pattern, like a 3-row,3-column,3-block,9-cell triple?

Yes, there is a 3x3 variant, but it's never been seen. Uniqueness tests 1-4 can all be done in the 3x3, but it's not worth checking for because it's beyond rare.

Or how about something that looks like this?

Code: Select all

. a b | e f .
. c d | g h .

No, but I think a 4x4 exists in 4 boxes by doubling that pattern. If that's the case then it should also be possible to build a 6x6 in 6 boxes (3x2). I think 6x6 is the utmost limit of the test, because an NxN test requires N boxes, N columns, N rows, and N cells used per box.

Just a bit off topic (or perhaps back on it), it seems the naked and hidden partial subsets of uniqueness test 3 complement each other in a way similar to the way regular full subsets do. If you have 6 cells to work with for example, including c or d, this is the equivalent of 5. If you find a partial naked pair, there's also a partial hidden triple. Weird, huh?