The New Sudoku Players' Forum

[kjellfp]

OK, a minor improvement, brought me down from 7.2 seconds to 6.0. I'm running with 3GHz CPU, cygwin under WinXP.

[dukuso]

...
so you can wholeheartedly say, that the whole enumeration
only takes 8s (?)


>> Can you use this to write a program which reads sudokus and displays
>> the 6 numbers from {1,..,416} for the S-classes of their 6 chutes ?
>
>Yes.

I'd like to have that program. Is it much effort ?
Is it in C ?
Do you want any of mine for exchange ?

The same for the 6 chutes of G-classes is already at
http://magictour.free.fr/r47.exe
source attached to the executable.

The 306693(?) G-classes BTW. are already uploaded to
http://magictour.free.fr/sudogan.gz

[kjellfp]

dukuso wrote:

> so you can wholeheartedly say, that the whole enumeration
> only takes 8s (?)

6s, wholeheartedly. I now see how to improve it more, but my first attempt introduced a bug.

> I'd like to have that program. Is it much effort ?

I don't think so, but I'm going away for the weekend now, so it has to be next week.

> Is it in C ?

Yes

btw, I have an idea on how to find the number of G-classes. I'll try to implement it next week.

[dukuso]

look at this sudoku grid:

147 258 369
583 691 724
926 734 581

691 582 473
734 916 258
258 347 916

375 169 842
862 473 195
419 825 637

(gangsters: 42,5,42 - 42,1,42)


