The New Sudoku Players' Forum

[coloin]

Out of curiosity I have attempted to estimate the number of minimal puzzles per puzzle pattern.
In the patterns game - puzzles of a specific pattern are generated and rated. Generating as many puzzles seems to be the way to do it, using a vicinity search of the harder puzzles found... Most puzzles with more than 24 clues seem to have at least one mutable clue, usually more.

Taking the 25 clue level

Number of 25 clue ed minimal puzzles = number of ed grids x number of minimal puzzles per ed grid.
5.00E+09 x 6.35E+14 = 3.17495E+24
divide by the total number of ed patterns
1.72398E+14
= 1.8E+10

This may be an underestimate by ? 10% because some patterns cant have puzzles [ eg those with no clue in 2 rows in a band]

Maybe some one can confirm these rather large numbers !!!

Code: Select all

  clues    estimation of minimal puzzles per established pattern 
                                             
   16       0                               
   17      ~1                               
   18      ~50                               
   19      ~5000                             
   20      ~100000                           
   21      1589108                           
   22      68369243                         
   23      1108338021                       
   24      6953894398                       
   25      18416429124                       
   26      20532959229                       
   27      9930303323                       
   28                                       
   29     
   ..      decreasing
   ..
   39     ~1
   40      1

            ~ is my estimate

C

[m_b_metcalf]

Interesting. And in Game 251 we've seen only 57 of the 18 billion puzzles (so far)!

M

[champagne]

Taking the 25 clue level

Number of 25 clue ed minimal puzzles = number of ed grids x number of minimal puzzles per ed grid.
5.00E+09 x 6.35E+14 = 3.17495E+24
divide by the total number of ed patterns
1.72398E+14
= 1.8E+10

This may be an underestimate by ? 10% because some patterns cant have puzzles [ eg those with no clue in 2 rows in a band]


C

Hi Coloin,

In the pattern game, the symmetry reduces the count.

My own experience (but I have to dig in the past to see how many clues had the pattern) is to have produces (several times) more than 200 million puzzles in one game.
this requires some power (generating, sorting, rating ... ) and about one week of work

[coloin]

Thinking of how to prove this......

For a 25 clue pattern, 2 E+10 / 5 E+9 ~ 4

That means there should be 4 puzzles in each grid solution.

Is it possible to check 1 random grid for puzzles of 1 random pattern ?

Is it just as simple as running a random pattern mask over the 6^8 x 2 [3359232] clue morphs of a random grid solution ?

[coloin]

Well ..... I ran a few experiments, It seems that there are at least these numbers.There also appears to be a wide variation in the actual counts per pattern.

It isnt really that remarkable that the number of mutable clues in a puzzle increases with the number of clues. The chances that a puzzle will have a superfluos clue - ie non-minimal, also increases with the number of clues in the pattern. This may also explain the variations per pattern in that some patterns may have a higher minimal/non-minimal ratio at different number of clues....

Some patterns have symmetry - and i agree this must mean that there are less puzzles.

[coloin]

Taking this 29 clue puzzle [ diagonal pattern with 533333333 box data]

Code: Select all

+---+---+---+
|..1|..3|..2|
|.2.|.4.|.1.|
|5..|1..|6..|
+---+---+---+
|..2|6.1|..4|
|.5.|.7.|.6.|
|7..|3.4|2..|
+---+---+---+
|..7|..8|..5|
|.8.|.9.|.7.|
|9..|2..|3..|

Making these clues a mask, and streaming over a series of 435532 nearly random ED grid solutions .
Valid puzzle count

Code: Select all

29772
32830
38610
37286
33504
30972

i got a valid puzzle rate of 7.7 %

The implications of this are that with this pattern there are approx 0.077 * 6e21 possible representations of this puzzle [minimal and non-minimal]
Essentially different puzzles of this pattern might be more difficult to estimate as this pattern has 4 or more [16 ?] degrees of automorphism

Using this figure we could estimate the number of ED puzzles [minimal and non-minimal] with the pattern as 0.077 * 6^8*2 * 5e9 / degree of automorphism

A ratio of minimality to non-minimality would be then available - this would then used to confirm the numbers of minimal puzzles postulated earlier in the thread ...... hmmmm

C

[coloin]

Running the mask over two more patterns

Code: Select all

