The New Sudoku Players' Forum

[Moschopulus]

Here is a grid which does not contain a puzzle with 16 clues:

937856241
562194387
481273569
823647915
615932478
749581623
378469152
196725834
254318796

How do I know? By a computer calculation.
Recall that an unavoidable set is a set of cells such that the digits in the cells can be permuted to obtain another valid sudoku grid.
Any set of clues for a sudoku puzzle must include a clue from any unavoidable set.

First find the following unavoidable sets in this grid:


{17,19,77,79} (17 means row 1, column 7, etc)
{27,28,87,88}
{37,39,47,49}
{41,43,71,73}
{44,45,74,75}
{11,21,15,25}
{23,33,24,34}
{53,63,54,64}
{81,91,85,95}
{83,93,89,99}
{55,65,59,69}
{42,52,46,56,48,58}
{94,96,14,12,36,32}
{82,92,76,86,98,78}
{16,18,22,26,31,38,51,57,62,67}

Next observe that any two of these sets are disjoint (have no elements in common).
There are 15 sets, so we know already that any puzzle from this grid must have at least 15 clues.
With a friend who is a far better programmer than me, we wrote a program to find all possible choices of 16 clues with one from each of these unavoidable sets. We also included other unavoidable sets, and we ensured that the choice of clues included one from all these sets.
The result was about 1e8 possible puzzles with 16 clues.
We ran each of these through a solver written by dukuso (many thanks) and every one had multiple solutions. Total computation time: about 20 hours on 2.1 GHz.
Barring bugs, this grid has no 16.

[coloin]

Great proof

Does this grid have the maximum number of unavoidables etc ? [canonical excepted]

What would be the minimum clues for this grid ?

Is there an 18 ?

If you can find a 17 in it it will be even more significant !

["Hint" - run your program a bit longer !!!]

Colin

[dukuso]

the Moschopulos grid doesn't look very special to me

gangsters 31,15,22-32,38,31
average clues in a locally minimal sudoku: 24.49 a bit more
a random grid but much less than the evil,canonical grid with 25.72

[evert]

Found a 21:

Code: Select all

 ; ; ; ; ; ; ; ; ;
 ; ;2; ;9; ;3;8; ;
4;8; ; ; ; ;5; ; ;
 ; ; ; ; ; ; ; ; ;
 ;1; ; ; ; ;4; ; ;
7; ;9; ;8; ; ;2; ;
3; ; ;4; ; ;1; ; ;
 ; ;6;7; ; ; ;3; ;
2; ; ; ; ; ; ;9; ;


still looking for a 20

[coloin]

Good work chaps

There is little point in trying too hard here, but if it does have low[er] numbers of clues, it perhaps confirms the recent shift in opinion that 16ers do exist.

But we are no nearer to getting one.......except we would tend to give up if we thought they didnt exist.

I think this also confirms that we arnt going to get down to absolute minima without number cruching it.

Guenter has crunched it for the evil canonical grid. [19 not 18]
You have cruched it for your grid. [21 not 16]

Thats two little grains of gold.......we want to find the "humdinger" nuggett.

[evert]

Hi
My program is certainly not the most effective
Somebody should be able to find a 20 here very soon
(I stopped my computer after 4 hours but that doesn't say anything)

[gfroyle]

Here's a 19..

Code: Select all

9.. ... ...
... ... .87
4.. 2.. ...

..3 6.. ..5
..5 ... 47.
... .81 ...

... ..9 1..
..6 ... ...
... .18 .9.


What do we think the answer is (for this grid)?

Gordon

[gfroyle]

Here is another stack of 19s for Moschopulus's puzzle..

http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=6

Enjoy!

Gordon

[Moschopulus]

here is some statistics, starting from a full grid and generating 1e6
random locally minimal sudokus from it.


1) one grid from each G-class at random
2) Gordon's grid with 29 17s, used by Colin above
3) our canonical grid,(1,1,1-1,1,1)
4) random sudokus,

dukuso, can you add a 5th column for this grid alongside these four? Maybe then we can guess the answer for this grid.

[dukuso]

here the statistics from another thread together with
Moschopulos' grid:


1) one grid from each G-class at random
2) Gordon's grid with 29 17s, used by Colin above
3) our canonical grid,(1,1,1-1,1,1)
4) random sudokus,
5) Mosch.grid (only 100000 samples then multiplied by 10)

Code: Select all


