Sudoclues: max, min, forest, leaves

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

Sudoclues: max, min, forest, leaves

Postby sg » Thu Mar 02, 2006 1:44 pm

The big open problem in the maths of Su Doku is to count the total number of proper puzzles (the number of solutions is known; proper puzzles are those with exactly one solution). Among the proper puzzles a special role is played by the irreducible puzzles (known widely on the forum as minimum puzzles). The notion of the puzzle tree and puzzle forest are useful.

Starting from any complete solution grow the complete game tree in the following recursive fashion. Note that the root of the tree, ie the complete solution, is a proper puzzle. Starting from any proper puzzle, remove entries one at a time and check whether the new puzzle is proper. If it is, then (and only then) it is a node in the graph. Draw an arrow from the starting proper puzzle to the new proper puzzle (an arrow points into every node other than the root; more than one arrow may point into a node). This directed graph I call a puzzle tree (strictly speaking this is a misnomer).

If a node on the puzzle tree has no arrow going out from it, then it is a leaf node. All leaf nodes are irreducible (in the sense that if we remove any clue from such a puzzle it is no longer a proper puzzle).

Now, all complete Su Doku solutions can be broken into disjoint orbits by the symmetry group (see Frazer for more). Taking one representative from each orbit, since they cannot be connected by a symmetry, the set is called a set of essentially different solutions. These have been counted.

The puzzle forest is the collection of puzzle trees for each member of the set of essentially different solutions. Since each node in the forest is a proper puzzle, a node belongs to only one tree (ie, different trees do not share nodes).

More details and the beginning of a formal document are available.

Various questions about the puzzle forest are interesting. A sampler:
  1. What is the minimum number of clues in the forest?
  2. What is the maximum number of clues in the leaves of the forest?
  3. Do different trees in the forest have different maxima and minima?
Bounds and partial answers to these questions are known.

I report results from the complete enumeration of the puzzle forest for Shi Doku (2X2 Su Doku). I'll give details of the programs later. In order to set out the results let me recall that there are 2 orbits of solutions: 1234341221434321 and 1234342121434312. The first row is in order, as is the first block. Since the two are distinguished by the value in the [4,4] place, I call them configurations 1 and 2 respectively. I grow the puzzle trees from these roots and find
  1. the minimum number of clues in the forest is 4
  2. the maximum number of clues in the leaves of the forest is 7
  3. on configuration 1 the minimum has 5 and the maximum leaf has 7 clues, on configuration 2 the minimum has 4 and the maximum lead has 6 clues.
  4. the total number of essentially different proper puzzles (including the two trivial: fully filled puzzles) is 84370
  5. the total number of essentially different irreducible puzzles is 1312.
  6. the total number of puzzles can be obtained from the breakup below, since one knows the structure of the orbits for this problem.

Full statistics are:
Code: Select all
Clues   All nodes               Leaves only
        conf_1  conf_2          conf_1  conf_2
16      1       1               0       0
15      16      16              0       0
14      120     120             0       0
13      560     560             0       0
12      1808    1816            0       0
11      4224    4320            0       0
10      7216    7744            0       0
 9      8848    10560           0       0
 8      7380    10884           0       0
 7      3760    8224            48      0
 6      960     4144            432     128
 5      96      960             96      576
 4      0       32              0       32
Total   34989   49381           576     736
sg
 
Posts: 22
Joined: 14 February 2006

Postby sg » Thu Mar 02, 2006 2:35 pm

