## Complete Sudoku Collection - Vol. 1

Everything about Sudoku that doesn't fit in one of the other sections
I have almost finished searching the 17-clue pattern... I found 36 puzzles, as expected.
Nick70

Posts: 156
Joined: 16 June 2005

The search is finished and I confirm there are 36 puzzles on that pattern.
Nick70

Posts: 156
Joined: 16 June 2005

Nick70 wrote:The search is finished and I confirm there are 36 puzzles on that pattern.

Does *your* exhaustive search program work by filling in the pattern in all possible (legal, inequivalent) ways, and then checking each one in turn?

If so, then a 20-cell pattern is surely a gargantuan search?

With regard to the X pattern, I had already searched all puzzles on that pattern with each digit occurring at most three times - there are however a few on that pattern where a digit occurs MORE than three times. These were found by by randomized search, but it is interesting that there turn out to be no more...

Cheers

Gordon
gfroyle

Posts: 214
Joined: 21 June 2005

Since we've done multiplication (the X pattern) what about addition (the + pattern) ?

Code: Select all
`... .+. ...... .+. ...... .+. ...... .+. ...+++ +++ +++... .+. ...... .+. ...... .+. ...... .+. ... `

The search space is very small, maybe this can be done by hand...
Moschopulus

Posts: 256
Joined: 16 July 2005

gfroyle wrote:Does *your* exhaustive search program work by filling in the pattern in all possible (legal, inequivalent) ways, and then checking each one in turn?

Yes, it works as described by other posters.

gfroyle wrote:If so, then a 20-cell pattern is surely a gargantuan search?

Yes, the search on the 19-clues pattern at the top of the thread took a couple of months.
Nick70

Posts: 156
Joined: 16 June 2005

Moschopulus wrote:Since we've done multiplication (the X pattern) what about addition (the + pattern) ?

This would give a 15, let's try to settle whether 16s exist first...
kjellfp

Posts: 140
Joined: 04 October 2005

It looks like 19 clues counted in that "X" pattern

But it is 16 at the most..... [cant see 15..but you may well be right !]

I dont think there can be 4 empty boxes though - even with 32 clues in Boxes 2,4,6&8. ?

It pays tribute to Gordon's methods that he got all 36.
I suppose all the solutions are "close" to each other wrt common clues.

Is their scope for optimizing all this ?

Do you think you [Gordon] have "gone over" all grids with a pattern......ie all 17s ? !

C
coloin

Posts: 1864
Joined: 05 May 2005

Moschopulus wrote:Since we've done multiplication (the X pattern) what about addition (the + pattern) ?

Code: Select all
`... .+. ...... .+. ...... .+. ...... .+. ...+++ +++ +++... .+. ...... .+. ...... .+. ...... .+. ... `

The search space is very small, maybe this can be done by hand...

Does any1 want to consider the possibility of there being less clues needed (and therefore more chances of a 16/17) if the diagonal rule is used?
Lardarse

Posts: 106
Joined: 01 July 2005

coloin wrote:I dont think there can be 4 empty boxes though - even with 32 clues in Boxes 2,4,6&8. ?

Sudokus with 4 empty boxes are not too common, but quite simple to generate. (Don't think I've seen 5 emtpy boxes though.) Here a few samples:

Code: Select all
`000000000063000029780000104000149000000503000000726000601000045900000700270000830000000000706000025052000896000052000000961000000304000900000080001000072370000410000000005107000200560000194000040000000652000000397000702000600098000041015000900000000005843000601120000380000819000000236000000070000009000078260000900017000003000000006276000081340000705000800000000450000000127000167000009009000024008000650000000007781000409420000380000090000000176000000240000650000730043000062090000100000000009034000708758000320000487000000102000000360000290000006306000405500000190000000010200000043397000608000540000000601000000092000805000020003000106061000980000000010300000204754000630000894000000605000000023000840000070006000300005000429000000017025000004860000200000067000000014000000938000408000509200000030309000071000000017067000200892000360000010000000409000000568000056000070029000806308000024000000020105000308493000005000170000000302000000864000836000497900000180010000600000000030120000908509000400000406000000387000000009000410000670087000592050000100000000030910000604528000900000045000000380000000710000059000207270000015060000040000000037846000900020000060000540000000731000000086000590000300001000025064000810000000038500000010094000762000312000000054000000068000020000674360000820100000000000000039780000100069000527000975000000064000000301000302000090004000005871000402000000040654000108800000320000830000000514000000609000420000006900000801307000290000000050075000384060000072000950000000710000000384000180000006003000025200000431000000050170000620029000187000905000000014000000270000600000500005000970800000312000000057100000602694000030000807000000265000000039000009000570530000108076000040000000084901000067700000501000030000000579000000864000030000006620000039840000050000000089104000600870000150000697000000180000000302000300000006510000927260000800000000089350000200102000450000003000000970000000125000489000007070000503530000028000000090007000103134000607000876000000031000000209000648000320090000004300000705`
Ocean

