## Sudoku Enumeration Problem

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

### continum

Code: Select all
`123|456|78945*|***|******|AAA|BBB-----------2..|...|......|...|......|...|...-----------...|...|......|...|......|...|...`

starting with A then B cell there is precisely 360 valid permutations to cycle through for digits

Code: Select all
`123|456|78945F|DDD|EEECCC|AAA|BBB-----------2..|...|......|...|......|...|...-----------...|...|......|...|......|...|...`

this reduces C,D,E sectors to 1 set of 3 numbers each with 6 possible arrangement {permutations}
and cell F as a single digit choice.

the first band has exactly 360 * 6*6*6 *1 different unique arrangements
specifically : = 77,760 different unique arrangements

add to the mixed digit cycling (1..9) and you have 77,760 * 9! ==> 77,760 * 362,880 =>> 28,217,548,800 arrangements for band 1.

2nd stage
Code: Select all
`123|456|78945F|DDD|EEECCC|AAA|BBB-----------2HH|FFF|GGG...|...|......|...|...-----------...|...|......|...|......|...|...`

cycle the combinations of 3 digits from 13456789 for section F cycling each of the 6 potential permutation of that combination removing line of sight permutations that are invalid.
cycle the combinations of 3 digits from (13456789 - selection F) for position G then cycle each of the 6 potential permutations
that leaves H locations as pair of digits {fixed or not}

this is where we note a problem carrying forward

best illustrated with examples.

Stage three problem and solution:

Code: Select all
`123|456|78945F|DDD|EEECCC|AAA|BBB-----------2HH|FFF|GGG***|***|******|iii|***-----------...|...|......|...|......|...|...`

the problem arise from selection of combination of valid numbers In i

Code: Select all
`.---------------------------.---------------------.------------------------.| 1       2        3        | 4      5      6     | 7       8       9      || 4       5        6789     | 19     17     179   | 23      236     236    || 679     679      679      | 3      2      8     | 4       1       5      |:---------------------------+---------------------+------------------------:| 2       13       1        | 7      9      4     | 6       5       8      || 568     68       568      | 12     13     123   | 9       479     47     || 79      479      479      | 6      8      5     | 123     23      123    |:---------------------------+---------------------+------------------------:| 356789  1346789  12456789 | 12589  13467  12379 | 123589  234679  123467 || 356789  1346789  12456789 | 12589  13467  12379 | 123589  234679  123467 || 356789  1346789  12456789 | 12589  13467  12379 | 123589  234679  123467 |'---------------------------'---------------------'------------------------'`

take the above grid, selection i matches selection h's combination set. {658} that leaves a combination set of 123 in the middle row.

when we choose "I" as 123 the middle row is always left as 658! meaning row 4 and 5 can be swapped and will off set the solution count. by a factor of 2.
Code: Select all
`.---------------------------.---------------------.------------------------.| 1       2        3        | 4      5      6     | 7       8       9      || 4       5        6789     | 9      17     179   | 23      236     236    || 679     679      679      | 3      2      8     | 4       1       5      |:---------------------------+---------------------+------------------------:| 2       13       1        | 7      9      4     | 6       5       8      || 79      479      479      | 568    68     5     | 123     23      123    || 56      68       568      | 1      3      2     | 9       479     47     |:---------------------------+---------------------+------------------------:| 356789  1346789  12456789 | 25689  14678  13579 | 123589  234679  123467 || 356789  1346789  12456789 | 25689  14678  13579 | 123589  234679  123467 || 356789  1346789  12456789 | 25689  14678  13579 | 123589  234679  123467 |'---------------------------'---------------------'------------------------'`

a solution is the use a Combination set and Fix the last 5 positions for col 1. {instead of permutations.}

that way each potential permutation can only be applied to each row once in rows 5,6 and again for rows 678 if we don't fix all 5 spots we also have a 3! row swap problem in the last band.

Stage three:
Code: Select all
`123|456|78945F|DDD|EEECCC|AAA|BBB-----------2HH|FFF|GGGJ**|***|***J**|iii|***-----------K..|...|...K..|...|...K..|...|...`

J is a fixed Combination of 2 digits selected from ([1,2,3,4,5,6,7,8,9] - ([1,4,2] + [active digit in R3C1 of C if single, else j cannot reduce R3C1 to [] ]))
where R56C1 <> digits from [h] {as H is always a pair of locked digits}
solving R56C1 in sequential order

