Complete Sudoku Collection - Vol. 1

Everything about Sudoku that doesn't fit in one of the other sections

Postby Nick70 » Wed Dec 21, 2005 12:06 am

I have almost finished searching the 17-clue pattern... I found 36 puzzles, as expected.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Nick70 » Wed Dec 21, 2005 9:52 am

The search is finished and I confirm there are 36 puzzles on that pattern.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby gfroyle » Wed Dec 21, 2005 12:50 pm

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

Postby Moschopulus » Wed Dec 21, 2005 2:28 pm

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

Postby Nick70 » Wed Dec 21, 2005 2:43 pm

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

Postby kjellfp » Wed Dec 21, 2005 2:52 pm

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

Postby coloin » Wed Dec 21, 2005 2:59 pm

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: 2365
Joined: 05 May 2005
Location: Devon

Postby Lardarse » Wed Dec 21, 2005 10:44 pm

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

Postby Ocean » Fri Dec 23, 2005 1:53 pm

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
000000000063000029780000104000149000000503000000726000601000045900000700270000830
000000000706000025052000896000052000000961000000304000900000080001000072370000410
000000005107000200560000194000040000000652000000397000702000600098000041015000900
000000005843000601120000380000819000000236000000070000009000078260000900017000003
000000006276000081340000705000800000000450000000127000167000009009000024008000650
000000007781000409420000380000090000000176000000240000650000730043000062090000100
000000009034000708758000320000487000000102000000360000290000006306000405500000190
000000010200000043397000608000540000000601000000092000805000020003000106061000980
000000010300000204754000630000894000000605000000023000840000070006000300005000429
000000017025000004860000200000067000000014000000938000408000509200000030309000071
000000017067000200892000360000010000000409000000568000056000070029000806308000024
000000020105000308493000005000170000000302000000864000836000497900000180010000600
000000030120000908509000400000406000000387000000009000410000670087000592050000100
000000030910000604528000900000045000000380000000710000059000207270000015060000040
000000037846000900020000060000540000000731000000086000590000300001000025064000810
000000038500000010094000762000312000000054000000068000020000674360000820100000000
000000039780000100069000527000975000000064000000301000302000090004000005871000402
000000040654000108800000320000830000000514000000609000420000006900000801307000290
000000050075000384060000072000950000000710000000384000180000006003000025200000431
000000050170000620029000187000905000000014000000270000600000500005000970800000312
000000057100000602694000030000807000000265000000039000009000570530000108076000040
000000084901000067700000501000030000000579000000864000030000006620000039840000050
000000089104000600870000150000697000000180000000302000300000006510000927260000800
000000089350000200102000450000003000000970000000125000489000007070000503530000028
000000090007000103134000607000876000000031000000209000648000320090000004300000705

Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Moschopulus » Sat Dec 24, 2005 1:30 am

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

Postby Nick70 » Sat Dec 24, 2005 7:51 pm

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

Postby Red Ed » Sun Dec 25, 2005 12:48 am

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!:D
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gfroyle » Sun Dec 25, 2005 5:31 am

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

Postby kjellfp » Fri Dec 30, 2005 10:07 am

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

Postby Ocean » Fri Dec 30, 2005 3:56 pm

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 grid
XXX

00X
0X0 -> Probably none.
XXX

00X
0XX -> Probably none.
XX0

00X                                           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.
XXX

00X
0XX -> Probably none.
XXX

00X
XX0 -> YES (subset of case with 4 empty boxes).
XXX

0XX
X0X -> YES.
XX0


For 2 empty boxes, any choice is possible.
Ocean
 
Posts: 442
Joined: 29 August 2005

PreviousNext

Return to General