Posts: 442
Joined: 29 August 2005

Ocean wrote:
Sudokus with 4 empty boxes are not too common, but quite simple to generate. (Don't think I've seen 5 emtpy boxes though.)

None has been found with 5 empty boxes. Discussed before on this thread:
http://forum.enjoysudoku.com/viewtopic.php?t=1180
Moschopulus

Posts: 256
Joined: 16 July 2005

I did a complete search on another 17-clue pattern:
Code: Select all
`*.*.*...........*.*.........*.*.*.........*.*...*.........*.*...*.....*.*..*.....`

gfroyle's list had 28 puzzles on that pattern. I found 34:

Code: Select all
`1.2.3...........6.4.........7.8.6.........1.4...5.........1.2...6.....8.5..3.....1.2.3...........6.4.........7.6.8.........1.4...9.........1.2...6.....8.5..3.....1.2.3...........6.4.........7.6.8.........2.1...9.........1.3...6.....8.5..2.....1.2.3...........6.4.........7.6.8.........2.4...7.........2.1...6.....8.5..9.....1.2.3...........6.4.........7.6.8.........2.3...7.........1.3...6.....8.5..9.....1.2.3...........6.4.........7.6.8.........1.4...7.........1.2...6.....8.5..9.....1.2.3...........6.4.........7.6.8.........5.2...7.........2.1...6.....8.5..3.....1.2.3...........6.4.........7.6.8.........2.5...7.........2.1...6.....8.5..3.....1.2.3...........6.4.........7.6.8.........2.4...7.........2.1...6.....8.5..3.....1.2.3...........6.4.........5.6.7.........9.2...3.........2.1...6.....7.5..8.....1.2.3...........6.4.........3.7.6.........4.1...8.........1.2...6.....8.5..9.....1.2.3...........6.4.........3.7.6.........4.1...8.........1.2...6.....7.5..9.....1.2.3...........6.4.........3.6.7.........4.1...8.........1.2...6.....7.5..9.....1.2.3...........6.4.........3.6.7.........5.1...3.........1.2...6.....7.5..8.....1.2.3...........6.4.........3.6.7.........4.1...3.........1.2...6.....7.5..8.....1.2.3...........6.4.........3.6.7.........1.5...3.........1.2...6.....7.5..8.....1.2.3...........5.4.........6.7.8.........4.9...5.........4.2...5.....8.3..6.....1.2.3...........5.4.........6.7.8.........9.4...5.........4.2...5.....7.3..6.....1.2.3...........5.4.........6.7.5.........1.4...1.........1.2...5.....7.3..8.....1.2.3...........5.4.........6.5.7.........6.4...8.........4.2...5.....7.3..9.....1.2.3...........5.4.........6.5.7.........9.4...8.........4.2...5.....8.3..6.....1.2.3...........5.4.........6.5.7.........4.9...8.........4.2...5.....8.3..6.....1.2.3...........5.4.........6.5.7.........9.1...8.........1.2...5.....8.3..6.....1.2.3...........5.4.........6.5.7.........4.9...6.........4.1...5.....7.3..8.....1.2.3...........5.4.........6.5.7.........4.2...6.........2.1...5.....7.3..8.....1.2.3...........5.4.........6.5.7.........2.4...6.........2.1...5.....7.3..8.....1.2.3...........5.4.........6.5.7.........1.2...6.........1.8...5.....7.3..2.....1.2.3...........5.4.........6.2.7.........8.4...5.........4.1...5.....7.3..6.....1.2.3...........5.4.........6.2.7.........4.8...5.........4.1...5.....7.3..6.....1.2.3...........5.3.........6.7.8.........1.9...5.........1.2...5.....8.4..6.....1.2.3...........5.3.........6.7.8.........9.1...5.........1.2...5.....7.4..6.....1.2.3...........5.3.........6.7.8.........1.9...5.........1.2...5.....7.4..6.....1.2.3...........5.3.........6.7.5.........1.9...8.........1.2...5.....8.4..6.....1.2.3...........5.3.........6.5.7.........9.1...8.........1.2...5.....8.4..6.....`
Nick70