K is a fixed Combination of 3 digits selected from ([1,2,3,4,5,6,7,8,9] - ([1,4,2] + [active digit in R3C1 of C if single else j+F cannot reduce R3C1 to []] + step above))
solving R789C1 in sequential order

then proceed to select a 3 digit combinations for "i" as ( [1,2,3,4,5,6,7,8,9] - (f + R6C1)) and cycle the 6 permutations.
which leaves all the *'s cells as 1 set of 3 digit each with 1-6 potential permutations.

Stage 4, to be continued.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 904
Joined: 05 September 2006

### Re: Sudoku Enumeration Problem

coloin wrote:A long time ago I was surprised that there were only 5 essentially different row and column combinations [not 150 !] - it looks like you found all 5
I found that 9 more clues are needed to complete to a puzzle [i could not find 8 clues]
Of course there are 81 of these combinations in each solution grid - so most solution grids should have at least one of these 5 .....

coloin wrote:interestingly, here are the 5 different rowcols

the approx incidence in 2430 rowcols was
Code: Select all
`000000001000000002000000003000000004000000005000000006000000007000000008123478569 - 80 [#1]000000001000000002000000003000000004000000005000000006000000007000000008124378569 -162 [#2]000000001000000002000000003000000004000000005000000006000000007000000008124578369 -980 [#3]000000001000000002000000003000000004000000005000000006000000007000000008127458369 -557 [#4]000000001000000002000000003000000004000000005000000006000000007000000008147258369 -651 [#5]                                                                                                                                                                        2430`

So there are 81 of these row/column crossings in each solution grid ....

