## 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

PET, wow. I was aware of it but never had cause to learn & apply it. I'm impressed!
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Number of non equivalent patterns having N clues

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

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: 743
Joined: 01 June 2010
Location: Russia

### Re: Number of non equivalent patterns having N clues

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: 4733
Joined: 06 December 2005
Location: Paris, France

### Re: Number of non equivalent patterns having N clues

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: 743
Joined: 01 June 2010
Location: Russia

### Re: Number of non equivalent patterns having N clues

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

### Re: Number of non equivalent patterns having N clues

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: 743
Joined: 01 June 2010
Location: Russia

### Re: Number of non equivalent patterns having N clues

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.....X22  ............................................X..X..X.................X.....X....X.23  ............................................X..X..X.................X....X......X24  ............................................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: 2008
Joined: 05 May 2005

### Re: Number of non equivalent patterns having N clues

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

Previous