The New Sudoku Players' Forum

by **coloin** » Mon Nov 14, 2005 11:04 pm

Thankyou for that update

Sorry - I was way off with my "questimate" Perhaps there were more failed grids than I could have predicted.

Code: Select all: 1-- --- --- 2-- --- --- --- --- --- -1- --- --- -2- --- --- --- --- --- --- -12 --- --- --- -12 --- --- --- like this one

So for every template of the 1st clue there are 8696 ways to fill in the 2nd template.

EDIT This is wrong there are 17972 ways

The relevance is that there are these options to construct the 2nd template. Going on to the 3rd and 4th template may also need to be kept in mind.

by **Condor** » Tue Nov 15, 2005 11:47 pm

Red Ed wrote:By the former definition, I worked out a while back that there are
T(0) = 1 way of laying down no digits at all
T(1) = 46656 ways of laying down all the 1s
T(2) = 838501632 ways of laying down all the 1s,2s
T(3) = 5196557037312 ways of laying down all the 1s,2s,3s
T(4) = 9631742544322560 ways of laying down all the 1s,2s,3s,4s
T(8) = 6670903752021072936960 ways of laying down all the 1s-8s
T(9) = 6670903752021072936960 ways of laying down all the 1s-9s

Congratulations for those results Red Ed.

Here are your results factorised.

Code: Select all: T(0) = 1 T(1) = 46656 = 6^6 T(2) = 838501632 = 6^6 * 2^2 * 4493 T(3) = 5196557037312 = 6^6 * 2^2 * 3433 * 8111 T(4) = 9631742544322560 = 6^6 * 2^7 * 3 * 5 * 19 * 5659037 T(9) = 6670903752021072936960 = 6^6 * 2^14 * 3^2 * 5 * 7 * 27704267971

Red Ed wrote:My numbers could be wrong, though.

From the factorisation it looks like the numbers are correct.

[Edit]Turns out 1 was wrong. Corrected here now.

Analysis shows me that all T(n) needs a factor of 6^6 and 2^2.

by **Condor** » Thu Nov 17, 2005 3:45 am

Red Ed wrote:T(2) = 838501632 ways of laying down all the 1s,2s

Have confirmed that T(2) = 838501632.

The only thing I can add is that for every one of the 46656 templates there is 17972 ways of placing the second template.

by **Condor** » Wed Nov 23, 2005 2:16 am

dukuso wrote:46656 1-rookeries (templates) , 1 equivalence class
419250816 2-rookeries , 170 classes
866092839552 3-rookeries , 92053(?) classes

With the value for T(3) corrected your result match up. Thus:

Code: Select all: 46656 * 1! = 46656 419250816 * 2! = 838501632 866092839552 * 3! = 5196557037312

The next line should read

Code: Select all: 354937700196000 * 4! = 8518504804704000

dukuso wrote:Your numbers should be at least k! times higher for k-rookeries

These numbers show that:

S(n) * n! = T(n) where S(n) is the number of sets of templates.

Interestingly S(8) = S(9) * 9.

[Edit. More recent analysis has shown me that the number of rookeries is not equal to the number of sets of templates.]

by **Condor** » Wed Dec 14, 2005 5:48 am

dukuso wrote:46656 1-rookeries (templates) , 1 equivalence class
419250816 2-rookeries , 170 classes
866092839552 3-rookeries , 92053(?) classes
...
46656 8-rookeries , 170 classes
1 9-rookery , 1 class

A k-rookery is defined by the cells given by k numbers. In general in each sudoku grid there is k!/9!(9-k)! k-rookeries. The contents of the rookery don't matter.

While checking rookeries I have discovered some things that don't match up with the figures you give.

To show a rookery better consider the following grid

Code: Select all: 2 6 5 9 4 1 3 8 7 1 7 3 2 6 8 9 4 5 8 9 4 7 5 3 2 1 6 3 5 7 8 2 6 4 9 1 9 4 2 1 3 5 6 7 8 6 8 1 4 7 9 5 3 2 7 2 8 5 9 4 1 6 3 4 1 6 3 8 2 7 5 9 5 3 9 6 1 7 8 2 4

and marking all the numbers in the 138-set with '*' and all others with '.' we have

