38 posts
• Page **2** of **3** • 1, **2**, 3

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) ?

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

- 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

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

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:**1850**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
`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

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:

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

- 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

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.Nick70 wrote:I did a complete search on another 17-clue pattern:

...

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

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

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

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

38 posts
• Page **2** of **3** • 1, **2**, 3