no-given Sudoku -- twisted idea

Bob Hanson · Posted: Wed Nov 16, 2005 5:08 pm Post subject: no-given Sudoku -- twisted idea

A colleague of mine just pointed out that the real information unit in solving Sudoku is "Candidate X is not possible in Cell A." Thus, it would be conceivable to construct a Sudoku puzzle with no givens at all. One just has to provide enough "elimination clues" in the form

r3c2 is not 6
r4c5 is not 8

Thus my questions:

1) Has anyone ever presented Sudoku puzzles that have these sorts of elimination clues instead of givens?

2) Has anyone ever presented Sudoku puzzles that have a mixture of, say 15 givens and 5 elimination clues?

3) What is the fewest number of elimination clues that are necessary to solve an NxN Sudoku? (Note that each "given" constitutes up to 28 elimination clues.)

I would think it easy to construct an "unsolvable" 16-given 9x9 Sudoku, then provide -- how many -- perhaps one? -- elimination clue that would provide just the information necessary to, say, produce a hidden ntuple and complete the puzzle. That would be considerably less information than a 17-given Sudoku. And maybe one or two choice clues with a 15-given Sudoku? ... Where does this end?

If you want to experiment with this, by the way, there is a "hidden feature" of Sudoku Assistant that if you click on the background of a cell and enter a NEGATIVE number, it removes a mark. I'm not sure any other program has this feature or how useful it is. Maybe. I suppose they all do.

Sudoku Assistant
http://www.stolaf.edu/people/hansonr/sudoku
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

dukuso · Posted: Thu Nov 17, 2005 5:37 am Post subject:

yes, I think for most solvers it makes no difference whether you have
clues or candidate-lists (=domains for the 81 variables)
The idea has been mentioned here earlier, but I didn't
yet see such puzzles presented to the public.

The question of minimum candidates necessary for a unique solution
is also interesting.. I haven't thought about it.
Maybe you should post it to the sudoku-player's forum
to the _long_ "minimum number of clues"-thread

Nick67 · Posted: Sun Nov 20, 2005 12:44 am Post subject:

Bob Hanson · Posted: Mon Nov 21, 2005 2:15 pm Post subject:

fascinating. This puzzle has, by my calculation, 239 "tidbits" of information -- "Cell [i,j] cannot be k", while a typical 17-clue Sudoku (from top95) has about 350. So from an informational perspective, there is far less here than a 17-clue Sudoku.

I wonder what the lower limit of starting information is, in "tidbits"
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

dukuso · Posted: Tue Nov 22, 2005 6:49 am Post subject:

think of the following game: player A choses a secret
sudoku-grid and player tries to find it by asking as few
questions as possible of the type: "is there a s in cell (r,c) ?"

start with the empty grid. There are 6.67e21 solutions.

Always make the binary choice which divides
the number of solutions into two halfs which are as similar
in size as possible.

There are 9 choices for cell (1,1) . So you remain with 6.67e21*8/9
solutions in worst case, which is : "no 9 in cell 1".
Contimue with chosing 8 for cell (1,1) etc.

8 bits required to determine the value for (1,1)
7 bits required to determine the value in (1,2)
....
1 bit required to determine the value in (3,2)

36 bits in total to determine the first block.

5 bits for (1,4) , 4 bits for (1,5) , 3 bits for (1,6),
5 bits for (2,4) , 4 bits for (2,5) , 3 bits for (2,6),
2 bits for (3,4) , 1 bits for (3,5)

27 bits for the 2nd block in worst case.

2 bits for (1,7) , 1 bit for (1,8)
2 bits for (2,7) , 1 bit for (2,8)
2 bits for (3,7) , 1 bit for (3,8)

9 bits for the 3rd block in worst case.

27 bits for the block 4
9 bits for block 7
27 bits for block 5
9 bits for block 6
9 bits for block 8
9 bits for block 9

-------------------------------------

162 bits as upper limit. This can likely be reduced by looking
at what possibilities might be left for B5689, once B12347 are
filled etc.
The strategy can be used independently on the answers of player A.

Giving one clue is the same as 8 bits = 8 questions for that cell.
17 clues = 8*17 = 136 bits to determine the grid.

If each question divides the number of remaining solution-grids by
two then we need 73 questions.

So there could be configurations with 100 given bits and unique solution

There are 16-clue-puzzles with 2 solutions, so the
current record is 129 bits.

That is 129 rows removed from the 729 rows in the exact-cover-matrix
then there is a unique subset of 81 disjoint rows
taken from the remaining 600 rows.

I tried to generate some minimal no-givens-sudokus and they had
230 candidate-negative-marks in average, minimum 208,maximum 251.
So chosing clues=givens is already a relatively effective
method to determine the grid.

-Guenter

here is the one with 208 forbiddens:

edit: puzzles removed. They are way too hard for human solvers,
about 1000 times harder than random normal minimal sudokus !
I didn't expect that sudoku-like 9*9-puzzles could be that hard.

