## Greatest divergance possible in dual solution puzzle?

Everything about Sudoku that doesn't fit in one of the other sections

### Greatest divergance possible in dual solution puzzle?

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.
tso

Posts: 798
Joined: 22 June 2005

### Re: Greatest divergance possible in dual solution puzzle?

tso wrote: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.
Nick70

Posts: 156
Joined: 16 June 2005

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.
Last edited by dukuso on Thu Sep 08, 2005 9:17 am, edited 2 times in total.
dukuso

Posts: 479
Joined: 25 June 2005

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
tso

Posts: 798
Joined: 22 June 2005

### re: Greatest divergance possible in dual solution puzzle?

dukuso (2005.Sep.7) wrote: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 :
Ocean (2006.Oct.1) wrote: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

Pat

Posts: 3701
Joined: 18 July 2005

### Re: re: Greatest divergance possible in dual solution puzzle

Pat wrote:
dukuso (2005.Sep.7) wrote: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.
Ocean

Posts: 442
Joined: 29 August 2005

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
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

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

Posts: 998
Joined: 21 February 2006

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)
3x Swordfish
1x Jellyfish
6x Template (Colors, Multi-Colors, Fish, etc.)
11x XY-Chain/Net

*-----------------------------------------*
| 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   |
*-----------------------------------------*
Last edited by daj95376 on Sat Nov 18, 2006 5:51 pm, edited 1 time in total.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

JPF wrote: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.|
*-----------*
Ocean

Posts: 442
Joined: 29 August 2005

Ocean wrote: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.

daj95376 wrote: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
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

JPF wrote:
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 .
Red Ed

Posts: 633
Joined: 06 June 2005

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
2010 Supporter

Posts: 1000
Joined: 16 March 2006

JPF wrote:
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
Last edited by RW on Sun Nov 19, 2006 5:59 pm, edited 2 times in total.
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

RW wrote: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 ?
ravel

Posts: 998
Joined: 21 February 2006

Next