The New Sudoku Players' Forum

[coloin]

Thankyou for the update and contributions.

Mosch - I think the various ways one can portray essentially similar grids is confusing.....there are 29 17s in this grid...it is a representation of the SF grid...see page 19 of the minimum clues thread.

As to the likelihood of a 16.......well I hate to agree that it is unlikely but it is looking that way.....it depends really on how Gordon's program searched the space.

The number of 17s in a 16 [if there was one] would indeed be 65 non-minimal plus there would also be a few minimal ones.......so thats a few more reasons to have found the grid - if it was there.

We would indeed like to know what proportion of randomly produced 17grids are in Gordon's list. A problem exists however that although Gordon can find 17s - it is very difficult to get a 17 from a grid even from one which we know has at least one in it.

Wolfgang has a program which analyses a grid and the rookeries......possibly similar to the suexsf program from dukuso.

Take the following four grids

Code: Select all

grid                 SF         SFB         Random 17 [number 1122]   Random
suexsf value        24.10       24.02           24.17                 24.42
number of 17s       29           3               1                     0
number of 18s*     2076 [71]   240  [80]        89  [89]               1 [estimate]
number of 19s*    75211      10089            4182                    80 [estimate]

where * is the number of puzzles generated using a "backbone" of the grid - there may well be many more 18s & 19s.



The suexsf value - indicates suitable grids that might have a 17 - but is fairly non specific.

The suexsf program from dukuso is a program which calculates the occurance rate of clues in a large number of minimal sudoku puzzles - all generated from one particular valid grid. It can be used to pinpoint the backbone of 14 clues in the SF.....I will provide more details if anyone is interested.

Here is the backbone of the SF [Strangely Familiar grid - 29 sudoku puzzle grids]

Code: Select all

+---+---+---+
|...|.4.|7..|
|.8.|...|...|
|.1.|...|...|
+---+---+---+
|...|8..|..6|
|7..|...|...|
|4..|...|2..|
+---+---+---+
|3..|.7.|...|
|...|...|...|
|...|..6|.18|   14 clues - 29 different ways to add 3 more clues.
+---+---+---+


and here is the output at clue 14

Code: Select all


  58    0  265  290 1694    0 1689    0  154
 285 1694    0    7   86  190    0  246  186
 240 1694  774  222    0    0  175  319   51
   0   91  105 1694  110   54  107   63 1674
1694    0   97  219  201  197    0  134   36
1694  138   20   85  112  162 1671  206  236
1691   45  427  216 1694    0  201  206  265
   0  114  222  215  207  197   77  242  385
   0    0  182  103  212 1670   46 1693 1694

these are the counts of clues in 17,18,19,20,21,22 minimal sudoku puzzles generated at random from the SF grid. The "best" clues are fixed at each step.


But it has not been perfected [or automised or fast] to reliably get 17s from a grid containing a 17.
I would be interested to see how others determine 17s from a grid and maybe we can answer Gordons's question.

C

[udosuk]

Thanks Gfroyle for the list!

Even if there could be no 16-clue valid puzzle, it might be worthwhile to shift the focus to find any more 16-clue "2-solution" puzzles. And it would be very nice to prove that the only one we got so far is the UNIQUE one!

[gfroyle]

Here are the pseudo-Sudokus with low numbers of completions... the file name indicates how many completions (ie xall16-002 lists all the ones I know with 16 clues and 2 completions).

Code: Select all