So I just give some puzzles in short computer readable format:
100011101111010100000001000110010011100100100100010000000000100110000011000100001000000000100011111110001000100101110011001110100000000000010100000000000010100010000011101000000100100010000100110101000001001001110100000000000100001001000000010110011001010000001110001010101001011111001111111000000000000000100000000000000000000001000010000100000110000000001101000001001100101100101011101100000000000100000110100000110000000001000000100101000001000001001010001111111101000101000000001000000010010000000010100110000000000010001110011001000010000000000100001010011100000100010101000000110011000111001001011010100010000110111011011100111001100000001000101000100001010101101111001000100001100011001001011010000010000000001000010001000
nodes:154608 forbiddens:230
101001000000001001101011000111010010100000011111011011000000000101000000000000010000000010011000001101011000100100110000100111001000000000001110011000100001000000101001100100000000000000000010000010000000000101011010000110010010100100010011100110001110000110001000100000111000010000010001000000001001010000010001000110011001000101000001000010000100110101000100000000011011000000001101010010000001000000000100101110111100011100111110010001000110100000111101011110000011010000100001011001000000000000010001000101000000100000000010010101010001001000110000000101000011001100000000000001111100001100000000010001000010010000000100110011111000101000000110001001000000010001100100000110110000000101101111001001100100111000000000011101101
nodes:226933 forbiddens:230
100000110000100000000000100000011010001010000001000000000000100000000010000011010100101100111101110011100100000110011011110100011100000000000000101000000000111100100000000000000111100100000010001011101000010100000100111000101110000011000010100011000101000100000000100000101100011101100111001000000001000111000000001000001111001011100001000000110000000000000000101101000000100101110001001100000100110011011000000000010000000010011011100001011001000110010000100001000000001000010000000000010011110000000010000001000000000100000010100110011000001001100001101000000101011100000010011100000010000110000000000100001110100010101101001000100001000000101010111000110000000000110000001000100011100000100000000110111101111000000000001101100
nodes:204785 forbiddens:221
000001100000000100110000000000111010011000010010010100000000000010001110111111110101011000000010101100000110110110001100000110100010000001100010101101100010010100101100000000000000000100000100011001000100000010010010010000010100011100010001000110110001001001100000010100111111001000001010100000000100011100010000000000010010111000000101011011000010000000000000000100010111100000001010000000100110001000000111000100000100001110010100000000011110101100001101100011011001010010000001010000001000000011000011000000110001111010000000010000100110100010001101111110001101110110001000000011001010100010000111101010101000010100011110111001100000000000001000000000010000001011011100010001000000000100010000100110001000000010100000000110010
nodes:150874 forbiddens:237
001100101101011011000000010010000010001011001000100000010100000000001000000001111011100010101011010101000010000000001000001000101111011001001000100000000110111010011001100101010000010011010000001100010100000100000000000010110010101000010000010011011001100001001000101001100111111000001100000100010000101001001111100100000011111101000011000000010001000010000000010000011000010000000000000011110100010100010001000001000001000010100000001101011000000111001001010000010000010100010000101111001100000000000000000110100001001000000010000100011000000000101000010000000000000111100001000100000010111011000000000001101100000010010000010000000100000110000011000000000000010000000100010100000000100011010000110000110010001100010100100000010
nodes:70821 forbiddens:216
001100000000000000100100001000010000000110010110000000001011000000010100000010001101000000011110000001100000010001000000000000101000110000001110100100111001000101111000000111110011000000100010010101001010110111010111000001100000000000100000110111000101000000010000100111010000000010000100110100110010001100000100000000000110000001100010010000000000011110010111001010000010010001010000000000001000110010000111001111010000001000000000011000000001100100001000000001101001000001000010000001001100001010100000000100100101000000001111000000010011000100000010100100000101001100001010100101110100100000100000100000001100100001111000001000000100011100101110010000100110001000101101011000000000100000010110000010000111011100001010110000101
nodes:140233 forbiddens:221
100000000000100100011110100100001000010101001011010000100011101111100000101110010000100100001100111000101100000000000100001110001110101001001101010110101100100111000101000100000010000010100100001001010011001100100010101000000110000100000111101110111011000011011000000010100001001000000000000110011101001011001010010100100000010010000100000000010000000101010001000001000110100000100010010001010010000010001000001101010101000000000000011010011010101100100000000000000110100111001001000000000001000101010000001010100000000001010001010000100000000101101001000000000010001111100010000000001111010000100001001011111000000000000001000000000010000000110000100011010111010011101001111000110010000000110100110011100000100000001100100101000
nodes:113986 forbiddens:237
011000010000100000011100001101111100001000110010000000111001000000000100000000000000010000010000100000000000100000000000000110010000000001100000000110000010010000000000000100000011100101001001000001000000101000011010101111001000001110111010011000011101000010001100000001000001101001000100010011111110001101001000110011000111100110000000010000000000000100000110000000010001000000101101000001000000100000001001010000001010000011110011110001101010010011010000000100000000000000000011110001100001000000000010100001101100010100100000100000010000001011000101111101010010010000000110000011010110001011100000000100100111100010000110010000001010111011000000100011000101000011011100001100000010110110010010001001011010000000100010111010101
nodes:87241 forbiddens:225
011010011001010010011000101000100000000000000111110011001000000001000000000000000001001100001110110001000000001100100001101101000000000011011100001001100100001000011100010000000000000010000010100010000110010000100010010001100100111110100000100000001001010000000010000100001001000000000000110101100010011001000001000010100000000001000001000010010000101101000100010010010101000110101111001000000000000000000000100010000100110010000100010111000010100000111000000000010000000101000100100101000000100000000000011010101000000101100010101001010100000000000100000100110000000010001110000101010111100000000000000000000110010010000011111010000100110000000000010001100001100010000100101100000000000010001000000011101100011101110010000100101
nodes:84146 forbiddens:207

Pat