Sudoclues: max, min, forest, leaves

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

Postby Red Ed » Mon Mar 06, 2006 12:30 am

Ocean wrote: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 ?]
Um, it tells us something about the order of the group fixing that particular type of grid, but not much else.

Where are you going with this? We know the full structure of the symmetry group (and people like Gordon and Frazer can write it down compactly using something called a wreath product, apparently), so we know the limit of all possible symmetries and their orders. Beyond that, we resort to computer-aided searches to count the number of grids fixed by any particular conjugacy class of symmetry ops.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gfroyle » Mon Mar 06, 2006 7:54 am

Where are you going with this? We know the full structure of the symmetry group (and people like Gordon and Frazer can write it down compactly using something called a wreath product, apparently), so we know the limit of all possible symmetries and their order


The wreath product is actually pretty straightforward...

As an illustration, let's consider the group for the 3x4 case - by this I mean a 12x12 grid where the blocks each have 3 rows and 4 columns. Therefore there are 4 bands and 3 stacks.

We know that we can permute the rows within each band, and then permute all the bands between themselves. This gives us Sym(3) (the symmetric group of all permutations of 3 things) on each of the 4 bands individually. Then we have Sym(4) permuting the entire bands bodily.

This is then expressed as Sym(3) wr Sym(4) (note the order: Sym(3) on EACH ONE of the bands, then Sym(4) on the WHOLE COLLECTION of bands).

Therefore we have of course Sym(4) wr Sym(3) acting on the columns.

The row perms and column perms are independent and so the whole group is

(Sym(3) wr Sym(4)) X (Sym(4) wr Sym(3))


If 3 were equal to 4 (or rather, if we were doing this for m x n and we happened to consider the case where m was equal to n) then there would be an additional factor of 2 representing the transpositions.

The conjugacy classes of this group will give us all the possible symmetries... apart from the requirement that the order of the element must divide the order of the whole group, I don't think that much more can be said.

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Red Ed » Mon Mar 06, 2006 9:26 am

Great, thanks ... hoped you'd take the bait. I know nothing about wreath products, so can only guess, but ... is Sym(n) wr Sym(n) wr C_2 the group in the case m=n ???
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gfroyle » Tue Mar 07, 2006 2:09 am

is Sym(n) wr Sym(n) wr C_2 the group in the case m=n ???


Yep, I believe that's right.

(Sym(n) wr Sym(n)) on the rows and also the columns, then the C_2 doing the transposition of the matrix.. (or Sym(2) if you prefer).

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby sg » Tue Mar 07, 2006 12:29 pm

Just to round off the discussion; Shi Doku has
  • 288 solutions of which 2 are essentially different
  • 13579680 puzzles of which 85632 are irreducible
  • 1536 6-clue, 58368 5-clue and 25728 4-clue irreducible puzzles
  • 4710 essentially different puzzles of which 36 are irreducible (13 4-clues, 22 5-clues and 1 6-clue)

(Essentially different means that the objects are not connected by group action, ie, belong to separate orbits of the group under question. These are different for solutions and puzzles; puzzles require only a subgroup of invariances of solutions.)

For the record, I think Ocean is following a track which could be productive. We know (from a lot of hard work by people on the forum, Ed, Kjell, Frazer etc) that all the possible equivalence classes of the Su Doku group, SD(R,C), are not populated by Su Doku solutions whereas some are populated more than once. A detailed look, perhaps of the kind that Ocean is pursuing, could lead somewhere interesting.

For example, I ask two (not necessarily independent) questions:
  • Does the structure of the permutation group on M symbols, S_M (where M=RC), have any role to play in determining which classes of GSD(R,C) (ie, SD(R,C)/S_M: the geometric Su Doku group; whose construction was explained above by Gordon) are populated by RXC Su Doku?
  • What distinguishes different orbits which lie in the same equivalence class?

If the answers are known, then it would be nice to have a pointer.
sg
 
Posts: 22
Joined: 14 February 2006

Postby sg » Fri Mar 10, 2006 11:06 pm

I have a little progress to report on the enumeration of puzzles. For RXC Su Doku, each puzzle tree has upto 2^(M^2) nodes, where M=RC. Clearly this grows too fast to allow quick scanning. In order to reduce the problem, over the last few days I've been playing with the notion of a skeleton. A worked out example for an utterly trivial case is given in http://theory.tifr.res.in/~sgupta/sudoku/clues.html.

