Sudoku Enumeration Problem

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

continum

Postby StrmCkr » Tue Jan 09, 2018 2:40 am

Code: Select all
123|456|789
45*|***|***
***|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|789
45F|DDD|EEE
CCC|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|789
45F|DDD|EEE
CCC|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|789
45F|DDD|EEE
CCC|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|789
45F|DDD|EEE
CCC|AAA|BBB
-----------
2HH|FFF|GGG
J**|***|***
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.
User avatar
StrmCkr
 
Posts: 879
Joined: 05 September 2006

Re: Sudoku Enumeration Problem

Postby coloin » Wed Sep 26, 2018 8:32 pm

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

Re: Sudoku Enumeration Problem

Postby Serg » Thu Sep 27, 2018 8:38 pm

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

Re: Sudoku Enumeration Problem

Postby coloin » Fri Sep 28, 2018 9:08 pm

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

Re: Sudoku Enumeration Problem

Postby StrmCkr » Mon Oct 01, 2018 6:55 am

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|789
45F|DDD|EEE
CCC|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.
User avatar
StrmCkr
 
Posts: 879
Joined: 05 September 2006

Re: Sudoku Enumeration Problem

Postby coloin » Sat Oct 06, 2018 12:27 am

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

Re: Sudoku Enumeration Problem

Postby coloin » Sat Oct 06, 2018 6:04 pm

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

Previous

Return to General