Three nearly identical puzzles

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

Three nearly identical puzzles

Postby tso » Thu Jun 15, 2006 12:23 pm

These three puzzles are identical except for the two givens in the center box, yet they each have a unique solution and have wildly different difficulty.

Easy:
Code: Select all
+-------+-------+-------+
| . . . | . . 3 | . 9 . |
| 3 . . | . . . | . . 1 |
| . 6 1 | 9 . 8 | 2 . . |
+-------+-------+-------+
| . . 8 | . . . | . . . |
| . . . | 7 . 1 | . . . |
| 5 . 9 | . . . | 4 . . |
+-------+-------+-------+
| . . 7 | 3 . . | 5 2 . |
| 2 . . | . . 6 | . . 4 |
| . 3 . | . . . | . . . |
+-------+-------+-------+


A little harder:
Code: Select all
+-------+-------+-------+
| . . . | . . 3 | . 9 . |
| 3 . . | . . . | . . 1 |
| . 6 1 | 9 . 8 | 2 . . |
+-------+-------+-------+
| . . 8 | . . . | . . . |
| . . . | 1 . 7 | . . . |
| 5 . 9 | . . . | 4 . . |
+-------+-------+-------+
| . . 7 | 3 . . | 5 2 . |
| 2 . . | . . 6 | . . 4 |
| . 3 . | . . . | . . . |
+-------+-------+-------+



A lot harder:
Code: Select all
+-------+-------+-------+
| . . . | . . 3 | . 9 . |
| 3 . . | . . . | . . 1 |
| . 6 1 | 9 . 8 | 2 . . |
+-------+-------+-------+
| . . 8 | . . . | . . . |
| . . . | 2 . 1 | . . . |
| 5 . 9 | . . . | 4 . . |
+-------+-------+-------+
| . . 7 | 3 . . | 5 2 . |
| 2 . . | . . 6 | . . 4 |
| . 3 . | . . . | . . . |
+-------+-------+-------+



What is the maximum number of valid Sudokus that can be made in this mold -- identical placement of givens, all but two givens identical in all puzzles?
tso
 
Posts: 798
Joined: 22 June 2005

Postby JPF » Fri Jun 16, 2006 10:46 pm

tso wrote:What is the maximum number of valid Sudokus that can be made in this mold -- identical placement of givens, all but two givens identical in all puzzles?

Let's start with a much easier question :
What is the maximum number (p) of valid Sudokus that can be made with all but one given identical in all puzzles ?

By "randomly" generating a small sample of 1000 minimal puzzles, I got the following distribution for p :
Code: Select all
p   

4     5.5 %
3    33.3
2    57.9           
1     3.3
     ----
    100.0 %


p=1 means that it's impossible to change the digit in any cell of the puzzle.
It seems to be the less probable case.

Here's an example of 4 valid puzzles, different by only the digit in a given cell.

Code: Select all
[1,2,6,9 are valid digits in R9C3]

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


and some more (p=4) :
Code: Select all
020600010000800003000730500015000230403000608600070000007210000000000000081000050
020600010000800003000730500015000230403000608600070000007240000000000000081000050
020600010000800003000730500015000230403000608600070000007250000000000000081000050
020600010000800003000730500015000230403000608600070000007290000000000000081000050

200000000040070020006054007020006005400009800000020000073010500900300100100500060
200000000040070020006054007020006005400009800000020000073010500900300100100500070
200000000040070020006054007020006005400009800000020000073010500900300100100500080
200000000040070020006054007020006005400009800000020000073010500900300100100500090

200000450805000700007010008000900000406000100090800006500090070000063000080007020
200000450805000700007020008000900000406000100090800006500090070000063000080007020
200000450805000700007040008000900000406000100090800006500090070000063000080007020
200000450805000700007050008000900000406000100090800006500090070000063000080007020