Posts: 156
Joined: 16 June 2005

Nick70 wrote:I did a complete search on another 17-clue pattern:
...
gfroyle's list had 28 puzzles on that pattern. I found 34:
Mmm... that shows up bias in the way Gordon is searching for grids. If we take your first experiment, on which Gordon "scored" 36/36, and this new one on which Gordon scored 28/34, then the joint maximum likelihood estimator of the true number of 17s is ~36020. At this MLE, the first result looks lucky to the tune of 1-in-15 (p-value 6.67%) and the second looks unlucky to the tune of 1-in-25 (p-value 3.95%). Not a very good fit.

Thinking out loud now ... is there something about the neighbourhood of puzzles on the first clue set that makes them particularly attractive to Gordon's searcher? If so, then perhaps we should try Nick70's programs on clue sets in bad neighbourhoods (those with few 18s?) instead, to pick up the puzzles that Gordon's program left behind.

Ooh, look at the time. Merry Christmas!
Red Ed

Posts: 633
Joined: 06 June 2005

Red Ed wrote:]Mmm... that shows up bias in the way Gordon is searching for grids. If we take your first experiment, on which Gordon "scored" 36/36, and this new one on which Gordon scored 28/34, then the joint maximum likelihood estimator of the true number of 17s is ~36020.

Actually, I now have 34479 puzzles in hand, and they contain all 34 of that collection of Nick's

The rate of puzzle discovery has ramped up slightly because I am experimenting with ways to force the search out of explored territory and into new territory...

I think 36000 is too low... I aim to have 35000 by New Year...

However, I am sure that the search is biased.. just that I don't know how..

Cheers and Merry Christmas

Gordon
gfroyle

Posts: 214
Joined: 21 June 2005

### 5 empty boxes impossible

Moschopulus wrote:
None has been found with 5 empty boxes. Discussed before on this thread:
http://forum.enjoysudoku.com/viewtopic.php?t=1180

There is no Sudoku with 5 empty boxes. As mentioned in the link, there are two non-isomorphic cases to consider.

A)
0XX
X00
X00

B)
XX0
X00
00X

Other cases involve three empty boxes in a band or stack, and can never give unique solutions.

Case A) has been handled in the B12347-method and the best is 1960 solutions (see the lilnk)

Case B) was started by dukuso, he got down to 84 solutions as the best, but interrupted the program after an hour as he estimated it would take days to complete.

I have written a program to do B) in the most efficient way I could find, and the program completed in 14 minutes. The smallest positive number of solutions found was 72. Therefore there is no Sudoku with 5 empty boxes. The program also computed the total number of sudoku grids for a check on its reliability, and so the number 6670903752021072936960 has been reconfirmed for the Nth time (but this was the fastest I have seen not using the band by band method).

72 is also the smallest number of solutions possible for any clue-set with 5 empty boxes, as the smallest number of solutions for three empty boxes on a row is 96.
Last edited by kjellfp on Mon Jan 02, 2006 6:06 am, edited 2 times in total.
kjellfp

Posts: 140
Joined: 04 October 2005

### Re: 5 empty boxes impossible

kjellfp wrote:
Moschopulus wrote:
None has been found with 5 empty boxes. Discussed before on this thread:
http://forum.enjoysudoku.com/viewtopic.php?t=1180

There is no Sudoku with 5 empty boxes. As mentioned in the link, there are two non-isomorphic cases to consider...

Thanks to Moschopulus for pointing to the previous discussions, and to kjellfp for updated information!

As far as I am aware of, this is the status for sudokus with empty boxes:

For 4 empty boxes, there are five nonisomorphic cases:
Code: Select all
`000 0XX -> No unique grid (3 empty boxes in a row)XXX 00X 00X -> No unique gridXXX00X 0X0 -> Probably none.XXX00X 0XX -> Probably none.XX000X                                           X0X XX0 -> Many unique grids   [Also isomporph to 0X0 XX0                                           X0X`

For 3 empty boxes, there are four nonisomorphic cases:
Code: Select all
`000 XXX -> Obviously no unique grid.XXX00X 0XX -> Probably none.XXX00X XX0 -> YES (subset of case with 4 empty boxes).XXX0XX X0X -> YES.XX0`

For 2 empty boxes, any choice is possible.
Ocean

Posts: 442
Joined: 29 August 2005

PreviousNext