+---+---+---+
|8..|...|7..|
|9.2|.73|.5.|
|...|.9.|.3.|
+---+---+---+
|...|6..|3..|
|62.|5..|.8.|
|.5.|.84|.1.|
+---+---+---+
|..8|9..|..4|
|4.7|.65|...|
|1..|...|9.8|
+---+---+---+   12284 puzzles  x 3 less in a random 29-clue pattern

Code: Select all

+---+---+---+
|..1|..2|..3|
|.2.|.1.|.4.|
|3..|5..|6..|
+---+---+---+
|..5|1.4|2..|
|.4.|.7.|..1|
|2..|9.8|.3.|
+---+---+---+
|..9|6..|.7.|
|.6.|.4.|3..|
|8..|..7|..4|
+---+---+---+   35927 puzzles similar - but ultimately more ED puzzles - in a asymmetric 533333333 29-clue pattern

[m_b_metcalf]

Taking this 29 clue puzzle [ diagonal pattern with 533333333 box data]

Code: Select all

+---+---+---+
|..1|..3|..2|
|.2.|.4.|.1.|
|5..|1..|6..|
+---+---+---+
|..2|6.1|..4|
|.5.|.7.|.6.|
|7..|3.4|2..|
+---+---+---+
|..7|..8|..5|
|.8.|.9.|.7.|
|9..|2..|3..|

[snip]

By chance I once investigated this pattern for the Patterns Game, but abandoned it because of the paucity of high diamonds (and, what's more, I didn't find a singles-only to submit).

Here is a minimal one (reflected) with symmetry of givens:

Code: Select all

 1 . . 2 . . 3 . .
 . 2 . . 3 . . 4 .
 . . 4 . . 5 . . 2
 6 . . 7 . 2 4 . .
 . 8 . . 5 . . 2 .
 . . 9 8 . 6 . . 7
 8 . . 5 . . 9 . .
 . 9 . . 1 . . 8 .
 . . 1 . . 8 . . 3  ED=2.0/1.2/1.2

Regards,

Mike Metcalf

[coloin]

Yes Mike .....i think at 29 clues minimal puzzles wont be that common.
However .... given that that 29 clue stem can be pared down to 23 clues - and have a lot of hard puzzles.
The 27 clue stem that is asymmetric - only one of the 15 - would appear to have at least x2 and sometime x18 more ED puzzles.
I will look at those 27 clue puzzle/patterns with diagonal clues - probably they will all be similar ....

Code: Select all

01#..1..2..3.2..1..4.5..6..1....2..4..1.5..6..7.7..2..3....7..5..8.8..7..9.9..3..2.. #   C27/S4.da/M1.16.3   
02#2...4...6..4..2.3..7.8..1....24...1.1...3...2.3...54....5..9.7..1.6..2..6...7...9 #   C27.M/S4.da/M1.31.2
03#..2..3.1..3..1.2..5..6....4..5..7.2..9..4.8..6..9....7.8..9..5.2..5..4....3..8..9 #   C27/S2.d/M1.33.1   
04#..1.2.3...2...1..43..5...6...42...8.9...3...2.3...67...4...3..75..8...4...2.6.1.. #   C27.M/S2.p/M1.13.4
05#1....2..3.9..4..1...73..5....21....9.6..2..5.9....56....3..41...7..8..2.2..6....8 #   C27.M/S4.da/M1.11.6
06#2...3.1....14...2..5...6..3.6.2..4..3...5..7...7..3..65..8..7...9..1..4...6..2..9 #   C27/S2.d           
07#.2..7...84..6..9....5..4.7..1.2..3..2...1...4..3..5.6..9.5..6....1..7..37...3..5. #   C27.M/S4.da/M1.16.1
08#1..3..2...2..4..1...3..6..52...8..7..7.5..3....9..1..67...9.5...4.1....8..8..2.6. #   C27/S2.d           
09#..2.1.3...1...2.4.5..3....2..5..7.8.6...3...4.4.6..9..7....4..6.3.2...5...4.9.7.. #   C27.M/S4.da         
10#..1..2..3.2..1..4.3..5..6....51..2...4..7...12....8.3...96...7..6..4.3..8....7..4 #   C27 [asymmetric]   
11#..1..3..2.2..4..3.4..6..5....23...1..4...57..5...9...8..6.8..7..9.1..6..7....2..1 #   C27/S2.d           
12#2..1....3..1..2.4..5..3.6..5..7...9...6.8.2...8...4..1..7.6..8..6.4..1..3....7..5 #   C27/S4.da           
13#2...3.1....14...2..5...6..3.6.2..4..3....4.7...7.8...65..8..7...9..1..4...6..2..9 #   C27/S2.d           
14#6....2.7...8.1...5.9.5..3....2..1..3.1..2..4.5..3..2....4..8.9.1...9.8...3.4....7 #   C27.M/S4.da         
15#..1.2...3.2...34..5..1...6...4..1.7.2...9...6.6.4..8...9...2..8..69...1.3...5.7.. #   C27.M/S4.da