xall16-002
5.2...4.....71...3..............46...7.2......1.......6....2.......3..1.4........
xall16-004
1..6............5........3.....4.72.....2....3.........24...1.....3..6...7.5.....
5.42.........4..3.1.........6..73.........5.1..........3.....7....5..4..6........
5.42.........4..3.1.........6..73.........5.1..........3.....7....5..4..8........
xall16-006
....6.5.28.1................5..2....4......8....9..3.....8.4.9..2..........1.....
...71....4.6......2.............45..6..2...........31..3..5...........42.1.......
.7....3.2...5.6............5..4.........7.2....1......6.....4...2..3.......1...5.
1.42.........4..3.5.........6..73.........5.1..........3.....7....1..4..8........
6...42....3....7............8.73...........42...1.....2.4..5.........3..5........
xall16-007
2.....3.6..1.5.................41.5.67....2...3.........8....4....7........6.....
xall16-008
....57...1...3....6.4......2......6....4...1..7........3....7.5...1...........3..
....9.2.56.8................5..2....4......8....9..3.....8.4.6..2..........1.....
....9.5.26.8................5..2....4......8....9..3.....8.4.6..2..........1.....
....9.5.28.1................5..2....4......8....9..3.....8.4.9..2..........1.....
.3.5.....7......2........1..43...5......1..........3..2.1..7......3..6.4.........
6.1...........24...........42...3.......5..17.........5..16.....4....3.....7.....
6.2...5.....13...4..............57...3.2......1.......7....2.......4..3.5........
7.38........6..4..2...............73.4.1..............61....9......2.1......7....
xall16-009
4..35....61..........7......83..1..........2........4.5.....1..2..4...........8..


Enjoy!

gordon

[Moschopulus]

Here are the pseudo-Sudokus with low numbers of completions...

Thank you. Is it always possible to add a clue to these pseudo-16s to get a 17? Did you find them by removing a clue from a 17?

I guess all the completions are reasonable candidates for a 16.

Interestingly, the clique numbers in the completions can vary. The 7 completions of xall16-007 have clique numbers 9, 10, 8, 9, 10, 12, 10.

[gfroyle]

Thank you. Is it always possible to add a clue to these pseudo-16s to get a 17? Did you find them by removing a clue from a 17?.

Most of those can have a clue added to form a 17, but not all of them.

They are found by deleting clues from 17s, and then perturbing them while retaining the property of having few completions... the idea is that I hope that I can "step" from a pseudo-16 to a genuine-16 by a series of perturbations where each intermediate puzzle has less than, say, 200 completions.

Gordon

[udosuk]

Another favour to ask gfroyle or Ocean... please post the 12 {0 1 2 2 2 2 2 2 4} and the 13 {1 1 1 2 2 2 2 2 4} as well, since the next one up has 81 occurences, quite a stepping up...

Forgot to thank Ocean last time... BTW could you show us the unique (for now) {111112235:B}, and maybe all 5 17-sudokus that have five clues in the same box? Thanks again!

Haven't had time to tackle all these but hopefully some of them will be good challenges!

[Ocean]

Another favour to ask gfroyle or Ocean... please post the 12 {0 1 2 2 2 2 2 2 4} and the 13 {1 1 1 2 2 2 2 2 4} as well, since the next one up has 81 occurences, quite a stepping up...

Forgot to thank Ocean last time... BTW could you show us the unique (for now) {111112235:B}, and maybe all 5 17-sudokus that have five clues in the same box? Thanks again!

Code: Select all

V:422222210
000000074002800000000000003070530000600000010000000200540000600000071000700000000
000004560010030000700000000042000000000700800006400000300052000000000041000000000
000041000020000006000000800450600007300000040000200000000000410000570000000000300
000500070600200000000000080000001300504000000700080000000040207000700600010000000
001000460200008000000000100000025008014000000000030000530000000000600700000100000
001000460500008000000000100000025008014000000000030000230000000000600700000100000
008600000010000002000000530200700000070300000000000028600000400500020000000010000
008700000010000002000000630200500000030400000000000028400000500600020000000010000
020000800000050700010000000700600200500000030000402000000200010600000004000080000
071000000000200000000000800850000400000170600000300000000010030400005000000000012
085200000000000067000000000000046800600030000100000000060000540003007000000100000
340000000000200600060000000000041000007000050000000080400000103000700400002500000

