Number of non equivalent patterns having N clues

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

Re: Number of non equivalent patterns having N clues

Postby Red Ed » Wed Jun 05, 2013 4:42 pm

PET, wow. I was aware of it but never had cause to learn & apply it. I'm impressed! 8-)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Number of non equivalent patterns having N clues

Postby Serg » Fri Jun 07, 2013 6:44 am

Hi, Red Ed!
Red Ed wrote:PET, wow. I was aware of it but never had cause to learn & apply it. I'm impressed! 8-)

Thanks. BTW, I found excellent semestral course "Combinatorial Enumeration" on the site of The University of Western Australia (see here). Lectures 5 and 7 (presentations) by Gordon Royle are devoted to Polya Enumeration Theorem.

Serg
Serg
2018 Supporter
 
Posts: 701
Joined: 01 June 2010
Location: Russia

Re: Number of non equivalent patterns having N clues

Postby JPF » Fri Jun 07, 2013 5:38 pm

Thanks Serg for checking.

Here are # of e-d patterns having n clues in each box.

Code: Select all
   n                       Nn
                                                                 
   0                        1                                                                 
   1                      322                                                                 
   2               33,135,278                                                                 
   3           63,971,492,029                                                                 
   4        2,420,865,426,641                                                                 
   5        2,420,865,426,641                                                                 
   6           63,971,492,029                                                                 
   7               33,135,278                                                                 
   8                      322                                                                 
   9                        1     

JPF
JPF
2017 Supporter
 
Posts: 4022
Joined: 06 December 2005
Location: Paris, France

Re: Number of non equivalent patterns having N clues

Postby Serg » Sat Jun 08, 2013 11:02 pm

Hi, JPF!
I confirm your results. Well done!
JPF wrote:Here are # of e-d patterns having n clues in each box.

Code: Select all
   n                       Nn
                                                                 
   0                        1                                                                 
   1                      322                                                                 
   2               33,135,278                                                                 
   3           63,971,492,029                                                                 
   4        2,420,865,426,641                                                                 
   5        2,420,865,426,641                                                                 
   6           63,971,492,029                                                                 
   7               33,135,278                                                                 
   8                      322                                                                 
   9                        1     


Serg
Serg
2018 Supporter
 
Posts: 701
Joined: 01 June 2010
Location: Russia

Re: Number of non equivalent patterns having N clues

Postby coloin » Mon Nov 10, 2014 11:17 pm

Well it seems that if you don't have an empty box there are large reductions in the possibilities
Code: Select all
1 clue in one box  - 1 pattern                             
3 clues in a band  - one clue in a box - 3 patterns   
6 clues in 2 bands - one clue in a box - 36 patterns 
8 clues in 8 boxes - 385 patterns                     
9 clues in 9 boxes - 322 patterns
C
Last edited by coloin on Tue Nov 11, 2014 10:53 pm, edited 1 time in total.
coloin
 
Posts: 1877
Joined: 05 May 2005

Re: Number of non equivalent patterns having N clues

Postby Serg » Tue Nov 11, 2014 12:41 pm

Hi, coloin!
coloin wrote:Well it seems that if you don't have an empty box there are large reductions in the possibilities
Code: Select all
...
6 clues in 2 bands - one clue in a box - 32 patterns 
...

