coloin wrote:Its not looking good for finding a 10-clue

We don't really expect to find a 10-clue SudokuP. We want to

prove that such a beast exists or not.

coloin wrote: Remove grids that cant have an 11, scan every other grid for a 11 - using hitting sets of UAs.

Actually I was just about to post the results of my initial foray into the actual generation of Hitting Sets and testing the associated puzzle sets.

I had hoped to piggy-back the enumeration of 11-clue puzzles along with the 10-clue testing, but that now looks to be an impossible dream.

I tested the process (generate puzzles using HSets and test-solve) using one of the known cases, namely the first one in the original set of 10:

- Code: Select all
`182764593493528176657193284841259637765831942329476815976315428214687359538942761`

The process reported these known cases (so is on the right track). There may be more, the job is only 70% complete:

- Code: Select all
`1.2........3..............4.4..5.....6..............1..7...........8..........7..`

1.2........3..8...........4.4..5.....6..............1..7......................7..

The largest set of UA's that I could assemble (using GridChecker, as my simplistic UA generator proved to be inadequate) was 124, from which I obtained:

- 27,266,402 Hsers of size 10

- 620,690,909 HSets of size 11

These are "net" figures, ie the HSets of size 9 do not include any repeats of size 8, etc.

The first 3 cases need to be multiplied by the "free cell multiplier", for size 8 this is C(73, 3) = 62,196, for size 9 it's C(72,2) = 2,556, and for size 10 it's 71.

So the total number of 11-clue puzzle candidates that need to to be tested is (1130 x 62196) + (375331 x 2556) + (27266402 x 71) + 620690909 =

3,586,232,967 .

Even at 50,000 grids/second (and we have to to add the overhead of generating the HSets, a non-trivial exercise), that's roughly one whole day to completely enumerate.

If this "profile" is typical of an 11-clue puzzle, and it does appear to be so, then that's the death sentence for exhaustive enumeration!

The same job runnng in 10-clue mode, where the multipliers are more favourable, invoves (1130 x 2628) + (375331 x 72) + 27266402 = 57,259,874 10-clue puzzles to test.

This only took about 35 minutes, which I can live with, so the project remains alive and kicking.

Months I can do, years is well outside my comfort zone!