Here is a brief description of the algorithm used to enumerate all essentially different Shi Doku puzzles. It is a little clunky, so I would appreciate it if someone else checks it. There are three parts to the code:
  • The solver: I have two versions, one is a (relatively slow) depth first enumeration, and the second is a simple (but fast) code which repeatedly looks for naked and hidden singles in rows, columns and blocks. In the enumeration I used the fast code, but randomly checked a very small fraction of the rejects through the slow code and found that there were no false negatives. This is my biggest worry: since I cannot prove that the second algorithm is equivalent to the first. Until then, the count of essentially different puzzles reported earlier remains a lower bound.
  • The case generator: Starting from an M*M grid, one can leave out any combination of clues, requiring a check of 2^(M*M) possibilities. The clues to be removed are encoded in the binary rep of numbers between 0 and 2^(M*M). Every zero means you retain the clue in that position, every one means remove the clue. Run the solver to check whether the puzzle is proper. Record every proper puzzle.
  • The tree analysis: run over all proper puzzles to determine mother-daughter relations and identify the leaf nodes (irreducible puzzles).

In order to make further progress steps 2 and 3 should be merged. Once a node is seen to be non-viable, there is no need to check the sub-graph rooted at that node. Also, for 3X2 Su Doku (Roku Doku) and higher, a better solver is needed since there are explicit examples where my fast solver will fail.
sg
 
Posts: 22
Joined: 14 February 2006

Postby coloin » Thu Mar 02, 2006 4:52 pm

Valient work on the 2X2 grids.......and your analogy is a very good.
It would be an enormous task to do what you have done for the 3X3 - even for one grid !
However - I think it is more relevant to only deal in terms of minimal puzzles - all minimal puzzles of a specific size [range 17-33 in the 3X3] will have a constant number of non-minimal puzzles. Besides the numbers at a guess are in the 10^40 range.

In the 2X2 case
Code: Select all
 The total number of essentially different irreducible puzzles is 1312.
Code: Select all
The total number of essentially different grids is 2 [conf_1 & conf_2]
Code: Select all
             [conf_1]    [conf_2]
clues
 7              48        0
 6             432      128
 5              96      576
 4               0       32
Total          576      736
excellent

Perhaps these figures give an indication of how big a job it is but perhaps it could be worked out for a few 3X3 grids.
Code: Select all
The total number of essentially different irreducible puzzles in any one grid is ?
Code: Select all
The total number of essentially different grids is 5472730538
Code: Select all
               SF   Random   Oceanmax1    Canon
clues   
34                              ?
33             0                8          ?
32             0                          18[correct]                 
31             0
30             1?     ?
29
28
27
26
25
24
23
22
21
20        570000
19         60000      1                   many
18           748      0         1         0                     
17            29      0         0         0
16             0      0         0         0

The grids
Code: Select all
SF         639241785284765193517983624123857946796432851458619237342178569861594372975326418
Random     123849567456217839789356124642598713971463285538172946397681452865724391214935678
Oceanmax1  127548963468391275395726814984132657216857349753469128831674592572913486649285731
Canon      123456789789123456456789123231564897564897231897231564312645978645978312978312645


dukuso wrote:counts of clues in randomly generated minimal
sudokus over sf :

average:24.104503 , 1000000 samples
19 3
20 229
21 6277
22 61494
23 227035
24 352839
25 248868
26 86121
27 15453
28 1589
29 89
30 3

An approximation would be this - although I dont know how much double counting is envolved here ! but a more conservative ratio of the 20s is 570000/229 = 2489. It indeed may be skewed more than this. However.......
Code: Select all
17 .                          29
18 .                         748
19 3                       60000             
20 229                    570000       
21 6277                 15623453
22 61494               153058566
23 227035              565090115
24 352839              878216271       
25 248868              619432452
26 86121               214355169
27 15453                38462517
28 1589                  3955021
29 89                     221521
30 3                        7467
31 .                           ?
total                 2500000000

total essentially different minimal puzzles = 10^19
Last edited by coloin on Thu Mar 02, 2006 9:17 pm, edited 1 time in total.
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby frazer » Thu Mar 02, 2006 7:25 pm