Start with a solution, then delete some entries, keeping the rest as clues. The skeleton of this puzzle is obtained by replacing each deleted entry by 0 and everything else as 1.

Choose a numbering of the M^2 cells. The bits of the skeleton written out in order of the numbering is the binary representation of a number which I call the value of the skeleton. The canonical numbering starts with 0 for the r1c1, increases along the row, is M for r2c1, and so on upto M^2-1. The value of the skeleton in the canonical ordering can be called the canonical value of the skeleton. Values of skeletons always lie between 0 and 2^(M^2)-1 (these are the only two values which are invariant under relabelling of the cells).

The ordered bits of the skeleton can also be interpreted as the vertices of an unit hypercube in M^2 dimensions. A subgroup of the symmetries of the hypercube acts on the skeletons.

Pruning Strategy 1: Since the geometric Su Doku group, GSD(R,C), acts on the skeletons, it can be used to enumerate the essentially different (ED) skeletons. More pertinently, the little group of a solution can be used to enumerate the ED skeletons. One needs to examine only the ED skeletons in order to generate full information about the whole game tree.

Note 1: This approach was implicitly taken by Red Ed in the enumeration of the Shi Doku solutions.

Note 2: As Kjell points out somewhere, the little group of most solutions is trivial so there is no reduction in the work required in most cases. However, in special cases of high symmetry, this can reduce the work enormously.

Note 3: Since the orbits of skeletons 0 and 2^(M^2)-1 are just themselves, the subgroup of the symmetries of the hypercube which act on the skeletons cannot be bigger than the subgroup of rotations of the hypercube around this body diagonal (the diagonal line which joins these two points).

Pruning Strategy 2: If one enumerates impossible skeletons, then these can be eliminated from the enumeration of all trees. Some impossible skeletons are those which have only 1's in two rows in the same block, since that would leave two rows without clues. In order to push this strategy, one needs a classification theorem about which little groups are not allowed.

Note 4: This was the structure behind the two questions in my previous post.

Pruning Strategy 3: Of course, once a puzzle has been proven to be improper, the whole subgraph below this node is automatically improper. Proof: note that the puzzle tree contains no inconsistent puzzle (ie, puzzle with zero solutions). Hence every improper puzzle in the graph has more than one solution. The removal of clues cannot decrease the number of solutions. Therefore, the result.

Note 5: Subgraphs are most easily identified by their skeletons. Once a subgraph is ruled out, one should mark these skeletons as unusable (since parts of them can be reached from other parts of the game tree).

Note 6: Skeletons are also useful enumeration tools in various proofs. For example, the best proof(s) that I have for the fact that M-1 clues are not sufficient for M>3 depend on the enumeration of equivalence classes of skeletons with M-1 clues.
Last edited by sg on Sat Mar 11, 2006 4:52 am, edited 2 times in total.
sg
 
Posts: 22
Joined: 14 February 2006

Postby Red Ed » Sat Mar 11, 2006 12:04 am

Interesting stuff, but this still leaves you with the problem of labelling the skeleton (putting flesh on the bones?) to make actual puzzles. Take a look at my set of 36 minimal 2x2-sudoku puzzles, for example, and you'll see several with the same skeleton.

I disagree with this, but only in a nit-picking way:
sg wrote:Since the geometric Su Doku group, GSD(R,C), acts on the skeletons, it can be used to enumerate the essentially different (ED) skeletons. More pertinently, the little group of a solution can be used to enumerate the ED skeletons. ... This approach was implicitly taken by Red Ed in the enumeration of the Shi Doku solutions.
I actually used the related fact that puzzles from essentially-different grids are themselves e-d. This let me do as you'd done and split the work into 2 searches, one per representative solution grid. At no point did I group puzzles by their skeleton class.

sg wrote:... the best proof(s) that I have for the fact that M-1 clues are not sufficient for M>3 depend on the enumeration of equivalence classes of skeletons with M-1 clues.
Now that sounds like progress. What's the biggest M for which you can prove this? Could you outline the proof here please?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby sg » Sat Mar 11, 2006 12:49 am

Red Ed wrote:Interesting stuff, but this still leaves you with the problem of labelling the skeleton (putting flesh on the bones?) to make actual puzzles.


A puzzle is completely specified by the skeleton and solution: P(skel,sol). In other words, I'm still trying to stick to the method by which one enumerated the 2X2 puzzle tree, but trying to reduce the work by pruning the graph as much as possible using group theory.

Red Ed wrote:At no point did I group puzzles by their skeleton class.