040090023005130090060000080000010000102083009080200000000500007706020000010060000
040090023005130090060000080000010000102083009080600000000500007706020000010060000
040090023005130090060000080000010000102083009080700000000500007706020000010060000
040090023005130090060000080000010000102083009080900000000500007706020000010060000

000001200047089000230500090002046000000000010070000004020000300090000170000803650
000001200047089000230500090003046000000000010070000004020000300090000170000803650
000001200047089000230500090005046000000000010070000004020000300090000170000803650
000001200047089000230500090009046000000000010070000004020000300090000170000803650

038020000001000800620050090080060007006900400090004008000080500050007100000300020
038020000004000800620050090080060007006900400090004008000080500050007100000300020
038020000005000800620050090080060007006900400090004008000080500050007100000300020
038020000009000800620050090080060007006900400090004008000080500050007100000300020

005000400042000008000100053708000090014030000030700600000080940000020000061040800
005000400043000008000100053708000090014030000030700600000080940000020000061040800
005000400046000008000100053708000090014030000030700600000080940000020000061040800
005000400047000008000100053708000090014030000030700600000080940000020000061040800

803070500000000900270085000004300209000020000600007000008000010030090450060400300
803070500000000900270085000004300209000020000600007000008000020030090450060400300
803070500000000900270085000004300209000020000600007000008000060030090450060400300
803070500000000900270085000004300209000020000600007000008000070030090450060400300

and some "untouchables" (p=1)
Code: Select all
010400800206000000800050009000003210020010000000007600000340060000080000000670031
002800004300000000000600700000004806009010020001082005000500908508291000000000000
501790002207040000080030000040003690010020500000800007100980200000002070000000006
030000204028000000400000700370002006201070000006500070000806045600920000000000000
000000000008000060005026740060305000000000002591062000900007300700850000000600800
000000901700028060000005000600004090004000006083006007210000000059000410040000002
040006010073004600008000000004200903700000400036000000000000009209000000010035200

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby tso » Sat Jun 17, 2006 3:21 am

Cool. They're especially interesting when changing a single clue leads to a solution grid with the greatest divergence and/or the puzzle's subjective difficulty changes the most.

I suppose that's another challenge question -- what is the greatest number of digits that can differ in the solution grids of two sudokus that differ only by the value of a single clue? (65 would be the upper limit.)

This is similar to a question I posed some time ago here.
tso
 
Posts: 798
Joined: 22 June 2005

Postby JPF » Tue Jun 20, 2006 5:00 pm

Here are 5 valid puzzles, only different by the digit in a given cell.
Code: Select all
[1,2,3,7,9 are valid digits in r5c6]

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


Unfortunately, all of them are very easy (7 to 9-steppers).
only r5c6 = 7 or 9 make the puzzle minimal.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby tso » Tue Jun 20, 2006 9:28 pm

Interesting puzzle nonetheless. Actually, if r5c6 is simply left empty, the puzzle has exactly 5 solutions, one for each of the 5 possibilities left for that cell. All but 17 cells can be solved without filling this cell -- which partially explains why they all have similar difficulty. A puzzle with only 16 unsolved cells has a much lower limit for complexity of the solution.
tso
 
Posts: 798
Joined: 22 June 2005

Postby JPF » Tue Jun 20, 2006 11:30 pm

tso wrote:Interesting puzzle nonetheless. Actually, if r5c6 is simply left empty, the puzzle has exactly 5 solutions, one for each of the 5 possibilities left for that cell. All but 17 cells can be solved without filling this cell –

actually, only 15 cells are unknown :
Code: Select all
 8 1 2 | 5 4 6 | 3 7 9
 4 5 7 | . 9 . | 2 6 8
 6 9 3 | 7 2 8 | 4 1 5
-------+-------+-------
 5 7 6 | 4 8 . | 9 . 1
 . . 4 | . . . | 8 5 6
 . . 8 | 6 5 . | 7 . 4
-------+-------+-------
 2 4 5 | 8 . . | 6 9 3
 3 8 9 | 2 6 5 | 1 4 7
 7 6 1 | 9 3 4 | 5 8 2