The MC grid is composed of all 81 x [#5]
Code: Select all
`*-----------*        +---+---+---+                                    +---+---+---+                             |...|...|..1|        |5..|...|4.1|                                    |.7.|...|4.1|                             |...|...|..2|        |.9.|4..|..2|                                    |...|.6.|..2|                             |...|...|..3|        |..1|.8.|..3|                                    |...|...|..3|                             |---+---+---|        +---+---+---+                                    +---+---+---+                             |...|...|..4|        |.2.|9..|..4|                                    |...|..7|..4|                             |...|...|..5|        |..6|.1.|8.5|                                    |..6|...|..5|                             |...|...|..6|        |...|...|..6|                                    |3..|..1|..6|                             |---+---+---|        +---+---+---+                                    +---+---+---+                             |...|...|..7|        |...|.6.|1.7|                                    |.2.|...|..7|                             |...|...|..8|        |...|...|..8|                                    |...|...|.58|                             |147|258|369|        |147|258|369|                                    |147|258|369|                             *-----------*[#5]    +---+---+---+  MCgrid with 13 clues solving it   +---+---+---+  [#5] solved with 9 clues   `

maybe [#3] is just common and [#1] is just rare

Explain ?
coloin

Posts: 1743
Joined: 05 May 2005

### Re: Sudoku Enumeration Problem

Hi, coloin!
coloin wrote:interestingly, here are the 5 different rowcols

the approx incidence in 2430 rowcols was
Code: Select all
`000000001000000002000000003000000004000000005000000006000000007000000008123478569 - 80 [#1]000000001000000002000000003000000004000000005000000006000000007000000008124378569 -162 [#2]000000001000000002000000003000000004000000005000000006000000007000000008124578369 -980 [#3]000000001000000002000000003000000004000000005000000006000000007000000008127458369 -557 [#4]000000001000000002000000003000000004000000005000000006000000007000000008147258369 -651 [#5]                                                                                                                                                                        2430`

Interesting! But "rowcol" configuration (17 cells) resembles two-box (2 boxes sharing the same band) configuration (18 clues). There are 10 e-d two-box configurations. (Right?)

I have no explanations of rowcols' properties.

Serg
Serg
2018 Supporter

Posts: 626
Joined: 01 June 2010
Location: Russia

### Re: Sudoku Enumeration Problem

Code: Select all
`+---+---+---+|...|.95|..1||...|...|..2||.64|...|..3|+---+---+---+|...|...|..4||7..|.1.|..5||...|...|.36|+---+---+---+|...|...|2.7||..6|...|..8||123|478|569|+---+---+---+   [#1] with puzzle solved by adding 9 clues `

Well ... I think its all down to the morphing and relabeling.

If you fix column 9 - there are 6*5 * 6! ways to put a clue in row 9 = 21600

however you can swap and relabel both cols and stacks and col 7 and 8
6*6*2*2 = 144
21600/144 = 150 [the figure in Mathimagic's first post in this thread ! ]

but it boils down to 5 in the end somehow !
coloin

Posts: 1743
Joined: 05 May 2005

### Re: Sudoku Enumeration Problem

000000001000000002000000003000000004000000005000000006000000007000000008123478569 - 80 [#1]
000000001000000002000000003000000004000000005000000006000000007000000008124378569 -162 [#2]
000000001000000002000000003000000004000000005000000006000000007000000008124578369 -980 [#3]
000000001000000002000000003000000004000000005000000006000000007000000008127458369 -557 [#4]
000000001000000002000000003000000004000000005000000006000000007000000008147258369 -651 [#5]

in reverse generation these 5 should be the only configurations seen by my code that generates all grids. to show what i mean i first had to transpose the grids then do a digit swap to equate my starting position:
Code: Select all
`.---------------------------.------------------------------.------------------------------.| 1       2        3        | 4         5         6        | 7         8         9        || 4       5        6789     | 123789    123789    123789   | 1236      1236      1236     || 6789    6789     6789     | 123789    123789    123789   | 123456    123456    123456   |:---------------------------+------------------------------+------------------------------:| 2       1346789  1456789  | 1356789   1346789   1345789  | 1345689   1345679   1345678  || 356789  1346789  1456789  | 12356789  12346789  12345789 | 12345689  12345679  12345678 || 356789  1346789  1456789  | 12356789  12346789  12345789 | 12345689  12345679  12345678 |:---------------------------+------------------------------+------------------------------:| 356789  1346789  12456789 | 12356789  12346789  12345789 | 12345689  12345679  12345678 || 356789  1346789  12456789 | 12356789  12346789  12345789 | 12345689  12345679  12345678 || 356789  1346789  12456789 | 12356789  12346789  12345789 | 12345689  12345679  12345678 |'---------------------------'------------------------------'------------------------------'`

your posted 5 grids changed to match. {to show how i did it exta same steps on each of the 5 grids }
000000001000000002000000003000000004000000005000000006000000007000000008123478569

transpose (anti diagonal)
digit swaps
1 -> 9
8 -> 2
7 -> 3
4 -> 6
{this is the only one of the 5 grids that needs these extra 2 steps}
5 -> 6
Col swap: 5 -> 6

Code: Select all
` 1234567894........6........2........3........5........7........8........9........`

now for the other's the same process as above generates them to these 5 grids.
Code: Select all
`1234567894........6........2........3........5........7........8........9........1234567894........6........2........3........7........5........8........9........1234567894........7........2........3........5........6........8........9........1234567894........7........2........5........6........3........8........9........1234567894........7........2........5........8........3........6........9........`

alright I can explain this pretty easy now that i have it converted to match my grid generator and can also figure out how it is 5 and not 10.

Code: Select all
`123|456|78945F|DDD|EEECCC|AAA|BBB-----------2..|...|......|...|......|...|...-----------...|...|......|...|......|...|...`

the first band has exactly 360 * 6*6*6 *1 different unique arrangements
specifically : = 77,760 different unique arrangements

on inspection this number appears correct... it actually isn't.
{my initial calculations failed to realize that if CCC = 789, then there is actually only 1 unique arrangement and 3 permutations.

that means CCC+F is a quad set of 6789 digits where F can be any of the 4,

however CCC can assign 6 to any of the spots, where the position of the "2/3 of 789" can be directly swapped with each-other.

which means R3C1 HAS 2 CHOICES.
6 OR 7

{where my initial calculations has 4 permutations for what could be in R3C1. }
indicating that for each of the 77,760 arrangements on Col 1 has 10 configurations.

now the fun part.
R4C2 is fixed as a 2.

if we choose 6 at r3C3
I know that these 3 digit sets are swap-able with them selves.
[789 ]
[123]
[456]

and that 5 can only exists in box 4 or box 6
with exactly enough cells that 789 exists together or can rotate through
and that 2-3 can freely swap to change box 4-7 to be identical in all arrangements
= 2 ways to place digit 5.

if we choose 6 @ R3C3 then Digit 5 is locked to box 4 or 7. {2 choices} -> 2 potential arrangements

if we choose 7 @ R3C3 then Digit 6 is locked to box 4 or 7 { 2 choices} & Digit 5 is locked to box 4 or 7. {2 choices} => 3 potential arrangement of both digits

{either 5 is paired with 6, alone, or with 8. doesn't matter which configuration as they can swap to form one another => 3 different arrangements}

so yah.... if u can understand this and write it out better..
this is your proof of why there is only 5 different arrangements for cols+ row.

{this potential will drastically reduce my initial calculation run time down by a huge factor}
Some do, some teach, the rest look it up.

StrmCkr

Posts: 904
Joined: 05 September 2006

### Re: Sudoku Enumeration Problem

Yes there are only 5 ED rowcols
Code: Select all
`........1........2........3........4........5........6........7........8123478569  [#1]........1........2........3........4........5........6........7........8124378569  [#2]........1........2........3........4........5........6........7........8124578369  [#3]........1........2........3........4........5........6........7........8127458369  [#4]........1........2........3........4........5........6........7........8147258369  [#5]`

in #1
Code: Select all
`+---+---+---+|...|...|..1||...|...|..2||...|...|..3|+---+---+---+|...|...|..4||...|...|..5||...|...|..6|+---+---+---+|...|...|..7|                                                                                 |...|...|..8||123|ccc|xx9|+---+---+---+ `

it easy to see that 78 has to be in ccc, leaving the 456 to be filled one way

But its not clear why there should be a paucity of #1 in the counting

Except there are only 20 ED ways to fill in this pattern
Code: Select all
`+---+---+---+|...|...|..x||...|...|..x||...|...|..x|+---+---+---+|...|...|..x||...|...|..x||...|...|..x|+---+---+---+|...|...|xxx||...|...|xxx||xxx|xxx|xxx|+---+---+---+   `

For #1, a can only be 1234 - and there is only one ED way to complete Box 9
Code: Select all
`+---+---+---+|...|...|..1||...|...|..2||...|...|..3|+---+---+---+|...|...|..4||...|...|..5||...|...|..6|+---+---+---+|...|...|aa7||...|...|aa8||123|478|569|+---+---+---+  `

here are the other ED ways
Code: Select all
`........1........2........3........4........5........6........7........8123478569   [#1]........1........2........3........4........5........6......417......328123478569     1........1........2........3........4........5........6........7........8124378569   [#2]........1........2........3........4........5........6......427......318124378569     2........1........2........3........4........5........6......147......328124378569........1........2........3........4........5........6........7........8124578369   [#3]........1........2........3........4........5........6......127......458124578369     ........1........2........3........4........5........6......157......248124578369........1........2........3........4........5........6......217......548124578369     6........1........2........3........4........5........6......417......258124578369........1........2........3........4........5........6......427......518124578369........1........2........3........4........5........6......527......148124578369........1........2........3........4........5........6........7........8127458369   [#4]........1........2........3........4........5........6......247......518127458369     ........1........2........3........4........5........6......257......148127458369     3........1........2........3........4........5........6......517......428127458369........1........2........3........4........5........6........7........8147258369   [#5]........1........2........3........4........5........6......127......458147258369........1........2........3........4........5........6......147......258147258369........1........2........3........4........5........6......217......458147258369........1........2........3........4........5........6......217......548147258369........1........2........3........4........5........6......247......158147258369     8........1........2........3........4........5........6......257......148147258369........1........2........3........4........5........6......527......148147258369........1........2........3........4........5........6......527......418147258369   `

I generated 100000 random grids and counted the rowcol.
Code: Select all
`                                                              ........1........2........3........4........5........6........7........8123478569   [#1]    4363........1........2........3........4........5........6........7........8124378569   [#2]   13315........1........2........3........4........5........6........7........8124578369   [#3]   48617........1........2........3........4........5........6........7........8127458369   [#4]   11140........1........2........3........4........5........6........7........8147258369   [#5]   22565                                                                                           100000`

We have explained why #1 has a 4.3% / 1 in 20 incidence
But #3 occurs 48% of the time despite only a 6 in 20 incidence [30%]
And #5 occurs 22% of the time despite a 8 in 20 incidence [40%]
So more explaining to do I guess !
coloin

Posts: 1743
Joined: 05 May 2005

### Re: Sudoku Enumeration Problem

Strangely enough this
Code: Select all
`+---+---+---+|...|...|..1||...|...|..2||...|...|..3|+---+---+---+|...|...|..4||...|...|..5||...|...|..6|+---+---+---+|...|...|417||...|...|328||123|478|569|+---+---+---+`

[#1] pattern with a representative box9 completed.
Despite its apparent rarity [there are 81 of these patterns in each solution grid] it was present in 967/1000 random solution grids ...

And the 6th of the [#3] patterns was present in 997/1000 random solution grids
coloin

Posts: 1743
Joined: 05 May 2005

Previous