Didn't mean to imply that you did. What I wanted to point out was that the reduction into ED irreducible puzzles that you performed can be done using skeletons (hence the "implicitly" in my note 1).

Red Ed wrote:
sg wrote:... the best proof(s) that I have for the fact that M-1 clues are not sufficient for M>3 depend on the enumeration of equivalence classes of skeletons with M-1 clues.
Now that sounds like progress. What's the biggest M for which you can prove this? Could you outline the proof here please?


Its very painstaking and pedestrian, and nothing more (in essence) than examining each puzzle in turn. Only, the use of skeletons allows you to dispose of whole classes of puzzles at one go. But because there are a lot of skeletons, its still a lot of work. I'm now certain that I have M=4 properly, and the M=6 is probably okay. But by M=8 the number of skeletons is too large to examine by hand. I'll put it all in a pdf document and make it public.

Example: the last two rows cannot be devoid of clues, that means that the canonical value of the skeleton must be smaller than 2^8(2^8-1) for 2X2 and 2^24(2^12-1).

The proof that at least M-1 clues are required depends only on the S_M part of SD(R,C) anyway, so one should expect that for large enough M the GSD(R,C) should also be taken into account so this will not be a sharp lower bound. I wish I could see more clearly what makes something "large enough".
sg
 
Posts: 22
Joined: 14 February 2006

Postby Red Ed » Sat Mar 11, 2006 8:56 pm

Unless my coding let me down, the minimum number of clues for the 3x2 case (M=6) is 8.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby sg » Sat Mar 11, 2006 9:04 pm

Full enumeration or skeletons?
sg
 
Posts: 22
Joined: 14 February 2006

Postby Red Ed » Sat Mar 11, 2006 10:31 pm

Full-ish. Outer loop was over 49 representative e-d grids. Inner loop was over sets of 7 (then, when that failed, 8) clues such that at least M-1=5 distinct values were chosen. The run took only a few minutes, so it seemed safer not to risk introducing bugs by optimising further.

For concreteness, here's an 8-clue puzzle:
Code: Select all
1.|.4|..
..|..|.2
..|..|3.
--+--+--
..|..|.5
..|6.|..
.3|..|4.

In total, there are 537 eight-clue puzzles up to isomorphism.
Red Ed
 
Posts: 633
Joined: 06 June 2005

re: 2x3 - minimum number of clues

Postby Pat » Mon Sep 04, 2006 9:21 am

Pat (2005.Oct.30) wrote:for a box-size of 2x3,
menneske.No offers plenty of 8-clue puzzles

so, i wonder if a 7-clue puzzle may be possible?


i now see that this has been answered:

Red Ed (2006.Mar.11) wrote:Unless my coding let me down,
the minimum number of clues for the 3x2 case (M=6) is 8.

there are 537 8-clue puzzles up to isomorphism.


menneske.No has 657 puzzles
- obviously they were not checked for equivalence.



for example, their puzzles #111117 and #140386,
rated Super Hard,
are equivalent:
menneske.No #111117 wrote:
Code: Select all
 . . 1 | . . 2
 . . . | . . .
-------+------
 . . 6 | . . 1
 3 . . | 4 . .
-------+------
 . . . | . . .
 4 . . | 3 . .
menneske.No #140386 wrote:
Code: Select all
 1 . . | . 6 .
 . . . | . . .
-------+------
 . 3 . | . . 5
 6 . . | . 1 .
-------+------
 . . . | . . .
 . 5 . | . . 2
User avatar
Pat
 
Posts: 3280
Joined: 18 July 2005

Postby Lardarse » Thu Sep 07, 2006 8:59 pm

How?

A lot of this is going over teh top of my head, but it's nice to know that progress is being made.

However, I still don't see how those 2 are equivalent...
Lardarse
 
Posts: 106
Joined: 01 July 2005

re: equivalent puzzles

Postby Pat » Fri Sep 08, 2006 8:50 am

Lardarse wrote:How?
I still don't see how those 2 are equivalent...

take the first puzzle,
swap top and bottom bands,
swap rows within those bands,
swap columns within each stack,
and re-assign the digits thus -
  • 1 becomes 5
  • 2 remains
  • 3 and 6 swapped
  • 4 becomes 1
User avatar
Pat
 
Posts: 3280
Joined: 18 July 2005

Postby Lardarse » Fri Sep 08, 2006 3:59 pm

No wonder all of this stuff is over my head...:(
Lardarse
 
Posts: 106
Joined: 01 July 2005

PreviousNext

Return to General