kjellfp wrote:I have now completed an exhaustive search on the form

- Code: Select all
`00X`

0XX

XXX

No Sudoku exists, but there are plenty with only two solutions.

This completes the list of which empty-box sets there might be in a Sudoku. Ocean's list is complete, his assumtions were right. I.e. there are no Sudokus on any of the forms

- Code: Select all
`00X`

0XX

XXX

00X

0XX

XX0

00X

0X0

XXX

I don't know the minimal number of solutions for the last one.

Great!

To sum it up, what you have established is that all Sudokus with emtpy boxes belong to (or can be transformed to) one of these six (nonisomorphic) cases:

- Code: Select all
`0XX 00X 0XX 00X 0XX 00X `

XXX XXX X0X XX0 X0X XX0

XXX XXX XXX XXX XX0 XX0

I had prepared a trivial post on something analogous to a 'complexity hiearchy': [or maybe there is a better word...]

- Code: Select all
`00X `

0XX (3 empty boxes)

XXX

00X

0XX (4 empty boxes, but 'similar to' or 'same as' above)

XX0

00X

0X0 (4 empty boxes, and at least as 'hard' as those above)

XXX

00X

0X0 (5 empty boxes, and at least as 'hard' as all above)

XX0

00X

0X0 (6 empty boxes, and at least as 'hard' as all above)

X00

Since no Sudoku exists for the 3-case, it's now obvious that neither exists for the 4/5/6-cases in this hierarchy. Further, the minimal number of solutions cannot decrease down the hierarchy.

With reference to

kjellfp wrote: B)

XX0

X00

00X

...

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.

this means that the minimal number of solutions for this one:

00X

0X0

XXX

is between 2 and 72.