Code: Select all: . . . . . * * * . * . * . . * . . . * . . . . * . * . * . . * . . . . * . . . * * . . . * . * * . . . . * . . . * . . . * . * . * . * * . . . . . * . . * . * . .

Checking this rookery by computer I find that there are 10 sets of templates which can produce that rookery.

From this I also see that R(0)=R(9), R(1)=R(8), R(2)=R(7), R(3)=R(6), R(4)=R(5).

This leaves me uncertain about dukuso's figures for 2 and 3-rookeries.

Here are the number of sets of templates for each rookery for the sudoku grid given above.

Code: Select all: 1-2 1 | 2-4 1 | 3-7 2 | 5-7 2 1-3 2 | 2-5 1 | 3-8 1 | 5-8 1 1-4 2 | 2-6 1 | 3-9 1 | 5-9 1 1-5 1 | 2-7 1 | 4-5 4 | 6-7 1 1-6 1 | 2-8 4 | 4-6 1 | 6-8 1 1-7 2 | 2-9 1 | 4-7 1 | 6-9 1 1-8 4 | 3-4 1 | 4-8 2 | 7-8 2 1-9 1 | 3-5 4 | 4-9 4 | 7-9 2 2-3 2 | 3-6 1 | 5-6 2 | 8-9 1 1-2-3 10 | 1-5-9 1 | 2-5-9 2 | 3-8-9 1 1-2-4 3 | 1-6-7 8 | 2-6-7 1 | 4-5-6 16 1-2-5 1 | 1-6-8 8 | 2-6-8 20 | 4-5-7 11 1-2-6 2 | 1-6-9 2 | 2-6-9 3 | 4-5-8 12 1-2-7 4 | 1-7-8 12 | 2-7-8 12 | 4-5-9 25 1-2-8 25 | 1-7-9 4 | 2-7-9 6 | 4-6-7 1 1-2-9 1 | 1-8-9 8 | 2-8-9 4 | 4-6-8 2 1-3-4 3 | 2-3-4 2 | 3-4-5 12 | 4-6-9 5 1-3-5 8 | 2-3-5 12 | 3-4-6 1 | 4-7-8 5 1-3-6 4 | 2-3-6 2 | 3-4-7 4 | 4-7-9 10 1-3-7 12 | 2-3-7 8 | 3-4-8 2 | 4-8-9 12 1-3-8 10 | 2-3-8 10 | 3-4-9 6 | 5-6-7 5 1-3-9 4 | 2-3-9 7 | 3-5-6 9 | 5-6-8 2 1-4-5 6 | 2-4-5 7 | 3-5-7 25 | 5-6-9 4 1-4-6 5 | 2-4-6 1 | 3-5-8 4 | 5-7-8 3 1-4-7 5 | 2-4-7 3 | 3-5-9 9 | 5-7-9 6 1-4-8 27 | 2-4-8 10 | 3-6-7 2 | 5-8-9 2 1-4-9 12 | 2-4-9 6 | 3-6-8 3 | 6-7-8 4 1-5-6 3 | 2-5-6 8 | 3-6-9 2 | 6-7-9 4 1-5-7 3 | 2-5-7 2 | 3-7-8 6 | 6-8-9 1 1-5-8 5 | 2-5-8 5 | 3-7-9 9 | 7-8-9 6

by **dukuso** » Sat Jun 05, 2010 7:47 am

dukuso wrote:46656 1-rookeries (templates) , 1 equivalence class
419250816 2-rookeries , 170 classes
866092839552 3-rookeries , 92053(?) classes
...
46656 8-rookeries , 170 classes
1 9-rookery , 1 class

just as subsets of the 9*9.

ahhh, wrong.
This was done by joining two disjoint 1-rookeries, but several such joined pairs may give
the same 2-rookery.

So now I get 333100512 2-rookeries , the 170 clases should still be correct, but should be checked.
Also 3-rookeries,4-rookeries ...

and when counting them directly I get 737821872 2-rookeries , so there is another error somewhere.
Or are there 2-rookeries that can't be solved ?

by **dukuso** » Sat Jun 05, 2010 11:57 am

> Or are there 2-rookeries that can't be solved ?

yes !

first example below. Maybe you all knew this since long ?!?