in all the cases, r5c8=r6c5=5

Anyway, I found a better example :

Code: Select all
[3,4,5,8,9 are valid digits in A = r4c9]

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


A = 8 or 9 : singles (9 & 10 steppers)
A = 4 or 5 : need XY-Wing
A = 3 seems a bit more difficult.

If A is left empty, 5 solutions and 34 cells are unknown.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

all-but-one-given identical

Postby Pat » Tue Nov 28, 2006 5:06 pm

JPF (2006.Jun.16) wrote:What is the maximum number of valid SuDokus that can be made with all but one given identical in all puzzles ?


5 — two examples posted above, two in another Topic
    i should mention that some additional examples have been shown for a 5-mutable clue, but they lack one other property which i desire — when the cell is left empty (one less clue), the puzzle has more than 5 answers.

6
Ocean (2006.Nov.18) wrote:
Code: Select all
 . . 1 | . . 2 | . . .
 . 3 . | . 4 . | . . .
 5 . . | 6 . . | 7 . .
-------+-------+------
 . . 7 | . . . | . . 1
 . 8 . | . . . | . _ .
 2 . . | . . . | 6 . .
-------+-------+------
 . . 9 | . . 3 | . . 5
 . 4 . | . 2 . | . 8 .
 6 . . | 7 . . | 2 . .



gsf (2006.Dec.20) wrote:
Code: Select all
 . . . | . . 8 | 5 . 2
 . 2 3 | 5 9 1 | . . 8
 . . 1 | . 7 4 | 9 . .
-------+-------+------
 . . . | . . . | 6 . 1
 9 . 8 | . _ . | 7 . .
 2 . . | . . 7 | . 3 .
-------+-------+------
 . 6 7 | . . 3 | . . .
 8 . . | 4 . . | . . 7
 . 9 . | . 8 2 | . 4 .



7

Red Ed (2006.Nov.28) wrote:
Code: Select all
 . . . | . 8 5 | . 9 .
 7 . . | . 9 3 | 4 . .
 . 6 9 | 7 2 4 | 1 . .
-------+-------+------
 . . 3 | 4 6 8 | . . 9
 . 8 . | 5 1 . | 3 . 6
 5 . 6 | . . . | . . .
-------+-------+------
 6 . 1 | . . . | 9 . .
 . . . | . . . | . _ .
 . 2 . | 9 . . | 8 . .



Code: Select all
 . . 7 | . 8 3 | 5 . .
 2 5 . | 1 . . | . . 4
 3 . 9 | 4 . . | 1 . .
-------+-------+------
 8 . . | . . . | 7 4 3
 . . . | . 5 7 | . 8 .
 7 . . | . . . | . . .
-------+-------+------
 . . . | . . . | 9 . 6
 . . . | 3 . 1 | . 2 .
 . _ . | 7 . . | . . .



gsf (2006.Dec.6) wrote:
Code: Select all
 . 2 . | 4 . . | . . .
 4 . . | . . . | . 3 7
 . 8 . | . . . | 1 . 5
-------+-------+------
 . . 1 | . . 5 | 3 . 8
 . . _ | 9 . . | . . .
 . . . | 7 . 1 | . 6 4
-------+-------+------
 . . . | 5 . 6 | 8 . .
 5 . . | . 9 . | . . .
 . 7 . | 2 . 3 | . . .




8

Red Ed (2006.Nov.30) wrote:
Code: Select all
 1 2 . | 3 4 . | 5 6 .
 5 3 . | 6 . . | . . .
 4 . . | . 5 . | 7 2 3
-------+-------+------
 2 . 1 | . 3 . | 8 . .
 7 4 . | 2 . . | . . .
 . 8 . | 7 . . | 6 . 2
-------+-------+------
 . . 2 | 9 . . | . 8 .
 . 7 . | . . . | 2 1 5
 . . . | . . _ | 9 . .





~ Pat
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005


Return to General