clues , 1)     2)      3)      4)      5)
-------------------------------------------
17,     0       0       0       0       0
18,     0       0       0       0     0
19,     0     4.3       0       5    0
20,    59     182       0     254     40
21,  2428    6051      85    8268    1840
22, 33966   61826    1775   80869     27790
23,170727  227480   21648  273518   151580
24,342620  352289  116766  364111    329610
25,298349  248568  286836  209158    313240
26,122691   86061  329853   56006    141240
27, 25237   15908  185028    7284     30800
28,  2733    1547   50469     505    3650
29,   205      74    7040      22     200
30,   7.6     8.6     486       0      10
31,     0       0      12       0       0
32,     0       0     2.4       0       0
---------------------------------------------------
aver.24.38   24.10   25.72   23.88  24.49

 



(grr, I can't edit this as "code")



4) was generated by starting from an empty grid , adding clues
until there is a unique solution and then removing clues again.

the others were generated by starting from a full grid.
Apparantly there are differences, I don't know why.

[Wolfgang]

Id like to mention that Moschopulos' grid only contains 2628 pairs of clues that make a 3-rookery unique and only 30 of the 84 3-rookeries are unique with a 2-clue pair (the others need at least 3 clues), while for the strangely familiar grid the numbers are 5049/60.
(So it was more surprising for me that Moschopulos' grid has a 19 clue than that it doesnt have a 16 clue)

[dukuso]

Id like to mention that Moschopulos' grid only contains 2628 pairs of clues that make a 3-rookery unique and only 30 of the 84 3-rookeries are unique with a 2-clue pair (the others need at least 3 clues), while for the strangely familiar grid the numbers are 5049/60.
(So it was more surprising for me that Moschopulos' grid has a 19 clue than that it doesnt have a 16 clue)

can you explain this a bit more ?
what was a rookery, I don't remember.
19 clues sudokus - even 18-
seem _very_ likely in most grids, statistically.

[Wolfgang]

can you explain this a bit more ?
what was a rookery, I don't remember.

I introduced it there.
In a given grid a 3-rookery is defined by the cells given by 3 numbers (1,2,3 up to 7,8,9 - so there are 84 3-rookeries in a given grid). I call it unique with a 2-clue pair, if you can find 2 under the 27 cells, so that a sudoku given with all the 54 other numbers of the grid and the numbers of those 2 cells is unique.
A necessary condition that a sudoku is unique is, that all n-rookeries, 2 <=n <= 8, are unique with the given clues in the numbers of the n-rookery.
I tested some full grids of "normal" sudokus and some of the 17 clues, how many 2-clue pairs for 3-rookeries they have. There were much more (over 3000) in the 17-clues, so i assumed the more the better for low clue sudokus. This seems to be logical, because with many 2-clue pairs you have more chances to find low clues to make the 3-(or n-)rookeries unique.

[dukuso]

so, a "k-rookery" in a sudokugrid is a subset of k*9 cells which hold
only k different values. There are 9!/k!/(9-k)! k-rookeries
in each sudokugrid. We have 6^8*2 equivalence transformations
for k-rookeries (independent of k).

A "unique pair" in a k-rookery X of a sudokugrid S is a subset Y of 2 cells
of X such that the sudoku formed from the 9*k-2 cells from X-Y as holes
and all other cells as clues with entries as in S has a unique solution.

You examined some (how many ?) sudokugrids and counted the sum
over all 3-rookeries X of the number of unique pairs in X.

You found that sudokugrids formed by completing Gordon's
17-clue-sudokus have 3000 such pairs, while random sudokugrids
had less (about 2600) .



But I assume, that almost any sudokugrid admits a 17-sudoku.
Well, there could still be significantly more in those which Gordon
already found. Although the distribution of the bands in them
looked rather typical. See Moschopulos' picture here:
http://forum.enjoysudoku.com/viewtopic.php?t=605&postdays=0&postorder=asc&start=180

So, what makes a grid have many 3-unique-pairs ?
I think we'll need a verification of your observation first.

[Moschopulus]

If 2 clues from a 3-rookery together with all other cells have multiple solutions, then the other 25 cells in the 3-rookery form an unavoidable set. So finding these pairs is finding unavoidable sets. So you are claiming that the number of unavoidable sets is related to the existence of a 16, 17, 18?

The grid I posted has 15 small disjoint unavoidable sets, which helped in shortening the calculation. I don't know if this is unusual, but that seems likely. We need a way to find all unavoidable sets in a grid.