The New Sudoku Players' Forum

[tso]

Suppose Sudoku is created that has exactly two solutions. What is the greatest number of cells that can differ between the two answers?

On the same subject, here's a ridiculously hard *optimizer-type* puzzle idea suitable only for puzzle competitions:

Code: Select all

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

This puzzle has nearly 1000 solutions. Find two with the greatest number of cells that differ.

[Nick70]

Suppose Sudoku is created that has exactly two solutions. What is the greatest number of cells that can differ between the two answers?

18 is a lower bound. This would be for a sudoku only using 7 digits in the initial clues, so that the remaining two can be exchanged.

[dukuso]

here is one with 48 :

Code: Select all

1.....58.
8....1..6
.6..2....
...59....
....7....
.93..2...
.1....8.4
...9.7.5.
6..2..71.


[tso]

That's impressive -- over half the cells in the answers are different.


Clues given: 24
Cells that differ in two solutions: 44
Cells that are the same: 13

[Pat]

here is one with 48 :

Code: Select all

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

Ocean has now done better - 55 :

Here is the "ambiguity that involves 9 digits and 55 cells":

- - - -pseudo-puzzle and its 2 answers:

Code: Select all

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


817596234923471685465283719751829463289634571346715928692358147578142396134967852
914568273563279184827431659759123468238746591146895732682317945495682317371954826


[Ocean]

here is one with 48 :

...
Ocean has now done better - 55 :

Thanks Pat for showing this perspective. I didn't do much though. Red Ed found the size 55 unavoidable set, which was the hard part that deserves credit. I only wrote down the related pseudo-puzzle and the two solution grids, which was rather straightforward.

[JPF]

Here is a pseudo-puzzle (2 solutions)

The two solutions differ in 58 cells.

Code: Select all

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


197835264638247519425916387519364728742189653386572941261798435874653192953421876
164573289932148675785926143829315764341687952576492831253769418618254397497831526


Clues given : 21
Cells that differ in two solutions : 58
Cells that are the same : 2

JPF

[ravel]

I love those sudoku mysteries. Who would a have bet a cent, that this is possible?

[daj95376]

JPF, very interesting. Reducing it to bivalue cells was a challenge. Did you consider this variant?

Code: Select all

Clues given:                        23
Cells that are the same:             0
Cells that differ in two solutions: 58

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


Code: Select all

 4x Naked Pair
 9x Naked Triple
 6x Locked Candidate (1)
 1x Locked Candidate (2)
 5x Naked Quad
 3x Swordfish
 1x Jellyfish
 6x Template (Colors, Multi-Colors, Fish, etc.)
11x XY-Chain/Net
 5x Contradiction Chain/Net (simple)

*-----------------------------------------*
| 1   69  47  | 58  37  35  | 2   68  49  |
| 69  3   28  | 12  4   78  | 56  17  59  |
| 47  28  5   | 9   12  6   | 13  48  37  |
|-------------+-------------+-------------|
| 58  12  9   | 3   16  45  | 7   26  48  |
| 37  4   12  | 16  8   79  | 69  5   23  |
| 35  78  6   | 45  79  2   | 89  34  1   |
|-------------+-------------+-------------|
| 2   56  13  | 7   69  89  | 4   13  58  |
| 68  17  48  | 26  5   34  | 13  9   27  |
| 49  59  37  | 48  23  1   | 58  27  6   |
*-----------------------------------------*


[Ocean]

Here is a pseudo-puzzle (2 solutions)

The two solutions differ in 58 cells.

Code: Select all

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


197835264638247519425916387519364728742189653386572941261798435874653192953421876
164573289932148675785926143829315764341687952576492831253769418618254397497831526


Nice improvement. An unavoidable set of size 58! The set has a diagonal reflectional symmetry pattern, and is a reflection of its own twin set. Remarkable!

Code: Select all

# The two twin unavodable sets of size 58:
 *-----------*
 |.97|835|.64|
 |6.8|2.7|519|
 |42.|.1.|387|
 |---+---+---|
 |51.|.64|.28|
 |7.2|1.9|6.3|
 |38.|57.|94.|
 |---+---+---|
 |.61|.98|.35|
 |874|6.3|1.2|
 |953|42.|87.|
 *-----------*

 *-----------*
 |.64|573|.89|
 |9.2|1.8|675|
 |78.|.2.|143|
 |---+---+---|
 |82.|.15|.64|
 |3.1|6.7|9.2|
 |57.|49.|83.|
 |---+---+---|
 |.53|.69|.18|
 |618|2.4|3.7|
 |497|83.|52.|
 *-----------*

[JPF]

Nice improvement. An unavoidable set of size 58! The set has a diagonal reflectional symmetry pattern, and is a reflection of its own twin set. Remarkable!

Thanks.
I've the feeling that we can do better on the same theme.

JPF, very interesting. Reducing it to bivalue cells was a challenge. Did you consider this variant?

Thanks for the analysis.
The variant is a bit easier to solve as r4c3 = r3c4 = 9 needs more than SST...

Here is a case without common cells though :

Code: Select all

Clues given:                        23
Cells that are the same:             0
Cells that differ in two solutions: 58


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


168247395943851672572936841231485769857629413496173528389762154625314987714598236
195284367647359821832176954289461735453827619716593248368745192974612583521938476



JPF

[Red Ed]

Code: Select all

Clues given:                        23
Cells that are the same:             0
Cells that differ in two solutions: 58

Very impressive. So, we can create minimal unavoidables of size up to about 70% of the full grid. It's probably only a coincidence, but the same(ish) density is also possible in grids with region size 2x2 (max min = 12, essentially only one way) and 3x2 (max min = 26, lots of different ways).

An example of a size 26 minimal unavoidable in a 3x2 grid is shown below.

Code: Select all

. . | . 1 | 2 3            . . | . 3 | 1 2
. 1 | 4 . | . 5            . 5 | 1 . | . 4
5 2 | 3 6 | 1 4            2 1 | 6 4 | 5 3
----+-----+----    <==>    ----+-----+----
. 5 | 6 4 | . 2            . 2 | 4 5 | . 6
2 3 | 1 5 | 4 6            4 6 | 3 1 | 2 5
4 6 | . 3 | 5 .            5 3 | . 6 | 4 .

[RW]

Very nice unavoidable set! I would have imagined that a minimal set of this size would come from 2 grids with exceptionally few small unavoidables, but this is not the case. Unavoid finds 311 sets upto size 14, which is more than the average grid. The grids also have 58 2-digit unavoidables, which is a bit over average... Does this imply that a) there might be even larger minimal unavoidables in grids with better characteristics? or b) the average grid has minimal unavoidables of size 55+?

RW

[RW]

Code: Select all

Here is a pseudo-puzzle (2 solutions)

The two solutions differ in 58 cells.
...
197835264638247519425916387519364728742189653386572941261798435874653192953421876
164573289932148675785926143829315764341687952576492831253769418618254397497831526

After canonicalization:

Code: Select all

123457689456189327789263145234978516568341792917625834372514968695832471841796253
123457689456189327789263145234978516568341792917625834372514968695832471841796253

Both grids are the same... very interesting indeed!

RW

[ravel]

Both grids are the same...

Wow, like for Gordons famous 16 clue with 2 solutions [where it is obvious]. Does this hold for each [minimal] sudoku with 2 solutions, that have no common cells beside of the givens ?