Code: Select all: +---+---+---+ |OO.|...|...| |...|OO.|...| |...|...|OO.| +---+---+---+ |OO.|...|...| |...|O..|O..| |...|..O|..O| +---+---+---+ |..O|.O.|...| |..O|...|..O| |...|..O|.O.| +---+---+---+

by **dukuso** » Sat Jun 05, 2010 12:21 pm

for a given k, 1<=k<=9, the number of sudokugrids, (~6.7e21) equals the

sum over all k-rookeries of the
number of solutions of the 9*k empty cells with symbols 1..k
multiplied with the
number of solutions of the 9*(9-k) filled/discarded cells with symbols 1..9-k
multiplied with
binomial (9,k)

As we have the gang of the 44 for sudoku-bands, we have the

gang of the 10 for 2-rookery-bands
gang of the xx for 3-rookery-bands
...

the number of ways to complete a rookery-band into a full rookery only depends
on the 9 numbers of empty cells in each of the 9 minicolumns of the rookery-band.

by **dukuso** » Sat Jun 05, 2010 3:08 pm

for the number of rookeries I get:

0-rookeries:1
1-rookeries:46656~4.7e4
2-rookeries:731659392~7.3e8
3-rookeries:398298015072~4.0e11
4-rookeries:8656620965370~8.7e12
5-rookeries:8656620965370~8.7e12
3-rookeries:398298015072~4.0e11
2-rookeries:731659392~7.3e8
1-rookeries:46656~4.7e4
0-rookeries:1

someone please confirm

the automorphismgroup has size 6^8*2=3359232, so there could be
~3M classes of 4-rookeries

by **Red Ed** » Sun Jun 06, 2010 7:11 am

What's today's definition of k-rookery ?

by **dukuso** » Sun Jun 06, 2010 7:21 am

a k-rookery is a subset of the 81 cells in a 9*9 square which contains exactly k-cells
from each row,column,block

a k-template is a k-rookery whose 9*k cells are filled with numbers from {1,2,..,k},
such that the rookery-cells from each row,column,block contain each digit from {1,..,k}
exactly once

a sudokugrid is a 9-template, there are ~6.67e21 of them

for some k-rookeries there is no k-template, for others there are many
what's the maximum number of ways(k) to fill the cells in a k-rookery
to obtain a k-template ?

(1):1
(2):16? (O..O..... O..O..... ......OO. ......OO. .O..O.... .O..O.... .....O..O ..O..O... ..O.....O)
(8):1.59e16?
(9):6.67e21

by **dobrichev** » Thu Jul 21, 2011 12:49 pm

dukuso wrote:...for some k-rookeries there is no k-template, for others there are many
what's the maximum number of ways(k) to fill the cells in a k-rookery
to obtain a k-template ?

(1):1
(2):16? (O..O..... O..O..... ......OO. ......OO. .O..O.... .O..O.... .....O..O ..O..O... ..O.....O)
(8):1.59e16?
(9):6.67e21

There are 259272 different 3-templates populating 92048 different 3-rookeries.
Any 3-template has at least one completion to a valid sudoku grid.
max_ways(3) = 1728 (......000 ...000... 000...... ......000 ...000... 000...... ......000 ...000... 000......)
min_ways(3) = 6 (fully entwined triplets :lol:

)

Below is the distribution of 3-templates by the number of valid permutations of the labels within the 3-rookery.