[coloin]

Well ive done with the initial investigations ..

I ran the 27 and 25 clue diagonal masks and random 27 and 25 clue masks over my 435532 near random solution grids.

Average results

27 clue
diagonal 9000 puzzles 40 minimal
random 3000 puzzles 5 minimal

25 clue
diagonal 400 puzzles 60 minimal
random 100 puzzles 5 minimal

at the 25 clue level this equates to
5/435532 * 5e9 * 6^8 * 2 ~ 1.9e11 minimal puzzles per pattern

this tallies rather well
however there is a large variation between patterns.
the diagonal pattern do tend to have at least 3 times more puzzles.

C

[dobrichev]

Hi Coloin,

Just to mention that gridchecker tool has a function to scan a list of (ED) grids for all minimal valid puzzles with a given pattern.
Are you using it?

[coloin]

Acually your tool to --scan --cluemask was the one i wanted to use - but i couldnt work out the command line !
Yours probably would take seconds to cover 450000 puzzles - mine took 10 minutes !!!
what I have shown is that the diagonal patterns have more puzzles than random patterns with the same number of clues....... this probably means that there will be more hard puzzles.
A larger sample size of the random grids and random patterns would obviously make for more reliable results.
Afmob pm'ed me and he was able to get good results with his methods.
C

[dobrichev]

Example command line:

gridchecker --pattern --scanfor 1..2..3...2..3..4...4..5..26..7.24...8..5..2...98.6..78..5..9...9..1..8...1..8..3 < in_solutiongrids.txt > out_minimalpuzzles.txt

It takes only the given/non-given flag from the given pattern (a puzzle in this example) and generates list of all VPT. If the pattern has symmetries, the list is reduced accordingly. Then it processes each grid from the input file by finding the small unavoidable sets, then filtering only the patterns that hit all UA sets, then solving and checking for minimality the puzzles, and finally converts the puzzles back to canonical form in the coordinate system of the pattern given in the command line.
It typically takes one to ten seconds per grid per CPU, and uses all available cores.

From game 0269 with currently 84 posted puzzles you can solve the posted puzzles and, assuming there are no duplicate solution grids, to run the tool with one of the puzzles in the command line and the solutions list as input file. This way 3022 puzzles are generated for 193 seconds total CPU time (or ~50 seconds calendar time on 4-core machine).

This has been discussed some time ago. It is old code and I hope your version of gridchecker has it. Run w/o parameters and see if near to the bottom of the listed options there is --pattern section with --scanfor subcommand. If not I can send you a working one.

BTW I did a run over the 29-clue pattern above and found there are sufficient easy puzzles to start the patterns game from, and also that there is no plenty of hard diamonds as Mike said. It also has 16 symmetries so 4 grids per second were processed.

Cheers,
M.

[dobrichev]

what I have shown is that the diagonal patterns have more puzzles than random patterns with the same number of clues....... this probably means that there will be more hard puzzles.

I didn't follow your calculations, but you shouldn't compare "diagonal and symmetrical" patterns with "random non-symmetrical" w/o rescaling, because each pattern symmetry halves the number of ED puzzles.

[coloin]

i know that each pattern symmetry reduces by 2 the number of ED puzzles.
But I was running one mask over a large number of ED grids - looking for the rare case that the mask found a valid puzzle - so i couldnt generate an isomorph.

Well scanning a whole ED solution grid ... ....that would work and that was the other way that i thought it could be done. That is one clever program !

In your example you have found approx 36 25-clue puzzles per grid
- but the pattern has diagonal symmetry ...that would give 18 * 5e9 total ED puzzles for that pattern [approx]. [ or 36 * 5e9 if your program has screened out the isomorphs]

But those 84 grids are hardly random

i will repeat if I can ....

C