## Standardizing the Uniqueness descriptions...

Advanced methods and approaches for solving Sudoku puzzles

### Re: DanO argument

bennys wrote:To me it looks prefecly good argument.
The last code in Lummox answer is not perfectly valid possibility.

Doh! It took me a minute to look over that again before I realized my mistake. You're right; I completely missed something there. My "valid possibility" is in fact the deadly pattern with 1 and 4.

It takes forcing-chain logic to see this, though. If you let the 19 cell be 9, it forms 14 in the other two cells in box 5, eliminating 8 from the 18 cell via uniqueness 2 and putting a 1 there. If you let the 18 cell be 8, then it forms 14 in the other cells in box 8, exposing a naked 9 via uniqueness 1 in box 5 and therefore the 19 cell cannot be 9. So either the 19 or the 18 cell must be 1, and therefore 1 can be eliminated from the rest of column 6.
Lummox JR

Posts: 125
Joined: 22 September 2005

### Another one?

In Max beran post http://forum.enjoysudoku.com/viewtopic.php?t=1698

there is another one I think
With this code
Code: Select all
`+----------------+----------------+----------------+|                |                |                ||                |                |                ||                |                |                |+----------------+----------------+----------------+|                |                |52     256      ||                |                |                ||                |                |                |+----------------+----------------+----------------+|                |                |       75       ||                |                |                ||                |                |752    52       |+----------------+----------------+----------------+`

When you get R9C7 = 7 OR R4C8 = 6
But R9C7 = 7 -> R7C8 = 5 -> R4C8 = 6
So R4C8 = 6
bennys

Posts: 156
Joined: 28 September 2005

### Re: Another one?

Benny,
The possibilities are: (r9c7=7 or r4c8=6) or (r9c7=7 and r4c8=6)
You forcing net r9c7=7 => r7c8=5 => r9c8=2 => r4c8=6 proved the latter case is true. As such, not only that r4c8=6, but r9c7 must be 7.
Jeff

Posts: 708
Joined: 01 August 2005

Lummox JR wrote:DanO's right, although an explanation as to why would've saved me some grief.

And it would help the rest of us understand it -- so would either of you try and explain it. Is there a way to generalize it into a pattern that is more broadly useful?

We can't prove that we never have such a case. (Pop a naked 12 into two other positions in that column, and there you go.) Rather, the uniqueness logic cannot prove such to be the case when using the 12's as the roof cells.

Which brings up the question - is there an extension to the unique rectangles pattern (perhaps with the naked 12, etc) that gives us enough additional information to permit additional reductions. This was my actual point earlier, if badly stated.

Posts: 81
Joined: 10 June 2005

### To jeff

For me anyway OR is not exclusive.
So I don’t understand your post at all.
bennys

Posts: 156
Joined: 28 September 2005

Menneske.no Super Hard #5916740
Code: Select all
`+-------+-------+-------+| 5 . . | . . . | 3 7 . | | . 3 2 | . . 7 | . . 8 | | . . 7 | 8 . 3 | 9 . 1 | +-------+-------+-------+| . 5 . | 4 9 6 | 7 1 . | | . . . | 7 8 1 | . . . | | . 7 1 | 2 3 5 | 8 9 . | +-------+-------+-------+| 3 . 4 | . 7 9 | . 8 . | | 7 . 5 | 1 . . | . 3 9 | | . . 6 | 3 . . | . . 7 | +-------+-------+-------+`

Leads to an example of the uniqueness rule in the other shapes department
Code: Select all
`+ - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   |  46  46   .   |   .   .   .   |   .   .   .   |   + - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .   .   |   |   .  46   .   |   .   .   .   |   .   .  46x  |   |  46   .   .   |   .   .   .   |   .   .  46   |   + - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   |   .   .   .   |   .   .   .   |   .   .   .   |   + - - - - - - - + - - - - - - - + - - - - - - - +`
DanO

Posts: 40
Joined: 18 October 2005

### Amazing

I didn’t believe anybody would find an example
bennys

Posts: 156
Joined: 28 September 2005

### Re: Amazing

bennys wrote:I didn’t believe anybody would find an example

Me neither; an interesting pattern, but it doesn't really buy any significant progress, at least in this puzzle. Either way, you need tabling to solve the puzzle.

DanO, do you mind if I add this to the sample puzzles in the Susser? I know Vegard wouldn't mind, but since you're the one who saw it, I thought I should ask.

Dunno if I'll create a solver for it, though.

Posts: 81
Joined: 10 June 2005

Lummox JR wrote:DanO's right, although an explanation as to why would've saved me some grief.

And it would help the rest of us understand it -- so would either of you try and explain it. Is there a way to generalize it into a pattern that is more broadly useful?

As far as I can tell, no. DanO's case isn't so much of a pattern as a special kind of forcing chain.
We can't prove that we never have such a case. (Pop a naked 12 into two other positions in that column, and there you go.) Rather, the uniqueness logic cannot prove such to be the case when using the 12's as the roof cells.

Which brings up the question - is there an extension to the unique rectangles pattern (perhaps with the naked 12, etc) that gives us enough additional information to permit additional reductions. This was my actual point earlier, if badly stated.

I get what you're after here, which is basically a fifth test. But there's no way it can be found as an extension of the four known tests. Certainly subset rules will not rid both floor cells of the roof candidates, at least not as part of any uniqueness test on that rectangle.

I can't rule out that there's not an undiscovered uniqueness test that would bare both the floor cells, but I strongly doubt it because of the construction of the test. The fact that it can eliminate the roof candidates in one cell combines, in all known tests, with something that places one of the roof candidates in one floor cell. Considering test 3 is basically a combination of uniqueness with subsets, and 2 is sort of a special case of that, any undiscovered tests likely combine uniqueness with some other technique. I thought coloring might be an interesting possibility, but working over the clues it occurred to me that it should mostly just reduce to regular coloring.