V:422222111
000000061050030000000000000680040700200600000000000500900106000000000380000200000
000000706000300000900000000000016200080000050040000000107000600000800030600500000
000021000090000050000000000250800070600000200000900000300000102000470000000000006
000025006070000900000000000080900420000100000200000000502000030000740000600000000
000071000200000060000000000670500030040000700000200000009000107000830000000000400
000304000020000000500000000000850070041000000000000090004000103200070600000000400
000304000020000000500000000000950080041000000000000070004000103200070600000000400
000800740301000000000000000570006003000030002000000000640000300000010090000200000
054200000000000067000000000000046800600090000100000000060000590003007000000100000
078000000000000060000000050000001800600000300200060000004000701020650000000900000
085200000000000067000000000000046800600090000100000000060000590003007000000100000
420000050000008700000100000060095000000000001000040000000300260508000000000000500
450000060000008700000100000090026000000000001000040000000300250608000000000000600
...

B:532211111
000100800025000000000060000000702000100000400000500000800090070000000603000000052

B:532221110
000200400070000300010000000800300020000000670000000015400051000000070000900000000
000300400800500000706000000030000100000060000000008000000150070000000209000000086

B:522222110
000000091000020000000400000507000200100900000860000000040000080090001000000070300
000000091000030000000500000608000300200900000170000000050000020090001000000080400

Here is also the list of 'double zeros' (two empty boxes), since these are rare:

Code: Select all

B:443221100
000000109400050000000020300000109000500007000000300000013000000080000040009000020
000000308400050000000020100000103000500007000000800000013000000080000020009000040

B:433222100
000000031000407000000600000600300000407000000500080000030010000020000700000000450
000200080000000350000604000000000204700900000500000000140070000026000000000030000

B:333322100
000028000000010070000000035050600200037000000000000100800400000000305000100000000
000028000000010070000000063030500200067000000000000100800400000000306000100000000

B:432222200
000600100040200000030000070500000084102000000600000000000089000000030600000000002
420000000000000910000000600000416000750000000000090000000500082601000000000300000

B:333222200
000000210780000000000000400000000305000014000000060000201000040000800007060500000
000000280000310000000060000500000040703000000000000001000502300016000700040000000
000308000460000000500000000000000150000064000000000300008120000000500200070000004
000320000850000000010000000000016000000000203000005090000000610300400000200800000
000320000850000000010000000000016000000000302000005090000000610300800000200400000
000320000860000000010000000000041000000000203000006090000000410300500000200800000
000320000860000000010000000000051000000000302000006090000000510300800000200400000
001430600300000050000800000000201000750000000080000000000000408000075000000000200
001430700300000050000800000000201000560000000080000000000000408000065000000000200
200000500000000960800000000010380000060000400000020070000000081000506000000700000
200600030040000090000010000700300000105000000000809000080000500000000107030000000
701000000000904000000300000090000300000000409200000000000700028600010050040000000

!---------------------------------------------------------

[udosuk]

Thanks heaps Ocean mate! You're a legend!

[Wolfgang]

What would be great is if you could find 10 or 20 "random" 17s - that is, constructed without reference to the existing lists. Then if it turned out that all but 1 or 2 of them were already on the list, we would have confidence that the 17s are mostly found.

Since i dont want to wait longer for a new 17-clue:
With a slightly changed simple heuristic I have found 51 non-isomorphic 17-clues in 20 regions last week (always starting from a random sudoku) and all were already in your list !
So i think:
You probably have already found more than 90% of the 17-clues and there are less than 35000 grids containing a 17-clue (30531 in the moment).
If a 16-clue exists,
- it is hard in the sense that it needs much recursions to be solved
- it is "well hidden" in the sense that there are almost only hard 17-clues around it (including the 65 trivial ones)

[gfroyle]

Since i dont want to wait longer for a new 17-clue:
With a slightly changed simple heuristic I have found 51 non-isomorphic 17-clues in 20 regions last week (always starting from a random sudoku) and all were already in your list !
So i think:
You probably have already found more than 90% of the 17-clues and there are less than 35000 grids containing a 17-clue (30531 in the moment).