I think there are 22 essentially different patterns containing 1 clue per box for the first 6 boxes (B1-B6) and 9 clues per boxes for boxes B7-B9 (see thread One-clue-boxes patterns.

Serg
Serg
2018 Supporter
 
Posts: 701
Joined: 01 June 2010
Location: Russia

Re: Number of non equivalent patterns having N clues

Postby coloin » Tue Nov 11, 2014 10:10 pm

Well ..... I thought I just mis-typed but I indeed missed a few
Here are 36, the first 14 have 2 empty rows in a band, followed by your 22.
Code: Select all
 1  ...............................................X..X..X....................X..X..X
 2  ...............................................X..X..X....................X..X.X.
 3  ...............................................X..X..X....................X.X..X.
 4  ...............................................X..X..X...................X..X..X.
 5  ...............................................X..X..X.................X..X..X...
 6  ...............................................X..X..X.................X..X.X....
 7  ...............................................X..X..X.................X.X..X....
 8  ...............................................X..X..X................X...X..X...
 9  ...............................................X..X..X................X...X.X....
10  ...............................................X..X..X................X..X..X....
11  ...............................................X..X..X........X.....X.....X......
12  ...............................................X..X..X........X.....X....X.......
13  ...............................................X..X..X........X....X.....X.......
14  ...............................................X..X..X.......X.....X.....X.......
15  ............................................X..X..X....................X..X..X...
16  ............................................X..X..X....................X..X.X....
17  ............................................X..X..X....................X.X..X....
18  ............................................X..X..X...................X...X..X...
19  ............................................X..X..X...................X...X.X....
20  ............................................X..X..X...................X..X..X....
21  ............................................X..X..X.................X.....X.....X
22  ............................................X..X..X.................X.....X....X.
23  ............................................X..X..X.................X....X......X
24  ............................................X..X..X.................X....X.....X.
25  ............................................X..X..X.................X.X..X.......
26  ............................................X..X..X................X.....X.....X.
27  ............................................X..X..X...........X.....X.....X......
28  ............................................X..X..X...........X.....X....X.......
29  ............................................X..X..X...........X....X.....X.......
30  ............................................X..X..X..........X......X.....X......
31  ............................................X..X..X..........X......X....X.......
32  ............................................X..X..X..........X.....X.....X.......
33  ...................................X.....X.....X..............X.....X.....X......
34  ...................................X.....X.....X..............X.....X....X.......
35  ...................................X.....X.....X..............X....X.....X.......
36  ...................................X.....X.....X.............X.....X.....X.......
C
coloin
 
Posts: 1877
Joined: 05 May 2005

Re: Number of non equivalent patterns having N clues

Postby coloin » Wed May 06, 2020 10:58 am

Revisiting this.....as some things don't seem to be adding up !!

Looking at the number of ED patterns for 18,19 and 20 clues that JPF calculated .....
Code: Select all
 18  184060159680       1.84e11
 19  580219975879       5.80e11
 20  1726649409444      1.72e12


number of [minimal and non minimal] puzzles per grid by Afmob
Code: Select all
        minimal        min and non-min       total [x 5e9]
  18    4.625e-01      ---                     2.3e9
  19    2.219e+03      ---                     1.1e13
| 20    3.231e+06      3.438e+06               1.7e16


I did have a go at estimating the number of puzzles per individual pattern here

Just taking a random 20C puzzle - i easily generated over one million ED puzzles with that pattern
with the above figures, 1.7e16 / 1.7e12 = 1 e4 .... which is out by a factor of 100 !!!
the 19c and 18C seem under represented too !

the number of patterns is way more than it should be .... and i can only surmise that there must be many patterns which demonstrateably cant have puzzles

just how many min lex 18 or 19 or 20 clue patterns are there from this pattern with 2 empty rows i wonder ?
Code: Select all
..................123456789961524378742183596835679142658731924374962815219845637# 2 empty rows
+---+---+---+
|...|...|...|
|...|...|...|
|123|456|789|
+---+---+---+
|961|524|378|
|742|183|596|
|835|679|142|
+---+---+---+
|658|731|924|
|374|962|815|
|219|845|637|
+---+---+---+

and there are more different patterns which are maximal [adding one more clue - gives a valid pattern]

......614......927......538...589461...372895...164273123456789985217346476893152# 3 empty boxes
........5........8..7693421..5982167..1574932..9361854..4827513..8139246123456789# blue
.....9..5.....2..3.....7..2...578436456321789873964251917285364564793128382416597# 2 clues in a band
.....1.52.....4.37.....8.91...927143...183265123456789...732514317645928254819376# serg basic magic pattern
......624......573......198......251......837..2..3946123456789746928315895137462# serg 4 nearly empty boxes
.....3.17.....8.24.....1.35...827541...615398...394276123456789679182453485739162# serg variatons
.....8.26.....7.13.....5.97....59364....82971....13258456321789392876145781594632# serg variatons
....92.87....13.64....57.39....74852....61793....38416...345678456789321873126945# serg variatons


there will be double counting with all these of course, but maybe this is the reason !
coloin
 
Posts: 1877
Joined: 05 May 2005

Previous

Return to General