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

Postby coloin » Sat Apr 11, 2015 3:21 pm

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: 1632
Joined: 05 May 2005

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

Postby m_b_metcalf » Sat Apr 11, 2015 3:46 pm

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

M
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

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

Postby champagne » Mon Apr 13, 2015 6:01 am

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: 5650
Joined: 02 August 2007
Location: France Brittany

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

Postby coloin » Thu Apr 16, 2015 9:57 pm

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: 1632
Joined: 05 May 2005

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

Postby coloin » Fri May 15, 2015 4:20 pm

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: 1632
Joined: 05 May 2005

Re: Number of minimal and nonminimal puzzles per ED pattern

Postby coloin » Fri Jan 29, 2016 12:58 am

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
 
Posts: 1632
Joined: 05 May 2005

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

Postby coloin » Fri Jan 29, 2016 1:54 am

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: 1632
Joined: 05 May 2005

Re: Number of minimal and nonminimal puzzles per ED pattern

Postby m_b_metcalf » Fri Jan 29, 2016 2:52 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

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

Postby coloin » Fri Jan 29, 2016 5:04 pm

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
 
Posts: 1632
Joined: 05 May 2005

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

Postby coloin » Sun Jan 31, 2016 4:43 pm

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: 1632
Joined: 05 May 2005

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

Postby dobrichev » Sun Jan 31, 2016 9:21 pm

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: 1311
Joined: 24 May 2010

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

Postby coloin » Sun Jan 31, 2016 9:36 pm

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: 1632
Joined: 05 May 2005

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

Postby dobrichev » Sun Jan 31, 2016 10:34 pm

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: 1311
Joined: 24 May 2010

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

Postby dobrichev » Sun Jan 31, 2016 11:08 pm

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: 1311
Joined: 24 May 2010

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

Postby coloin » Sun Jan 31, 2016 11:41 pm

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: 1632
Joined: 05 May 2005

Next

Return to General