Code: Select all: #templ Exemplar #perm 2 ......123...123...123............231...231...312............312...312...231...... 1728 11 ......123...123...123............231..23.1...3.1..2.........312.3.21....21..3.... 792 3 ......123...123...123............231...231...312...........231....31...2231...... 576 63 ......123..1.23....23.1.......132...2.....3.131......2...2.1.3....3..21.132...... 510 17 ......123..1.23....23..1.........312.12.3.....3..12...1..2...3.2..3....13..1..2.. 432 10 ......123...123...123............231..2.31...31...2......21.3.....3...12231...... 384 36 ......123..1.23....23.1..........23121..3....3..1.2.........312..23.1...13.2..... 360 122 ......123..1.23...23.1...........231..3.12...12.3...........312..2.31...31.2..... 288 102 ......123..1.23....23.1..........23121.3.....3..1.2.......31..2...2..31.132...... 264 115 ......123..1.23....231.......231.....1.2..3...3....2.11....2.3.2...31...3......12 258 108 ......123..1.23....23.1.......132...21....3..3......12...2...31...3.12..132...... 252 110 ......123..1.23....23.1..........2312..13....31.2..........231....3.1..2132...... 240 67 ......123..1.23...23.1...........231.23.1....1..3.2.........312.1.23....3.2..1... 216 735 ......123..1.23....231.......2...3.1.1..32....3..1.2..1..2...3.2..3.1...3......12 198 279 ......123..1.23....231.......2.1.3...1.23.....3....2.11....2.3.2..3.1...3......12 192 288 ......123..1.23....23.1........32.1....1..23.132.........3.1..221....3..3..2....1 186 569 ......123..1.23....23.1.......3..21..32..1...1..2...3..1..32...2.....3.13..1....2 180 409 ......123..1.23....23.1........32.1....1..23.312.......3.2....11.....3.22..3.1... 168 486 ......123..1.23....23.1.......13...21....23..23......1...2.1.3....3..21.312...... 162 182 ......123..1.23....23.1........3.21.2....13..31...2......2...31.3.1....21.23..... 156 405 ......123..1.23....23.1.......1.23..2...3...131....2.....2.1.3....3...12132...... 150 429 ......123..1.23...23.1...........231..32.1...12..3..........312..231....31...2... 144 504 ......123..1.23...23.1..........231...3..12..1.2.3.......2...31.1.3....232..1.... 132 267 ......123..1.23...23.1..........23.1..3..1..2.12.3.....2.31....1..2...3.3.....21. 126 596 ......123..1.23...23.1........2..3.11..3....232..1......2..1.3...3...21..1..32... 120 1451 ......123..1.23...23.1.........32..1..3.1...21.2...3.....3..21..1.2...3.32...1... 108 1116 ......123..1.23...23.1..........231..2.3.1...31....2....2....31..3.1...21..23.... 102 2467 ......123..1.23...23.1.........32..1..2.1.3..1.3.....2...3..21..1.2...3.32...1... 96 3726 .....1.23..2..3..113..2.......23.1...1....23.32.1.......1..23....3....122..31.... 90 2040 ......123..1.23...23.1........2..3.11.2.3....3...1...2..3...21..1...2.3..2.3.1... 84 2063 ......123..1.23...23.1.........32..11.2...3..3...1.2.....3...12.1.2...3..23..1... 78 6601 .....1.23..2..3.1.13..2.......2..3.121.3.....3...1...2..1...23...3..21...2.13.... 72 3745 .....1.23..2.3..1..312.........12.3.2....3..131....2....312.....2.3..1..1.....3.2 66 7254 .....1.23..2..3.1.13..2.......2..13.21.3.....3...1...2..1..23....3...2.1.2.13.... 60 7923 .....1.23..2..3.1.13..2.......21..3..1.3....232....1....1..23....3...2.12..13.... 54 11439 .....1.23..2.3.1..13.2..........2.31..3.1.2..21.3..........3.12..1.2.3..32.1..... 48 8554 .....1.23..2.3..1..31..2.......1.3.2.2.3....131..2.......2..13.1....32..2.31..... 42 25121 .....1.23..2.3.1..13.2..........3.12.2.1..3..3.1.2.......31.2...13..2...2......31 36 21352 .....1.23..2.3.1..13.2.........2.31..21..3...3..1....2...3..2.1.1...2.3.2.3.1.... 30 34754 ..1..2..3.2..3..1.3..1..2....2..3..1.3..1..2.1..2..3....3..1..2.1..2..3.2..3..1.. 24 38884 ..1..2..3.2..3..1.3..1..2....2..1.3..3..2.1..1..3....2..3.1..2..1.2..3..2....3..1 18 47714 ..1..2..3.2..3..1.3..1..2....2..3..1.3..1..2.1..2..3....3.2.1...1.3....22....1.3. 12 27153 .....1.23..2.3.1..13.2.......13....2.2..1.3..3...2..1...3..2..1.1...32..2..1...3. 6

Counting the rookeries instead of templates is more correct. It will reduce the values in the leftmost column, preserving the rightmost column.

Cheers,
MD

