## Number of minimal puzzles per ED valid pattern with N clues

Everything about Sudoku that doesn't fit in one of the other sections

### Number of minimal puzzles per ED valid pattern with N clues

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
coloin

Posts: 1877
Joined: 05 May 2005

### Re: Number of minimal puzzles per ED valid pattern with N cl

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

M

m_b_metcalf
2017 Supporter

Posts: 10784
Joined: 15 May 2006
Location: Berlin

### Re: Number of minimal puzzles per ED valid pattern with N cl

coloin wrote: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
champagne
2017 Supporter

Posts: 7138
Joined: 02 August 2007
Location: France Brittany

### Re: Number of minimal puzzles per ED valid pattern with N cl

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

Posts: 1877
Joined: 05 May 2005

### Re: Number of minimal puzzles per ED valid pattern with N cl

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

Posts: 1877
Joined: 05 May 2005

### Re: Number of minimal and nonminimal puzzles per ED pattern

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
`2977232830386103728633504 30972i 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

Posts: 1877
Joined: 05 May 2005

### Re: Number of minimal / non-minimal puzzles per ED pattern

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 `
coloin

Posts: 1877
Joined: 05 May 2005

### Re: Number of minimal and nonminimal puzzles per ED pattern

coloin wrote: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

m_b_metcalf
2017 Supporter

Posts: 10784
Joined: 15 May 2006
Location: Berlin

### Re: Number of minimal puzzles per ED valid pattern with N cl

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.203#..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.606#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.108#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

Posts: 1877
Joined: 05 May 2005

### Re: Number of minimal puzzles per ED valid pattern with N cl

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
coloin

Posts: 1877
Joined: 05 May 2005

### Re: Number of minimal puzzles per ED valid pattern with N cl

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?
dobrichev
2016 Supporter

Posts: 1779
Joined: 24 May 2010

### Re: Number of minimal puzzles per ED valid pattern with N cl

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
coloin

Posts: 1877
Joined: 05 May 2005

### Re: Number of minimal puzzles per ED valid pattern with N cl

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
2016 Supporter

Posts: 1779
Joined: 24 May 2010

### Re: Number of minimal puzzles per ED valid pattern with N cl

coloin wrote: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.
dobrichev
2016 Supporter

Posts: 1779
Joined: 24 May 2010

### Re: Number of minimal puzzles per ED valid pattern with N cl

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
Last edited by coloin on Mon Feb 01, 2016 1:34 am, edited 1 time in total.
coloin

Posts: 1877
Joined: 05 May 2005

Next