The New Sudoku Players' Forum

[Ruud]

I have a very strange idea.

When I solve a puzzle using a Unique Rectangle, and that puzzle happens to have multiple solutions because of that unique rectangle, it is unavoidable (pun intended) that a conflict arises in the subsequent solving path. The remainder of the puzzle has to find a place for a digit that would otherwise be part of the UR. In exchange, a digit has been used in the UR that will surely leave some holes outside the UR.

What I'm aiming at is that being able to find a solution using a UR proves that there is a unique solution, otherwise it would be impossible to completely solve the puzzle.

I have 3 questions

1. Is it possible to irrefutably prove that using a 'wrong' UR will always cause an error?
2. If so, wouldn't this effectively 'legalize' UR techniques?
3. Can we extrapolate this to other uniqueness-based techniques?

Ruud

[RW]

1. Is it possible to irrefutably prove that using a 'wrong' UR will always cause an error?

No, an UR always removes an even amount of solutions. If the puzzle happens to have 3 or more solutions, then you might still find one of them using the UR. I've posted an example of such a puzzle here.

RW

[Ruud]

Thanks RW,

that blew a hole the size of the Grand Canyon in my theory.

Would it be possible to detect isolated UR's for which we can still apply this theory?

For example:

Code: Select all

.------------.------------.------------.
| 2   6   4  | 9   7   3  | 1   5   8  |
| 7   8   3  | 6   5   1  | 29  24  49 |
| 1   5   9  | 8   2   4  | 36  36  7  |
:------------+------------+------------:
| 9   7   6  | 5   1   2  | 8   34  34 |
| 8   4   1  | 3   9   67 | 5   67  2  |
| 3   2   5  | 4   8   67 | 69  167 19 |
:------------+------------+------------:
| 6   3   2  | 1   4   8  | 7   9   5  |
| 5   1   7  | 2   3   9  | 4   8   6  |
| 4   9   8  | 7   6   5  | 23  123 13 |
'------------'------------'------------'

Besides the UR in r56c68 there does not seem to be any other possible deadly pattern.

Ruud

[Myth Jellies]

The BUG+2 is also deadly pattern. The +2 has to be 3 or 6 which forms a naked pair with the other 36 in the column.

[ronk]

The BUG+2 is also deadly pattern. The +2 has to be 3 or 6 which forms a naked pair with the other 36 in the column.

In the context of Ruud's question, wouldn't the concept of minimal unavoidable set (or minimal uniqueness pattern) be appropriate?

[Myth Jellies]

The BUG+2 is also deadly pattern. The +2 has to be 3 or 6 which forms a naked pair with the other 36 in the column.

In the context of Ruud's question, wouldn't the concept of minimal unavoidable set (or minimal uniqueness pattern) be appropriate?

Probably true, though a BUG-lite should qualify as an unavoidable set. I was sort of thinking aloud here. A related topic might be something like the number of naked sets versus the number of unsolved groups in the underlying BUG grid. Likely nothing there though.

[Ruud]

I'm still brainstorming on this subject...

It is now clear that avoiding a pattern that would cause 2 or more solutions does not guarantee that there is a unique solution.

The BUG seems to be more promising.

A BUG can either have 0 or 2 solutions. If it would have 0 solutions, a move that avoids the BUG would not bring us to a solution that wasn't there in the first place. If it would have 2 solutions, a move that avoids it would block the path to either one of them, so we cannot solve the puzzle completely.

Therefore, a move that avoids a "real" BUG would not allow us to complete the puzzle. Being able to solve a puzzle with a BUG move therefore proves that there is only one solution.

This could als work for UR's that cannot be intertwined with other deadly patterns, but that requires more research into the properties of intertwining unavoidable sets.

Ruud

[RW]

The BUG seems to be more promising ... A BUG can either have 0 or 2 solutions.

I'm sorry to spoil your theories again, but here's a BUG with 3 solutions:

Code: Select all

 *--------------------------------------------------*
 | 9    4    6    | 7    3    2    | 5    1    8    |
 | 7    8    5    | 6    1    4    | 2    9    3    |
 | 3    12   12   | 5    8    9    | 6    4    7    |
 |----------------+----------------+----------------|
 | 5    6    7    | 2    9    8    | 4    3    1    |
 | 8    12   23+1 | 13   4    7    | 9    5    6    |
 | 4    9    13   | 13   5    6    | 8    7    2    |
 |----------------+----------------+----------------|
 | 6    5    8    | 4    7    3    | 1    2    9    |
 | 1    3    9    | 8    2    5    | 7    6    4    |
 | 2    7    4    | 9    6    1    | 3    8    5    |
 *--------------------------------------------------*

