## 17-clue and 18-clue Sudoku update

Everything about Sudoku that doesn't fit in one of the other sections
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]   Randomsuexsf value        24.10       24.02           24.17                 24.42number 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 16741694    0   97  219  201  197    0  134   361694  138   20   85  112  162 1671  206  2361691   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 1694these 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
Last edited by coloin on Wed Nov 30, 2005 2:03 pm, edited 3 times in total.
coloin

Posts: 1877
Joined: 05 May 2005

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!
udosuk

Posts: 2698
Joined: 17 July 2005

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-0025.2...4.....71...3..............46...7.2......1.......6....2.......3..1.4........xall16-0041..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-0072.....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-0094..35....61..........7......83..1..........2........4.5.....1..2..4...........8..`

Enjoy!

gordon
gfroyle

Posts: 214
Joined: 21 June 2005

gfroyle wrote: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.
Moschopulus

Posts: 256
Joined: 16 July 2005

Moschopulus wrote: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
gfroyle

Posts: 214
Joined: 21 June 2005

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!
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote: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 000000074002800000000000003070530000600000010000000200540000600000071000700000000000004560010030000700000000042000000000700800006400000300052000000000041000000000 000041000020000006000000800450600007300000040000200000000000410000570000000000300 000500070600200000000000080000001300504000000700080000000040207000700600010000000001000460200008000000000100000025008014000000000030000530000000000600700000100000 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:522222110000000091000020000000400000507000200100900000860000000040000080090001000000070300 000000091000030000000500000608000300200900000170000000050000020090001000000080400 `

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

Code: Select all
`B:443221100000000109400050000000020300000109000500007000000300000013000000080000040009000020 000000308400050000000020100000103000500007000000800000013000000080000020009000040 B:433222100000000031000407000000600000600300000407000000500080000030010000020000700000000450 000200080000000350000604000000000204700900000500000000140070000026000000000030000 B:333322100000028000000010070000000035050600200037000000000000100800400000000305000100000000 000028000000010070000000063030500200067000000000000100800400000000306000100000000 B:432222200000600100040200000030000070500000084102000000600000000000089000000030600000000002 420000000000000910000000600000416000750000000000090000000500082601000000000300000 B:333222200000000210780000000000000400000000305000014000000060000201000040000800007060500000 000000280000310000000060000500000040703000000000000001000502300016000700040000000 000308000460000000500000000000000150000064000000000300008120000000500200070000004 000320000850000000010000000000016000000000203000005090000000610300400000200800000 000320000850000000010000000000016000000000302000005090000000610300800000200400000 000320000860000000010000000000041000000000203000006090000000410300500000200800000 000320000860000000010000000000051000000000302000006090000000510300800000200400000 001430600300000050000800000000201000750000000080000000000000408000075000000000200 001430700300000050000800000000201000560000000080000000000000408000065000000000200 200000500000000960800000000010380000060000400000020070000000081000506000000700000 200600030040000090000010000700300000105000000000809000080000500000000107030000000 701000000000904000000300000090000300000000409200000000000700028600010050040000000 `
!---------------------------------------------------------
Ocean

Posts: 442
Joined: 29 August 2005

Thanks heaps Ocean mate! You're a legend!
udosuk

Posts: 2698
Joined: 17 July 2005

### Re: 17-clue and 18-clue Sudoku update

gfroyle wrote: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)
Last edited by Wolfgang on Wed Dec 07, 2005 5:40 am, edited 1 time in total.
Wolfgang

Posts: 208
Joined: 22 June 2005

### Re: 17-clue and 18-clue Sudoku update

Wolfgang wrote: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.
gfroyle

Posts: 214
Joined: 21 June 2005

### Re: 17-clue and 18-clue Sudoku update

gfroyle wrote: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?
Lardarse

Posts: 106
Joined: 01 July 2005

### Re: 17-clue and 18-clue Sudoku update

gfroyle wrote: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
Last edited by coloin on Thu Dec 08, 2005 8:26 am, edited 1 time in total.
coloin

Posts: 1877
Joined: 05 May 2005

### Re: 17-clue and 18-clue Sudoku update

Lardarse wrote: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

Posts: 214
Joined: 21 June 2005

### Re: 17-clue and 18-clue Sudoku update

coloin wrote: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
gfroyle

Posts: 214
Joined: 21 June 2005

### Re: 17-clue and 18-clue Sudoku update

coloin wrote: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?
Lardarse

Posts: 106
Joined: 01 July 2005

PreviousNext

Return to General