Red Ed posted a message to this forum just before it was hacked and the message disappeared; I was in the process of writing a reply with more details at exactly that moment... Anyway, he and I calculated the number of essentially different 2x3 sudoku grids; he then did the same for 2x4 grids, and started the calculation for 2x5 grids, this latter being the only other case where the complete number is believed known, I think. For the 2x3 case, there are just 49 essentially different grids (http://www.afjarvis.staff.shef.ac.uk/sudoku/sud23gp.html) and for the 2x4 case there are 1673187 (http://www.afjarvis.staff.shef.ac.uk/sudoku/sud24gp.html).
frazer
 
Posts: 46
Joined: 06 June 2005

Postby kjellfp » Thu Mar 02, 2006 8:49 pm

frazer wrote:...and started the calculation for 2x5 grids, this latter being the only other case where the complete number is believed known, I think.

The current situation about 2x5 is (as far as I know) unchanged since October 20. That is, I have calculated the number to be 1903816047972624930994913280000, but I havn't seen any confirmation yet. See Wikipedia.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Re: Sudoclues: max, min, forest, leaves

Postby Red Ed » Thu Mar 02, 2006 11:54 pm

sg wrote:Full statistics are:
I don't think this is right, as you have no 4-puzzles for config 1, whereas I claim this is one such:
Code: Select all
4-puzz      conf_1
 ....        1234
 .41.   =>   3412
 2..3        2143
 ....        4321
I think conf_1 has 41401 puzzles (284 minimal, including 4 of size 12), whereas conf_2 has 50027 (304 minimal, 128 of size 4).

A quick, and quite possibly wrong, check for isomorphic puzzles within each config suggests that conf_1 has 1465 (14 minimal) and conf_2 has 3245 (22 minimal). Obviously puzzles from different configs are not isomorphic. This implies that there are 4710 essentially different puzzles (36 minimal: 1 7-clue, 22 5-clue and 13 4-clue puzzles) on 2x2 sudokus ("shi doku") ... but I did this in a rush, so it needs checking/correcting.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Sudoclues: max, min, forest, leaves

Postby sg » Fri Mar 03, 2006 1:19 am

Red Ed wrote:... you have no 4-puzzles for config 1, whereas I claim this is one such:
Code: Select all
4-puzz      conf_1
 ....        1234
 .41.   =>   3412
 2..3        2143
 ....        4321


Your example is correct, so I have to check my programs. Please treat my numbers as lower bounds for now.

Frazer, thanks for the information on 2X3 etc.
sg
 
Posts: 22
Joined: 14 February 2006

Re: Sudoclues: max, min, forest, leaves

Postby sg » Fri Mar 03, 2006 3:27 pm

Red Ed wrote:A quick ... check for isomorphic puzzles within each config ...


Isomorphic under what?
sg
 
Posts: 22
Joined: 14 February 2006

Re: Sudoclues: max, min, forest, leaves

Postby Ocean » Fri Mar 03, 2006 4:56 pm

Red Ed wrote:I think conf_1 has 41401 puzzles (284 minimal, including 4 of size 12), whereas conf_2 has 50027 (304 minimal, 128 of size 4).

A quick, and quite possibly wrong, check for isomorphic puzzles within each config suggests that conf_1 has 1465 (14 minimal) and conf_2 has 3245 (22 minimal). Obviously puzzles from different configs are not isomorphic. This implies that there are 4710 essentially different puzzles (36 minimal: 1 7-clue, 22 5-clue and 13 4-clue puzzles) on 2x2 sudokus ("shi doku") ... but I did this in a rush, so it needs checking/correcting.

sg wrote:Isomorphic under what?


Two sudokus S1 and S2 are isomorphic if there exists a symmetry op g that transforms S1 into S2 (S2=g*S1).

Let H={h1,h2, ... hn} be the set of symmetry ops that fixes a grid G. (For simplicity let the identity op be part of H).

:idea: Proposition: The following is valid for sudoku grids of any size.
1. If f and g are two members of H, then h=f*g is also in H. [Here f*g means the successive application of the two symmetry ops]
2. The set H is a group of size n.
3. A sudoku S in G may or may not be fixed by one of the symmetry ops in H.
4. No other symmetry ops than the set H can fix a sudoku S (in G).
5. If a0 is the number of nonisomorhpic sudokus in G, and b0 is the total number of sudokus in G, then b0<=n*a0.
6. If a1 is the number of nonisomorhpic sudokus with k clues in G, and b1 is the total number of sudokus with k clues in G, then b1<=n*a1.
7. If a3 is the number of minimal nonisomorhpic sudokus in G, and b3 is the total number of minimal sudokus in G, then b3<=n*a3.

C1: The number of symmetry ops that fixes conf_1 is 32 (including the identity op).
C2: The number of symmetry ops that fixes conf_2 is 16 (including the identity op).

If any of these propositions are not consistent with the counting, either the proposition is false, or the counting is wrong.

[Edit: The original word "conjecture" is replaced with "proposition".]
Last edited by Ocean on Sun Mar 05, 2006 7:17 am, edited 1 time in total.
Ocean
 
Posts: 442
Joined: 29 August 2005

Re: Sudoclues: max, min, forest, leaves

Postby Red Ed » Fri Mar 03, 2006 7:44 pm

sg wrote:Isomorphic under what?
Under the usual group of validity-preserving transforms, which in this case is generated by
  • reordering columns 1<->2 or 3<->4 or (1,2)<->(3,4)
  • reordering rows similarly
  • transposition
  • relabelling digits
This is a group of order 128 x 4! with 20 conjugacy classes, 13 of which have some essentially-invariant grids, leading to 2 essentially different grids overall (as everyone knows).

Here are the 36 minimal puzzles that I found.
Code: Select all
+----+    +----+    +----+    +----+    +----+    +----+
|....|    |....|    |....|    |....|    |....|    |....|
|...1|    |...1|    |...1|    |...1|    |...1|    |..12|
|.1.2|    |.12.|    |.2..|    |.2..|    |.2..|    |....|
|3...|    |.3..|    |.3.4|    |.32.|    |3.4.|    |13..|
+----+    +----+    +----+    +----+    +----+    +----+


+----+    +----+    +----+    +----+    +----+    +----+
|....|    |....|    |....|    |....|    |....|    |...1|
|.1.2|    |.1.2|    |.1.2|    |.1.2|    |.1.2|    |.1..|
|....|    |....|    |....|    |....|    |..3.|    |..2.|
|.34.|    |1.3.|    |2.3.|    |3.4.|    |4...|    |3...|
+----+    +----+    +----+    +----+    +----+    +----+


+----+    +----+    +----+    +----+    +----+    +----+
|...1|    |....|    |....|    |....|    |....|    |....|
|.2..|    |...1|    |...1|    |...1|    |...1|    |..12|
|..3.|    |.1.2|    |.12.|    |.2..|    |.2.3|    |.1.3|
|4...|    |.2.3|    |2..3|    |31.2|    |3.1.|    |3...|
+----+    +----+    +----+    +----+    +----+    +----+


+----+    +----+    +----+    +----+    +----+    +----+
|....|    |....|    |....|    |....|    |....|    |....|
|..12|    |..12|    |..12|    |.1.2|    |.1.2|    |.1.2|
|.1.3|    |.13.|    |.13.|    |....|    |....|    |....|
|4...|    |.4..|    |3...|    |.213|    |.231|    |.321|
+----+    +----+    +----+    +----+    +----+    +----+


+----+    +----+    +----+    +----+    +----+    +----+
|....|    |....|    |....|    |...1|    |...1|    |...1|
|.1.2|    |.1.2|    |.1.2|    |..2.|    |..2.|    |..2.|
|...3|    |..2.|    |..2.|    |.1..|    |.1..|    |.1..|
|.24.|    |1..3|    |3..1|    |2..3|    |23..|    |3..2|
+----+    +----+    +----+    +----+    +----+    +----+


+----+    +----+    +----+    +----+    +----+    +----+
|...1|    |...1|    |...1|    |...1|    |...1|    |....|
|..2.|    |..2.|    |..2.|    |..2.|    |.12.|    |..12|
|.1..|    |.1..|    |.3..|    |.3..|    |...2|    |.1.3|
|32..|    |34..|    |4..2|    |41..|    |3...|    |.32.|
+----+    +----+    +----+    +----+    +----+    +----+

Ocean wrote::idea: Conjecture: The following is valid for sudoku grids of any size. ...
Yes, all these are true (I'm sure you knew this; in which case "proposition" would have been a better word than "conjecture"). Your 5/6/7, with your C1/C2, are a handy check on my full results from last night, which I'll now share in tedious detail ...

First, minimal puzzles:
Code: Select all
----- Config 1 -----        ----- Config 2 -----
Clues Puzzles Orbits        Clues Puzzles Orbits
--------------------        --------------------
   4      12      2            4     128     11
   5     256     11            5     176     11*
   6      16      1         --------------------
--------------------        Total    304     22
Total    284     14
The star (*) indicates that your bound on the number of non-isomorphic puzzles is attained, i.e. none of that particular type have any symmetries.

Now the results for all puzzles:
Code: Select all
----- Config 1 -----        ----- Config 2 -----
Clues Puzzles Orbits        Clues Puzzles Orbits
--------------------        --------------------
  16       1      1           16       1      1
  15      16      1           15      16      1*
  14     120      9           14     120     13
  13     560     21           13     560     35*
  12    1812     77           12    1816    133
  11    4272    144           11    4320    270*
  10    7480    270           10    7744    518
   9    9696    320            9   10560    660*
   8    9064    323            8   10890    717
   7    5760    194            7    8272    517*
   6    2208     87            6    4320    289
   5     400     16            5    1280     80*
   4      12      2            4     128     11
--------------------        --------------------
Total  41401   1465         Total  50027   3245
Lots more stars in that one (at least for odd-clued puzzles in config 2).
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Sudoclues: max, min, forest, leaves

Postby sg » Sat Mar 04, 2006 12:09 am

My program had a bug due to some pointers being overwritten in the computation of which cell belongs to which block. As a result, the checks for uniqueness in a block were not being properly applied. The corrected results below.

Code: Select all
N_clue  All nodes               Leaves
        conf_1  conf_2          conf_1  conf_2
16      1       1               0       0
15      16      16              0       0
14      120     120             0       0
13      560     560             0       0
12      1812    1816            0       0
11      4272    4320            0       0
10      7480    7744            0       0
 9      9696    10560           0       0
 8      9064    10890           0       0
 7      5760    8272            0       0
 6      2209    4320            16      0
 5      416     1280            256     176
 4      12      128             12      128
Total   41401   50027           284     304


Red Ed's gone one better than me by factoring out the little group of the orbit. I haven't implement that yet.

Another sidelight: I stuck to my fast generator. So this provides (a very inelegant) proof that repeated elimination suffices to solve Shi Doku.
sg
 
Posts: 22
Joined: 14 February 2006

Re: Sudoclues: max, min, forest, leaves

Postby Ocean » Sun Mar 05, 2006 11:11 am

Red Ed wrote:
Ocean wrote::idea: Conjecture: The following is valid for sudoku grids of any size. ...
Yes, all these are true (I'm sure you knew this; in which case "proposition" would have been a better word than "conjecture"). Your 5/6/7, with your C1/C2, are a handy check on my full results from last night, which I'll now share in tedious detail ...


Thank you for the results. (I agree with you that "proposition" is a better word than "conjecture", and have changed the previous post accordingly).


The set of symmetry ops for conf_1 is a group of order 32. It is isomorphic to Z2 x Z2 x Z2 x Z2 x Z2, and can be written as
H1={1,s,t,u,v,w,st,su,sv,sw,tu,tv,tw,uv,uw,vw,stu,stv,stw,suv,suw,svw,tuv,tuw,tvw,uvw,stuv,stuw,stvw,suvw,tuvw,stuvw} for some suitable choice of s, t, u, v and w.

The set of symmetry ops for conf_2 is a group of order 16. It is isomorphic to Z2 x Z2 x Z2 x Z2, and can be written as
H2={1,a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd} for some suitable choice of a, b, c and d.


Code: Select all
The group table (Cayley table) for H2 (symmetry ops of conf_2):

    |1   |a   |b   |c   |d   |ab  |ac  |ad  |bc  |bd  |cd  |abc |abd |acd |bcd |abcd|
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
1   |1   |a   |b   |c   |d   |ab  |ac  |ad  |bc  |bd  |cd  |abc |abd |acd |bcd |abcd|
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
a   |a   |1   |ab  |ac  |ad  |b   |c   |d   |abc |abd |acd |bc  |bd  |cd  |abcd|bcd |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
b   |b   |ab  |1   |bc  |bd  |a   |abc |abd |c   |d   |bcd |ad  |ad  |abcd|cd  |acd |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
c   |c   |ac  |bc  |1   |cd  |abc |a   |acd |b   |bcd |d   |ab  |abcd|ad  |bd  |abd |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
d   |d   |ad  |bd  |cd  |1   |abd |acd |a   |bcd |b   |c   |abcd|ab  |ac  |bc  |abc |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
ab  |ab  |b   |a   |abc |abd |1   |bc  |bd  |ac  |ad  |abcd|c   |d   |bcd |acd |cd  |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
ac  |ac  |c   |abc |a   |acd |bc  |1   |cd  |ab  |abcd|ad  |b   |bcd |d   |abd |bd  |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
ad  |ad  |c   |abd |acd |a   |bd  |cd  |1   |abcd|ab  |ac  |bcd |b   |c   |abc |bc  |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
bc  |bc  |abc |c   |b   |bcd |ac  |ab  |abcd|1   |cd  |bd  |a   |acd |abd |d   |ad  |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
bd  |bd  |abd |d   |bcd |b   |ad  |abcd|ab  |cd  |1   |bc  |acd |a   |abc |c   |ac  |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
cd  |cd  |acd |bcd |d   |c   |abcd|ad  |ac  |bd  |bc  |1   |abd |abc |a   |b   |ab  |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
abc |abc |bc  |ac  |ab  |abcd|c   |b   |bcd |a   |acd |abd |1   |cd  |bd  |ad  |d   |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
abd |abd |bd  |ad  |abcd|ab  |d   |bcd |b   |acd |a   |abc |cd  |1   |bc  |ac  |c   |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
acd |acd |cd  |abcd|ad  |ac  |bcd |d   |c   |abd |abc |a   |bd  |bc  |1   |ab  |b   |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
bcd |bcd |abcd|cd  |bd  |cd  |acd |abd |abc |d   |c   |b   |ad  |ac  |ab  |1   |a   |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
abcd|abcd|bcd |acd |abd |abc |cd  |bd  |bc  |ad  |ac  |ab  |d   |c   |b   |a   |1   |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+


The Cayley table for H1 (Z2 x Z2 x Z2 x Z2 x Z2) is the similiar kind for 32 elements.

Assignment of symmetry ops (examples):
Code: Select all
For conf_1, we may select two of the symmetry ops as s and w, and calculate s*w:
s:   C(2143), R(3412)              [swap col 1<->2 and 3<->4, swap rows 12<->34]
w:   T, D(1324)                    [swap rows and cols, swap digits 2<->3]
sw=  T, C(2143), R(3412), D(1324)

Similarly, we may (for conf_2) select symmetry ops a and b, and calculate a*b:
a:   C(2143), R(3412)     
b:   C(3412), R(4321), D(1243)
ab=  C(4321), R(2143), D(1243)

[I might need som advice on notation here ... is there any established way of writing equivalence operations?]


Finally, two new conjectures:

Let H be the set of symmetry ops that fixes a grid G (including the identity op). The following is valid for sudoku grids of any size: [Edit: False for 'any' size.]
:idea:Conjecture 1. All symmetry ops in H are self-inversive, that is h*h=1 for all h in H.
:idea:Conjecture 2. H is a group of order 2^m (for some m), and is always isomorphic to (Z2)^m (when m>0).
Last edited by Ocean on Sun Mar 05, 2006 6:58 pm, edited 2 times in total.
Ocean
 
Posts: 442
Joined: 29 August 2005

Re: Sudoclues: max, min, forest, leaves

Postby sg » Sun Mar 05, 2006 11:38 am

Ocean wrote:Let H be the set of symmetry ops that fixes a grid G (including the identity op). The following is valid for sudoku grids of any size:
:idea:Conjecture 1. All symmetry ops in H are self-inversive, that is h*h=1 for all h in H.
:idea:Conjecture 2. H is a group of size 2^m, and is always isomorphic to (Z2)^m (for some m).


Conjecture 2 implies 1. Look at the subgroups of SD(R,C) which are not Z_2. These are
  • a C_4 for 90 degree rotations of the square,
  • S_R and S_C permutations of rows and column within one block (except when R=2 or C=2, so 2X2 is a degenerate case)
  • S_C and S_R permutations of rows or columns of blocks (except when R=2 or C=2)
  • S_M for the symbols, or subgroups thereof.
  • combinations of the above
Your conjecture is equivalent to the claim that none of these can be subgroups of the little group. By appropriate choice of the representative of each orbit, one can rule out the first 4, but the 4th is harder to rule out: particularly cases where a permutation of symbols is undone by the other operations (all of which are permutations of cells). Checking this seems to be a fruitful direction to go.
sg
 
Posts: 22
Joined: 14 February 2006

Postby Red Ed » Sun Mar 05, 2006 12:10 pm

Both conjectures are false due to the brave claim that they hold for "sudoku grids of any size". Take a look at conjugacy class 7 for the 3x3 sudoku symmetry group: this has order 3, which can't happen in any group of order 2^m.

More generally, for any RxC sudoku, there is a grid that has symmetries of order R, C and LCM(R,C). Informally, the grid in question is just the obvious generalisation to any R,C of this 3x2 example:
Code: Select all
123|456
456|123
---+---
231|564
564|231
---+---
312|645
645|312
It should be clear that you can roll everything right by one stack and then relabel to return to the original grid: a symmetry of order R in general. Similarly, you get a symmetry of order C from cycling the bands. Doing both at once gives you a symmetry of order LCM(R,C).
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Ocean » Sun Mar 05, 2006 8:46 pm

sg wrote:Conjecture 2 implies 1. ...
True. I thought it might be easier to prove #1 than #2, therefore the split. But ...
Red Ed wrote:Both conjectures are false due to the brave claim that they hold for "sudoku grids of any size". Take a look at conjugacy class 7 for the 3x3 sudoku symmetry group: this has order 3, which can't happen in any group of order 2^m.
Thanks! I was not aware that you found groups of symmetry ops of order 3 in 3x3 sudokus. Must admit that I never followed the grid counting discussions in enough detail. When I read ... "In conclusion, there are 10945437157 essentially different completed sudoku grids if we use the group H. That is, 23919 G-classes give a single H-class, while the other 5472706619 G-classes split into two H-classes. " - I naively thought - (or rather assumed without thought) - this meant 23919 grid classes with symmetry group of order 2, the rest order 1 - which of course was not correct.
Red Ed wrote:More generally, for any RxC sudoku, there is a grid that has symmetries of order R, C and LCM(R,C).

This illustrative example shows that the expresson for the order of H (the group of symmetry ops fixing G) should include the factors R, C and LCM(R,C) - [or some multiplicity of the prime factors of R and C ?]
Ocean
 
Posts: 442
Joined: 29 August 2005

Next

Return to General