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?

Postby tso » Tue Sep 06, 2005 8:55 pm

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?

Postby Nick70 » Wed Sep 07, 2005 12:37 pm

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

Postby dukuso » Wed Sep 07, 2005 3:39 pm

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

Postby tso » Wed Sep 07, 2005 8:04 pm

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?

Postby Pat » Tue Oct 10, 2006 8:44 am

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
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Re: re: Greatest divergance possible in dual solution puzzle

Postby Ocean » Fri Oct 13, 2006 6:36 am

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

Postby JPF » Sat Nov 18, 2006 2:22 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby ravel » Sat Nov 18, 2006 5:00 pm

I love those sudoku mysteries. Who would a have bet a cent, that this is possible?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby daj95376 » Sat Nov 18, 2006 9:11 pm

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   |
*-----------------------------------------*
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

Postby Ocean » Sat Nov 18, 2006 9:19 pm

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

Postby JPF » Sun Nov 19, 2006 3:26 am

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Sun Nov 19, 2006 3:09 pm

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

Postby RW » Sun Nov 19, 2006 6:45 pm

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

Postby RW » Sun Nov 19, 2006 7:47 pm

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

Postby ravel » Sun Nov 19, 2006 9:05 pm

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

Return to General