each of the 27 minirows and each of the 27 minicolumns contain
exactly one number from {1,2,3} and one from {4,5,6} and one from {7,8,9}.
This is the case, only if each of the 6 chunks is from G-class 1,5,40,or 42
out of the possible 44 classes ("gangsters") of sudoku chunks
(chunks = 3*9-bands or 9*3-stacks).
Is there a name for this ? Let me call it 3doku until someone
suggest a better name. (That's a task for Tso)

You can view this as a 3d-configuration of 81
nonattacking pieces in a 9*9*9-cube, where pieces can move
along rows,columns,piles or inside the aligned
3*3*1 or 3*1*3 or 1*3*3 boxes.
View the symbol in a cell as the z-coordinate of the piece.
So in some sense it's a more "natural" and symmetrical
arrangement than a sudoku, which would consist of
nonattacking 1*1*9,1*9*1,9*1*1,3*3*1 - pieces only.
No 48-fold cubic symmetry here.

So this variant is a sort of "symmetrized sudoku",
it's the sudoku analogy to the 6 main-classes in
latin squares - you can permute the meanings of columns,
rows, symbols. Unfortunately the blocks can't be included
in this symmetrization, they have a special role,
since one block intersects 3 rows while rows-columns
rows-symbols,symbols-columns intersect 9 times.


How many grids are there ?
I think, it's 104015259648.
That was easy to count with a straightforward backtracking program
with some symmetry reductions. Can someone confirm ?

How many equivalence classes ?
That's a task for Kjell.
I found 594, but that's less certain than the above number.
I only have these 594 as graphs ATM (105 vertices), not yet
converted to sudokus, so I can't post them.

What's the symmetry-group ? I haven't thought about it yet...
That's a task for Ed and Frazer.

What's the minimum number of clues in a puzzle ?
That's a task for Gordon and Coloin.

...


-Guenter.

[coloin]

6 seconds......
in a couple of months we will be generating 16 clue puzzles at will !!!

Interesting grid.......I thought it was similar to a grid I was thinking of [but its not]:

This is a grid which solves a "4 constraint puzzle" from tso at then end of the latin squares thread
http://www.menneske.no/sudoku/dg/3/eng/

Every clue is in a unique position in every box.......I was wondering how many grids have this property.....

But your grid almost satisfies [bar a few clues] this.

In your grid, looking at the unavoidables for two numbers there seems a lot of 4 sets
{11,12,91,92,} {26,29,36,39,} {37,39,87,89,}
{82,87,92,97,}
{11,19,31,39,} {42,43,92,93,} {67,68,87,88,}
{28,29,78,79,}
{73,79,83,89,}
{14,18,24,28,} {32,33,82,83,}
{14,16,45,46,94,95,} {22,28,32,38,} {57,59,77,79,} {61,63,81,83,}
{35,36,64,65,84,86,} {71,78,91,98,}
{15,17,35,37,} {21,23,71,73,}
{17,18,97,98,} {
{13,17,23,27,} {34,35,64,66,85,86,} {48,49,98,99,} {51,52,71,72,}
{34,36,65,66,84,85,}
{81,84,91,94,}
{15,16,44,45,94,96,} {73,76,93,96,}
{72,75,82,85,}
{24,25,54,56,75,76,}

But that either makes it easier or else impossible to construct a 16,17 or 18 or 19 clue puzzle. I will have a go.

I have more to say on these sets of unavoidables in the "minimum clues"

Edit
Here is a grid which combines 3doku and the 4th constraint

147 258 963
583 691 427
926 734 185

691 582 734
734 916 258
258 347 691

375 429 816
862 175 349
419 863 572

it has a lot of unavoidables too

[Moschopulus]

look at this sudoku grid:

147 258 369
583 691 724
926 734 581

691 582 473
734 916 258
258 347 916

375 169 842
862 473 195
419 825 637

The middle stack (columns 4,5,6) decomposes into three 3x3 Latin squares:
258
582
825 etc.
Each of these requires 2 clues.

In the other stacks I can find 7 mutually disjoint unavoidable sets.

{13,23,17,27}
{32,33,82,83}
{42,43,92,93}
{51,52,71,72}
{48,49,98,99}
{57,59,77,79}
{67,68,87,88}

so at least 13 clues needed.

[dukuso]

this is not a normal sudoku.

When you solve such a puzzle you can rely on the fact
that there must be 123,456,789 in each minirow and minicolumn.
This should give puzzles with fewer clues

[coloin]

Thankyou Mosch - either grid doesnt look good for getting even a 17 under normal 3 constraint sudoku.

The addition of furthur constraints may give us puzzles with fewer clues - that is not in doubt.

The two extra constraints:
[1] one of each 123,456,789 in a mini colum/row
[2] each clue in a set position in a box

did seem to be similar in many ways

For what its worth - In constructing several grids with constraints [2] there did not seem to be many - perhaps only 1 or 2 [0 or 1 with [1]] with each valid B12347.

[kjellfp]

The newest version of my program now confirms the number of sudoku grids in 2.8 seconds. I don't think I'll work on it any more from now on.

dukuso, I have created and tested the code you wanted to find a {1..416}-class of a row. It returns the correct answer for the one row I bothered to check out, so I'm pretty sure it's correct.

I don't have a website yet to put it on. Give me your email-address, and I'll send it to you tomorrow.

BTW, it was worth the effort writing the code. It shows that my idea about signatures is overkill, the code I just wrote is faster.

[jayanth]

Here is an alternate way of arriving at 2612736 combos for (B1,B2,B3). This method also individually calculates number of possibilities for B2 and for B3. Please see Note #1 towards the end - shouldn't it be divisible as noted?



* First, some basics for notational purposes. Divide the 9x9 SuDoku into nine 3x3 blocks:
B1 | B2 | B3
B4 | B5 | B6
B7 | B8 | B9

* SuDoku constraints:
Row: each and every row contains every digit from 1 to 9. Hence, each digit from 1 to 9 can occur only once along a row.
Column: each and every column contains every digit from 1 to 9. Hence, each digit from 1 to 9 can occur only once along a column.
Block: each and every 3x3 block contains every digit from 1 to 9. Hence, each digit from 1 to 9 can occur only once in a block.

* There exist 9! (9P9) combinations for filling block B1.

* Let us determine number of possibilities for B2. First, let B1 be denoted as follows:
R1 | R1 | R1
R2 | R2 | R2
R3 | R3 | R3
R1, R2, R3 belong to the set [1,9] with the constraint that each number in the set is represented only once in the block (SuDoku 3x3 block constraint).

* Now, the first row of B2 cannot have any of the R1 (SuDoku row constraint).
It can have elements only from R2 or R3.
Further, the first row can have {none, one, two, three} R3 with the rest of the elements filled by R2.
This leads to only four possible variations for B2 as shown below, discounting the permutations in a row of B2.
Based on row one of B2, the SuDoku block constraint results in a single variant for rows two and three for B2.

Combo1:
R1 | R1 | R1 || R2 | R2 | R2 Row two of B2 cannot have R3 due to SuDoku's row constraint.
R2 | R2 | R2 || R3 | R3 | R3
R3 | R3 | R3 || R1 | R1 | R1

Combo2:
R1 | R1 | R1 || R2 | R2 | R3
R2 | R2 | R2 || R1 | R3 | R3
R3 | R3 | R3 || R1 | R1 | R2

Combo3:
R1 | R1 | R1 || R2 | R3 | R3
R2 | R2 | R2 || R1 | R1 | R3
R3 | R3 | R3 || R1 | R2 | R2

Combo4:
R1 | R1 | R1 || R3 | R3 | R3
R2 | R2 | R2 || R1 | R1 | R1
R3 | R3 | R3 || R2 | R2 | R2

Note the symmetry of Combo1 and Combo4 and the symmetry of Combo2 and Combo3.

* Lets calculate the possible permutations for B2.

* Let's consider Combo2, since Combo3 is symmetrical. For row one of Combo2, there are 3C2 ways of selecting R2 and 3C1 ways of selecting R3. And there are 3! ways of permuting (R2,R2,R3). Hence the number of possibilities for row one equals ( 3C2 * 3C1 * 3! ).

* For row two, there are 3C1 ways of selecting R1. R2 and R3 for rows two and three of B2 are already constrained by row one of B2. And there are 3! ways of permuting (R1,R3,R3). Hence the number of possibilities for row one equals ( 3C1 * 3! ).

* Hence the number of possiblilities for Combo2 or Combo3 equals the product of the possibilities for each row i.e. ( 3C2 * 3C1 * 3! ) * ( 3C1 * 3! ) * 3!. This can be expressed as (3!)^3 * ( 3C2 * 3C1^2 )

* Combo1 and Combo4 can each have (3!)^3 permutations. In this case, the question of selecting elements of R1, R2, R3 does not arise.

* Hence the number of possibilitied for B2 equals (3!)^3 * ( 1 + 3C2 * 3C1^2 + 3C2 * 3C1^2 + 1 ) = 6^3 * 56.
Hence there are 12,096 possibilities for B2.


* Each of the above B1, B2 combinations leads to a single variant wach of B3 as shown below. Again, permutations of a single row of B3 are not shown.

Combo1:
R1 | R1 | R1 || R2 | R2 | R2 || R3 | R3 | R3
R2 | R2 | R2 || R3 | R3 | R3 || R1 | R1 | R1
R3 | R3 | R3 || R1 | R1 | R1 || R2 | R2 | R2

Combo2:
R1 | R1 | R1 || R2 | R2 | R3 || R2 | R3 | R3

R2 | R2 | R2 || R1 | R3 | R3 || R1 | R1 | R3
R3 | R3 | R3 || R1 | R1 | R2 || R1 | R2 | R2

Combo3:
R1 | R1 | R1 || R2 | R3 | R3 || R2 | R2 | R3
R2 | R2 | R2 || R1 | R1 | R3 || R1 | R3 | R3
R3 | R3 | R3 || R1 | R2 | R2 || R1 | R1 | R2

Combo4:
R1 | R1 | R1 || R3 | R3 | R3 || R2 | R2 | R2
R2 | R2 | R2 || R1 | R1 | R1 || R3 | R3 | R3
R3 | R3 | R3 || R2 | R2 | R2 || R1 | R1 | R1

Note the symmetry of B2 and B3 between Combo1 and Combo4 and between Combo2 and Combo3.

* The possibilities for each and every combo for the B3 block is (3!)^3 = 216.

* Hence the possible (B2,B3) equals 12096 * 216 = 2612736. This is the same result as that obtained by BF and FJ.

NOTE:
-----
1. The final result obtained by BF and FJ, after discounting for the 9! combos of B1, is NOT divisible by 12096, the number of possible combos for B2. That is (72^2 * 2^7 * 27704267971) is not divisible by 12096. If their result is correct, then not all B2 variants above are valid. I am not sure about this.

2. We can speak of "patterns" of (B1,B2,B3) as defined by the combos 1 through 4 above, One can pick a row of blocks or a column of blocks in the SoDuko puzzle and "fit" it to one of the patterns described above.

3. If the pattern of, say (B1,B2,B3) is known, it is possible that there may be further restrictions on the patterns in the other rows (B4,B5,B6) or (B7,B8,B9). The same holds for block of columns or for correlations between rows of blocks and columns.

-Jayanth

[kjellfp]

1. The final result obtained by BF and FJ, after discounting for the 9! combos of B1, is NOT divisible by 12096, the number of possible combos for B2. That is (72^2 * 2^7 * 27704267971) is not divisible by 12096. If their result is correct, then not all B2 variants above are valid. I am not sure about this.

Different choices for B2 might give different numbers of ways to complete the board. That's why the final answer does not have to divide 9! * 12096.

[Red Ed]

look at this sudoku grid:
...
Is there a name for this ? Let me call it 3doku until someone
suggest a better name.
...
How many grids are there ?
I think, it's 104015259648.
That was easy to count with a straightforward backtracking program
with some symmetry reductions. Can someone confirm ?

Yes, I get that too (as 6688224 * 2 * 6^5).

What's the symmetry-group ? I haven't thought about it yet...
That's a task for Ed and Frazer.

I assume it's just the usual size 3359232 group crossed with (S_3)^4 instead of S_9. That is, you relabel digits within each set {123}, {456}, {789} and also switch the sets themselves. Since 104015259648 / (3359232 * 6^4) = 23.89, which is reassuringly a little less than an integer, I'd guess there are "essentially" only 24 3doku grids.

Ed.

[Dan Hoey]

This is a grid which solves a "4 constraint puzzle" from tso at then end of the latin squares thread http://www.menneske.no/sudoku/dg/3/eng/

Every clue is in a unique position in every box.......I was wondering how many grids have this property.....

I was thinking about the symmetries of the four-constraint puzzle. The constraints are that cell contents are not repeated in any

C column,

R row,

B block, or

P position within block.

There are many fewer symmetries in this puzzle, because you can't permute three rows in one 3x9 trough independently of the rows in another trough. But there is one kind of symmetry that doesn't appear in standard Sudoku. The C and R constraints can be exchanged with the B and P constraints, resulting in a mapping

Code: Select all

            from                                 to
01 02 03  04 05 06  07 08 09        01 28 55  04 31 58  07 34 61
10 11 12  13 14 15  16 17 18        10 37 64  13 40 67  16 43 70
19 20 21  22 23 24  25 26 27        19 46 73  22 49 76  25 52 79

28 29 30  31 32 33  34 35 36        02 29 56  05 32 59  08 35 62
37 38 39  40 41 42  43 44 45        11 38 65  14 41 68  17 44 71
46 47 48  49 50 51  52 53 54        20 47 74  23 50 77  26 53 80

55 56 57  58 59 60  61 62 63        03 30 57  06 33 60  09 36 63
64 65 66  67 68 69  70 71 72        12 39 66  15 42 69  18 45 72
73 74 75  76 77 78  79 80 81        21 48 75  24 51 78  27 54 81


I make it 8 * 6^4 permutations, or 8 * n!^4 permutations for the n^2 by n^2 grid. (That is before permuting the set of cell labels, which is another factor of n^2!.)

[dukuso]

4 dimensional number place puzzle
would be :

fill a 9*9 square with numbers from {1,2,3,4,5,6,7,8,9}
such that no two cells which have the same letter
in one of the 6 arrays below may contain the same number.
Sudoku only uses the first 3 arrays below,
the 4-constrained variant above only uses the first 4 arrays below.
Are there puzzles which use all 6 arrays ?

I found 104*9! grids here.

Code: Select all


AAAAAAAAA
BBBBBBBBB
CCCCCCCCC
DDDDDDDDD
EEEEEEEEE
FFFFFFFFF
GGGGGGGGG
HHHHHHHHH
IIIIIIIII

ABCDEFGHI
ABCDEFGHI
ABCDEFGHI
ABCDEFGHI
ABCDEFGHI
ABCDEFGHI
ABCDEFGHI
ABCDEFGHI
ABCDEFGHI

AAABBBCCC
AAABBBCCC
AAABBBCCC
DDDEEEFFF
DDDEEEFFF
DDDEEEFFF
GGGHHHIII
GGGHHHIII
GGGHHHIII

ABCABCABC
DEFDEFDEF
GHIGHIGHI
ABCABCABC
DEFDEFDEF
GHIGHIGHI
ABCABCABC
DEFDEFDEF
GHIGHIGHI

AAABBBCCC
DDDEEEFFF
GGGHHHIII
AAABBBCCC
DDDEEEFFF
GGGHHHIII
AAABBBCCC
DDDEEEFFF
GGGHHHIII

ADGADGADG
ADGADGADG
ADGADGADG
BEHBEHBEH
BEHBEHBEH
BEHBEHBEH
CFICFICFI
CFICFICFI
CFICFICFI



[Red Ed]

This is a grid which solves a "4 constraint puzzle" from tso at then end of the latin squares thread http://www.menneske.no/sudoku/dg/3/eng/

I make it 8 * 6^4 permutations, or 8 * n!^4 permutations for the n^2 by n^2 grid. (That is before permuting the set of cell labels, which is another factor of n^2!.)

I got an answer about 50 million times bigger a while back ...