Wow... that is very interesting, so thanks very much for that... I am still finding a trickle of 17s, but each one seems harder and harder to find..

What I can't get over is the difference between 18s and 17s (and until I understand that, I will still not have much confidence either way). In a recent thread, I posted 8 symmetric 18s - these arose because I searched my collection of 22 million 18s for ones with some symmetries, and I found 2 with that particular pattern. I found 6 more by simply altering a few entries in those 2. Then I started an exhaustive search for that pattern (which I knew I would not complete) and let it run for 2-3 days, after which I had 209 non-isomorphic ones! So my original list of 18s had AT MOST 1% of the ones with that pattern...

So from this sort of result I feel that there must be VAST numbers of 18s that I have not found...

Still, it is all interesting stuff ..

Gordon

PS (For dukuso) - our local paper had an article about Eternity II in which they claimed that Monckton (with the help of Oliver Riordan and Mark Selby) have completed the puzzle, and are now just looking for insurers to underwrite the prize for a new game.

[Lardarse]

PS (For dukuso) - our local paper had an article about Eternity II in which they claimed that Monckton (with the help of Oliver Riordan and Mark Selby) have completed the puzzle, and are now just looking for insurers to underwrite the prize for a new game.

What do you call local?

[coloin]

What I can't get over is the difference between 18s and 17s (and until I understand that, I will still not have much confidence either way).....
...........So from this sort of result I feel that there must be VAST numbers of 18s that I have not found...

I tried to post on this subject before....

I think almost every puzzle can be represented minimally as [16], 17,18,19 or 20 clues.

Mosch and Dukoso have analysed three grids :
Canonical - 19 clues but no 18 puzzle.
Miracle - 19 clues but no 18
Other canonical varient - 20 clues but no 19 .

Gordon has 30531 grids which have one or more 17s but dont have a 16.

There are numerous unavoidable sets in any one grid - average 700 - and this is not counting the sets over 35 clues in length.

In the SF we are able to pick 17 clue numbers which "hit" EVERY set in the grid. However there does not exist 16 numbers which hit EVERY set in this grid. There may be a grid which we are able to do this but it is becoming increasingly less likely.

The reason that I think the largest minimum clues is 20 is that it is impossible to construct a grid which has more than 20 disjointed sets. You would have to have 20 disjointed 4-set unavoidables. It is also likely that a grid with 16 disjointed 4-sets, which has only room for 2 more disjointed 6-sets, will be solvable in 19 clues.

I suppose the more larger [14 and above] sets you have the more likely you are to be able to pick clues which cover these sets minimally.

Mosch's miracle grid [MCN = 14 or 15] was an example which surprised us in being easily solved in 19 clues.

I havent found a grid which didnt reduce to less than 21 clues. I await exceptions to this.

Therefore it is not surprising that there are so many 18s.....maybe almost all of the 1e^10 essentially different grids can be solved with 18 clues.

A question...

Code: Select all

In the grids with 17 clues......are there any 18s in these grids which have only a small number[or none] of clues in common with the 17 puzzle ?


C

[gfroyle]

What do you call local?

Local means "in Australia" in this context, because I guess the audience for this forum is global.

More precisely: the article was in "The Australian" which is the only Australian national daily newspaper, so it is local to Australia, but not local to Western Australia.

Cheers

Gordon

[gfroyle]

Therefore it is not surprising that there are so many 18s.....maybe almost all of the 1e^10 essentially different grids can be solved with 18 clues.
C

Very good point... I was so busy being concerned about artificial phenomena skewing my search that I had overlooked the fact that the most likely explanation is simply that it is actually TRUE that most grids have 18s, but no 17s.

Gordon

[Lardarse]

A question...

In the grids with 17 clues......are there any 18s in these grids which have only a small number[or none] of clues in common with the 17 puzzle ?

I'll take that question 1 step further:

In SF where you found 29 (iirc) minimal 17's, how many minimal 18's are there?