Again, setting r5c3=1 avoids 2 of the solutions to reach the third. Of course, in this case you can use both the URs to prove that the puzzle has multiple solutions, but this is probably not the case with all BUG-patterns with more than 2 solutions.

These are things that are worth thinking of, but I don't feel very optimistic about the chances to recognize isolated unavoidable sets, without knowing the solution...

RW

[Ruud]

RW, both your examples show intertwined UR's.

I'm not giving up yet, although I agree with you that the chances are slim to "validate" each uniqueness-based move.

What we need is a definition of an irreducable BUG, which cannot be broken into smaller parts.

This may be an example:

Code: Select all

.-------------.------------.------------.
| 2   1   6  | 5    3   4  | 8   7   9  |
| 8   39  5  | 69   7   2  | 1   4   36 |
| 7   39  4  | 8    1   69 | 36  2   5  |
:------------+-------------+------------:
| 9   4   2  | 1    6   5  | 7   3   8  |
| 5   6   8  | 7    4   3  | 2   9   1  |
| 3   7   1  | 2    9   8  | 5   6   4  |
:------------+-------------+------------:
| 6   5   3  | 4    8   7  | 9   1   2  |
| 4   8   9  | 36   2   1  | 36  5   7  |
| 1   2   7  | 39+6 5   69 | 4   8   36 |
'------------'-------------'------------'

As far as I can see, there are no fragments of this BUG that can be isolated, which means that it must have 0 or 2 solutions.

Here is another one:

Code: Select all

.------------.------------.-------------.
| 1   5   6  | 2   9   4  | 38   78  37 |
| 4   8   9  | 1   7   3  | 2    6   5  |
| 7   3   2  | 5   6   8  | 1    4   9  |
:------------+------------+-------------:
| 9   2   7  | 3   4   1  | 6    5   8  |
| 5   1   8  | 9   2   6  | 7    3   4  |
| 3   6   4  | 7   8   5  | 9    2   1  |
:------------+------------+-------------:
| 2   47  5  | 8   13  9  | 34   17  6  |
| 8   47  1  | 6   35  2  | 45+3 9   37 |
| 6   9   3  | 4   15  7  | 58   18  2  |
'------------'------------'-------------'

And even this BUG, the biggest in my collection, seems irreducable:

Code: Select all

.------------.-------------.------------.
| 68  68  1  | 7   2   3   | 9   5   4  |
| 9   2   7  | 5   8   4   | 36  16  13 |
| 4   3   5  | 6   19  19  | 2   7   8  |
:------------+-------------+------------:
| 7   5   3  | 4   6   8   | 1   9   2  |
| 68  1   68 | 29  79  27+9| 4   3   5  |
| 2   9   4  | 3   15  15  | 7   8   6  |
:------------+-------------+------------:
| 1   7   68 | 28  35  25  | 36  4   9  |
| 5   4   9  | 1   37  6   | 8   2   37 |
| 3   68  2  | 89  4   79  | 5   16  17 |
'------------'-------------'------------'

Ruud

[RW]

And even this BUG, the biggest in my collection, seems irreducable:

I would dare to say that every BUG+1 in a puzzle with an unique solution is irreducable. The logic is simple, you have 2 candidates in all cells but 1, and 2 appearances of each candidate in all units, except in one unit of each type. If you could isolate a smaller part of this set to a smaller BUG-lite with the same properties, that would leave a set of cells with 2 candidates in each cell and all candidates appear twice in all units - BUG:

Code: Select all

.-------------.------------.------------.
| 2   1   6  | 5   #34 #34 | 8   7   9  |
| 8  *39  5  |*69   7   2  | 1   4  *36 |
| 7  *39  4  | 8    1  *69 |*36  2   5  |
:------------+-------------+------------:
| 9   4   2  | 1    6   5  | 7   3   8  |
| 5   6   8  | 7   #34 #34 | 2   9   1  |
| 3   7   1  | 2    9   8  | 5   6   4  |
:------------+-------------+------------:
| 6   5   3  | 4    8   7  | 9   1   2  |
| 4   8   9  |*36   2   1  |*36  5   7  |
| 1   2   7  |*39+6 5  *69 | 4   8  *36 |
'------------'-------------'------------'

Either that, or there will be 2 intertwined deadly patterns, connecting at the +1 cell, which would thus eliminate all candidates from the +1 cell like in the example I posted.

But yes, if you can prove that your BUG is irreducable, then you can safely make the BUG+1 elimination without assuming an unique solution. In the case of a BUG+1, it's not even so hard to check that the pattern is irreducable.

RW