At any rate, it's entirely impossible for existing tests to be extended in any way that would bare both floor cells. It's also not possible for an overall pattern (like an extension of the rectangle) to prove the same without the assistance of some undiscovered test, because any uniqueness test no matter what the pattern is predicated on an unvaoidable set, and those are broken merely by one cell in the pattern that doesn't contain the killer candidates.
Lummox JR

Posts: 125
Joined: 22 September 2005

I was going to file for a patent on the extended forms but the patent would be invalid if the form in not actually usefull

You will probably also want to list the extended form that looks like
Code: Select all
`+ - - - - - - - + - - - - - - - + - - - - - - - + |   .   .   .   |   .  12   .   |   .  12x  .   |    |   .  12   .   |   .   .   .   |   .  12   .   |    |   .  12   .   |   .  12   .   |   .   .   .   |    + - - - - - - - + - - - - - - - + - - - - - - - +`

These come directly from the possible patterns of 2 digits on a grid and extend to 4, 5, 6, 7 and 9 blocks. But anything above 3 will probably be too rare to bother looking for.

I'v also been searching for an example of the deadly pattern where 3 of the corners are singles. It might not be possible for such to exist or they may simply degenerate before it is useful to search for unique rectangles.
DanO

Posts: 40
Joined: 18 October 2005

As Paul mentioned, that extended form doesn't seem to be very likely; it hasn't come up yet that anyone's seen. Of course the same applies to the 3x3, 4x4, and 6x6 uniqueness forms, but then at least those have the benefit of being easier to spot.

My own thought is that more complex patterns may be out there, but are probably not worth searching for due to the difficulty in spotting them. Writing an algorithm to find those sets would be a trying thing, and in probably 99.999% of cases would be a huge waste of cycles. Likewise I don't think it's much more promising for human solvers.
Lummox JR

Posts: 125
Joined: 22 September 2005

DanO wrote:I was going to file for a patent on the extended forms but the patent would be invalid if the form in not actually usefull

I think the next step is to see if we can come up with a generalized description.

Here is my first stab at it:

A Unique Loop consists of a closed loop of naked pairs on the same number, traversing the rows and columns of the puzzle, with the additional restriction that each square in the loop is a naked pair in its block as well as its row and/or column.

Thus a Unique Rectangle is the simplest instance of a Unique Loop.

Assuming that that is correct, then:

In a Type-1 Unique Loop, one of the naked pairs has additional value(s); in order to prevent a deadly pattern, that square can be reduced so that it only contains the original values.

This raises the questions:

* Are there Type-2 through -4 Unique Loops?

* Can the Unique Loop definition be extended; for example, instead of just one naked set pair (eg: the floor pair in Unique Rectangles) having extra values, perhaps more than one can in a Unique Loop?

* Is it possible to define Unique Loops where the base possibilities change around the loop?

I agree that Unique Loops are a special/rare form of forcing chains (so the answers are probably yes,no,yes) but they may be useful, in particular if something about their structure means that they can be embedded -- with more than 2 squares having extra possibilities.

I wonder if this qualifies as a unique loop:

Code: Select all
`+ - - - - - - - + - - - - - - - + - - - - - - - + |   .   .   .   |   .  12   .   |   .   .  12   |    |   .  12   .   |   .   .   .   |   .  12   .   |    |   .  12   .   |   .  12   .   |   .   .   .   |    + - - - - - - - + - - - - - - - + - - - - - - - +|   .   .   .   |   .   .   .   |   .  12  12x  |    |   .   .   .   |   .   .   .   |   .   .   .   |    |   .   .   .   |   .   .   .   |   .   .   .   |    + - - - - - - - + - - - - - - - + - - - - - - - +`

Posts: 81
Joined: 10 June 2005

When the extended forms do show up there are a lot of naked pairs with the same values that make them stand out. I've only gone through about 30 puzzles in the Very Hard/Super Hard list to find one with the extended form.

I havent seen a sample Type-4 listed so here is one I just came across that uses one:
Menneske.no Super Hard #6753298
Code: Select all
`+-------+-------+-------+| . . . | 7 . . | 8 . 6 | | . 6 8 | 3 . . | . 2 . | | 4 . 1 | 8 6 2 | . . 5 | +-------+-------+-------+| . . . | 6 7 8 | . . . | | . 4 6 | 5 2 . | 7 8 9 | | 8 . . | 4 9 . | 6 . . | +-------+-------+-------+| 6 . 4 | . . 7 | . . . | | 9 2 . | 1 . 4 | . 6 . | | . 8 . | . 5 6 | . . 4 | +-------+-------+-------+`
Also, when the Susser gets stuck, there is a short implication chain proving that R8C7<>3 which opens the whole thing up.
DanO

Posts: 40
Joined: 18 October 2005

DanO, that pattern you posted could probably be described as a hidden swordfish, restricted to the top three rows.
gaby

Posts: 15
Joined: 25 October 2005

DanO wrote:Also, when the Susser gets stuck, there is a short implication chain proving that R8C7<>3 which opens the whole thing up.

Dan, it would help when posting puzzles if you post the possibility representation so we can see what state the puzzle is in. As you are using the Susser, if you just hold down SHIFT while dragging the puzzle out of the Susser, you'll get both the simple and possibility representations.

You can also drag the possibility representations back into the Susser, btw.

As I am "logically challenged" I can't see what you're talking about. Is it a Type-4 Rectangle, a Type-4 Loop?

If you assume we are all idiots who need to be walked through things, you won't be far wrong...