by **dobrichev** » Thu Jul 21, 2011 2:50 pm

Distribution of 3-templates by minimal number of clues required to complete its 3-rookery.

Code: Select all: #templ Exemplar #clues 5 ......123..1.23....23..1.........231.1..32....32.1....1..2..3..2..3...1.3..1....2 6 229 ......123..1.23...23.1...........231..3.12...12.3...........312..2.31...31.2..... 5 14779 .....1.23..2.3..1..31..2.......1.3.2.2.3....131..2.......1..23.1.32.....2....31.. 4 116554 ..1..2..3.2..3..1.3..1..2....2..3..1.3..1..2.1..2..3....3..1..2.1..2..3.2..3..1.. 3 127705 ..1..2..3.2..3..1.3..1..2....2..3..1.3..1..2.1..2..3....3.2.1...1.3....22....1.3. 2

Too low average.

by **dobrichev** » Fri Jul 22, 2011 8:48 pm

There are 119,503,486 distinct 4-templates living in 2,648,604 distinct 4-rookeries (classes).

Distribution of 4-rookeries by minimal number of clues required to complete it. In contrast to the table in the above post, here rookeries are counted instead of templates.

Code: Select all: #templ Exemplar #clues 170 ....12.34.34...1.21.23.4.......2341..43..1.2.2.14..3...1.2...433...4.2.142.13.... 8 3086 ....12.34.34...1.21.234.......1.342.2.1..43..34.2...1..1.43.2...2...1.434.3.2...1 7 35675 ..1..2.34..234.1..34...12...1..2.34..2.4.3..14.3.1...2.341...2.1..2..4.32...34.1. 6 303091 ..1..2.34.2..34..13.41..2....23.14...4..2.31.13.4....2.1.2...432...431..4.3.1..2. 5 1615858 ..1..2.34.2..341..34.1....2..23.1.4..13.4.2..4..2..3.1.3..1.42.1..42...32.4..3.1. 4 690723 ..1..2.34.3..14.2.24.3..1....21.3.4..1.4..3.24.3.2...1..4.312..12..4...33..2..41. 3

by **coloin** » Sat Jul 23, 2011 5:20 pm

Excellent .... does the computation get any easier for the 5,6,7 [8,9] !!

I am confused over the difference between a rookery and a template though !!

dukuso wrote:one 9-rookery, contents don't matter.

i would say the rookery was the actual clues and the template was the position of the clue .... i think red ed did query this.
From your recent post it is clear now why there is confusion

Code: Select all: So, the number of distinct 3-templates is 259272. The first and last of them alphabetically are respectively ......123...123...123............231...231...231............312...312...312...... ..1..2..3.2..3..1.3..1..2....2..3..1.3..1..2.1..2..3....3.2.1...1.3....22....1.3. The number of 3-rookeries having at least one valid 3-template is 92048 (confirming dukuso's count). ......111...111...111............111...111...111............111...111...111...... ..1..1..1.1..1..1.1..1..1....1..1.1..1..1.1..1..1....1..1.1..1..1.1..1..1....1..1

Anyhow a while back I could only generate 181 distinct 2-rookeries/templates. dukuso would say there were 170 classes [? templates/rookeries].

Hidden Text: Show

Have I overcounted ? - using havards program - they are all ED ? :roll:

Well the bug in gsfs minlexing has surfaced again - except havards usually is reliable.....
Hmmph, here are the 11 pairs - properly minlexed. I dont know why my usually reliable sofware thinks the pairs are different though.... :?:

Hidden Text: Show

Here is #4 and #6.

Code: Select all: #4#.......12....12....12.............21...12....12............12.....2..1..2.1...... # #6#.......12....12....12.............21...12....2.1...........12.....2..1..12....... #

not sure now if they are different or not !
C

The New Sudoku Players' Forum

Fruitless Sudoku Discoveries

Re:

Re: Fruitless Sudoku Discoveries

Re: Fruitless Sudoku Discoveries

Re: Fruitless Sudoku Discoveries

Re: Fruitless Sudoku Discoveries

Re: Fruitless Sudoku Discoveries

Re: Fruitless Sudoku Discoveries

Re: Fruitless Sudoku Discoveries

4-rookeries

Re: Fruitless Sudoku Discoveries