Well...it is a tricky one.
My first and second attempts at this were unsuccesful but my third attempt may be valid - although Ive made many assumptions and approximations
First Attempt-the reverse of the "birthday" problem in mathematics - coincidentally was an old research topic of
r.e.sThe formula k*=SQRT(2*N) .....rearranged gives N ~ 1/2 * k^2
Where N is the estimated number of grids and k is the number of grids generated when a significant number of duplicates emerge......
This was all very well but at the time I struggled to be able to recognise duplicates from more than a 64000 sample size.
Since then no grid has generated a single duplicate in one million grids, which makes me confident that we have more than 5^10^11 minimal puzzles per grid. [no marks really]
Second AttemptMy second method was to compute [using checker] the number of puzzles of size 20 in a particular grid
Accepting the potential for errors in this calculation
- Code: Select all
Est.no.of 20-clue puzzles Incid. of puzzles per 10^6 Number of puzzles estimated
Grid
74-2 3000 1 3*10^9
MC 638 5 1.3*10^7
We know this is wrong
There are at least 60,000 33s in the MC grid ! - none appeared by random generation !
Both these estimations are way too low and....... must be flawed - either as a bug or skewed by a probability quirk. [I think the latter]
Third AttemptI think this is similar to your method .....onlyI have found the average number of puzzles in a 34 clue minimal sudoku.....and made an approximation as to how many more puzzles each additional clue generates.
Take a random 25 clue puzzle ......add 9 non minimal random clues [from the solution grid][one clue in each box]
I think this is the same one as ravel used. [with 9 more clues]
- Code: Select all
+---+---+---+
|...|...|.8.|
|...|7..|163|
|.2.|...|.97|
+---+---+---+
|..2|3..|...|
|...|..4|7.2|
|91.|5.8|3.6|
+---+---+---+
|74.|.36|.25|
|.5.|8.7|..9|
|.39|2..|6.1|
+---+---+---+ ravel 34
Count up almost all the puzzles......This can be done.....
The program that I use finds it easier to come up with smaller puzzless..not sure why.
Here are the results of the numberof minimal puzzles found per grids generated.
- Code: Select all
puzzles generated 10000 100000 500000 2000000
ravel32 98
ravel33 233
ravel34 1259 1305 1305 1305
ravel35 4507 4563
ravel36 10482*
25clueplus9-1 886 910 910
25clueplus9-2 5591 11577 12104
25clueplus9-3 3038 4068 4080
25clueplus9-4 885 894 894
25clueplus9-5 5456 11407 11955
average 5208
So starting from 34 clues how many more puzzles do you get by adding an additional clue ?
In the ravel 32 98 total
In the ravel 33 135 new 233 total factor 135/98 = 1.37
In the ravel 34 1072 new 1305 total factor 1072/233 = 4.6
In the ravel 35 3258 new 4563 total factor 3258/1305 = 2.5
In the ravel 36 5919 new 10482 total factor 5919/4563 = 1.2 *
* most probably thereare more puzzles than 10482
If we ignore the effect of the unavoidable clues...
Assuming the average puzzles size is 25 clues. [it is]
Assuming the average puzzle count in a 34 cell non minimal puzzle is around 5000
Also assuming I have got these estimates correct !
- Code: Select all
In a 35 clue grid a clue is present in 25 ot of 35 ~ 75% therefore a 35 clue grid will 100/25 = 4.0 times more puzzles than a 34
In a 40 clue grid a clue is present in 25 ot of 40 ~ 62% therefore a 40 clue grid will 100/38 = 2.6 times more puzzles than a 39
In a 45 clue grid a clue is present in 25 ot of 45 ~ 55% therefore a 45 clue grid will 100/45 = 2.2 times more puzzles than a 44
In a 50 clue grid a clue is present in 25 ot of 50 ~ 50% therefore a 50 clue grid will 100/50 = 2.0 times more puzzles than a 49
In a 60 clue grid a clue is present in 25 ot of 60 ~ 41% therefore a 60 clue grid will 100/59 = 1.7 times more puzzles than a 59
In a 70 clue grid a clue is present in 25 ot of 70 ~ 35% therefore a 70 clue grid will 100/65 = 1.5 times more puzzles than a 69
In a full grid a clue is in 25 out of 81 ~ 30% therefore a 81 clue grid will 100/70 = 1.4 times more puzzles than a 80
Approximating ! adding 47 clues !
[35-36][37-38][39-42][43-45] [46-55] [56-65] [66-75] [76-81]
5000 * [4^2]*[3^2]*[2.5^4]*[2.2^3]*[2^10]*[1.7^10]*[1.5^10]*[1.4^6] = 5000*16*9*39*10*1024*201*57*7
=
23,060,356,300,800,000 ~ 2^16
Thats OK then
C