The New Sudoku Players' Forum

[jmehat]

Like many others, I am looking for sudoku problems with minimum number of givens. I am particularly interested in finding symmetric problems.

One question I encountered was to verify that in the collection of Gordon Royle there was no symmetric equivalent problem. Thus, I only had to examine the patterns of givens. In his collection of 32930 problems, I count 20717 different patterns.

The first method I used was to build the complete class of equivalent patterns for each grid, looking for symmetrics, but it is painfully slow with the program I wrote using standard dynamic programming (around 1 minute on a standard PC, when the pattern has no symmetry).

Then I realized that, when applying the transformations that give equivalent problems, the contents of two boxes are never exchanged, so the number of givens by box is constant. If you take the 3x3 contents of a box and apply one of the nine transformations that do not conserve symmetry, you can know very easily if a box is symmetrisable, A problem that has no symmetrisable box with an odd number of givens (actually, a number of givens having the same parity as the number of givens in the full grid), has no box that goes to the center, and can be eliminated. It reduces the number of patterns to 20588.

Then, I built a 3x3 count-box that contains the number of givens in the original boxes. Surely, in a symmetric problem, two symmetric boxes do contain the same number of givens (and the center box respects the preceding condition). So the patterns whose count box is not symmetrisable can be eliminated. This method reduces the number of patterns down to 3329.

In the next step, I examine if the contents of any pair of boxes can be made symmetric by a sequence of transformations (including symmetries, but not transpositions) ; that gives me a matrix of compatibility between boxes. I eliminate the problems where all of the nine boxes permutations contain opposite boxes that are not compatible. This one leaves 1579 patterns, which takes around one day of computing.

For the next step, I am not completely convinced of the correctness of my method neither of its implementation. For each pair of compatible boxes, I enumerate the methods that can be used to make their contents symmetric. Then (again for the nine permutations of boxes), I verify that there exists a common method for the four corners and for the two pairs of middle boxes. Only 45 patterns pass this step.

Do you think it is correct?

Do you think it is trivial?

May it be useful for something else?

Do some of you aready use something similar?
--
Jean Mehat, jmehat@gmail.com

[gfroyle]

This is a non-trivial problem to solve without using the appropriate tools - these tools unfortunately require a little bit of knowledge about permutation groups, and I don't know if that is knowledge that you have.

Overall, your technique is generally valid, but I think you would do better to go the other way round... rather than finding the entire equivalence class of each grid, and then searching for a symmetric one, it would be faster to start by finding all the PATTERNS equivalent to your desired symmetric pattern, and then check that none of my puzzles match that exact pattern.

Why is this better?

In general, most of my puzzles have no symmetries and so the equivalence class will have size 3359232. Thus you will have to compute this number of grids 30000 times and then check each one for symmetries.

Now let's go the other way round - start with your desired symmetric pattern (maybe a reflection, or a rotation ?). Then apply all the 3359232 possible legal transformations and get a whole stack of other patterns.. how many will there be? The number you get will be some divisor of 3359232 (in fact, it is the index of the normalizer of the subgroup preserving the desired pattern) and in general this will be a moderate number, usually no more than a few thousand.

But the key thing is that you only have to do THIS computation ONCE - and once you have the list of patterns, it is trivial to check that none of my grids have that pattern.

Even quicker you can take my word for it that none of them have "nice" symmetries like reflections or rotations, though there are *SOME* symmetries in a few of them...

Cheers

Gordon

[jmehat]

This is a non-trivial problem to solve without using the appropriate tools - these tools unfortunately require a little bit of knowledge about permutation groups, and I don't know if that is knowledge that you have.

Well, I don't know enough about permutation groups to find quickly a unique representative of every equivalence class. Have you a pointer on such a method?

Now let's go the other way round - start with your desired symmetric pattern (maybe a reflection, or a rotation ?). Then apply all the 3359232 possible legal transformations and get a whole stack of other patterns.. how many will there be? The number you get will be some divisor of 3359232 (in fact, it is the index of the normalizer of the subgroup preserving the desired pattern) and in general this will be a moderate number, usually no more than a few thousand.

As far as I know, there are 317 non-equivalent patterns with 90 degrees roational symmetry and the method you suggest is ok. But for 180 rotational symmetry, all I know is that the number of non-equivalent patterns is less than or equal to 145858, so it's better to go my way. Or do I miss something ?

The filter I described in my first post runs so quickly on your collection of 17 givens problems I didn't time it.

Jean

[gfroyle]

Or do I miss something ?

No, I wasn't very clear... let me try again..

First, we number all the cells from 1..81

Code: Select all

01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27
28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54
55 56 57 58 59 60 61 62 63
64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81


Now any symmetry can be described by saying what it does to each cell.. for example, a rotation by 90 degrees would send

01 -> 09 -> 81 -> 73 -> 01
02 -> 18 -> 80 -> 64 -> 02
(and so on..)

This is usually written in cycle notation as follows

(01, 09, 81, 73) (02, 18, 80, 64) (... etc ...)

which is just a short-hand notation for the same idea.


Now, suppose we are trying to find out whether any of the list have a reflection symmetry swapping left <-> right. This reflection has a cycle notation

(01,09) (02,08) (03,07) (04,06) (10,18) (11,17) (12,16) (13,15) ... etc .. (73,81) (74,80) (75,79) (76,78)

meaning that position 01 and 09 are swapped, as are 02 and 08. Notice that the centre line, namely positions 05, 14, 23, ..., 77 are all fixed and so are omitted from the cycle notation.

Now it is quick to check that none of the 32000 on my list have THIS EXACT permutation fixing the pattern of clues. But of course, each of the ones on my list is just one representative of an entire equivalence class of puzzles, and so we might ask whether some puzzle EQUIVALENT to one of the ones on my list has this permutation fixing it.

There are two options:

(1) Find all equivalent PUZZLES and check them against this exact permutation

(2) Find all equivalent PERMUTATIONS and check them against my exact list of puzzles


You are doing a sort of version of option (1), but being clever about not generating every puzzle by only considering equivalent puzzles that MIGHT be fixed by that permutation.

Option (2) involves using a group theory package to find all the "conjugate permutations" (that is a technical term) to the one specified above, and it turns out that there are just 108 conjugates permutations.

So to check for all reflectional symmetries, either horizontal or vertical, we just need to see if any of my list is fixed by those 108 permutations.

The reason I think that option (2) is better is that the general procedure is the same for any type of permutation that you are interested in, so it can be completely automated.

So for example, we might then consider a diagonal reflection (where the main diagonal is fixed, but the top-right and bottom-left corners are interchanged.)

I hope that this makes more sense than my earlier rushed post!

Gordon

[gsf]

There are two options:

(1) Find all equivalent PUZZLES and check them against this exact permutation

(2) Find all equivalent PERMUTATIONS and check them against my exact list of puzzles

where does canonical labeling fit in here?
e.g., a function f(P) where f(P)=f(Q) <=> P~Q

[gfroyle]

where does canonical labeling fit in here?
e.g., a function f(P) where f(P)=f(Q) <=> P~Q

Well, my list of 17-clue puzzles contains only one representative from each equivalence class, and the representative that I choose is computed by a "black box" canonical labelling algorithm.

So when Jean M was looking for symmetric puzzles, he had to make sure that he checked the entire equivalence class, rather than just the single representative that "happens" to be in my list.

So in a sense, we are trying to find the most effective way to "undo" the canonical labelling and work with the entire class....

My point is that there are actually TWO canonical labellings here - the particular choice of symmetry is just one member of an equivalence class of permutations (technical name for this is the "conjugacy class") and so we can either proceed by

- picking a canonically labelled PUZZLE and checking against entire equivalence class of symmetries

OR

- picking a canonically labelled SYMMETRY and checking against entire equivalence class of puzzles


The issue here is that humans have a very strong preference for a particular canonically labelled SYMMETRY, simply because of the way that we draw things, and so the temptation is to fix the symmetry and search the equivalence class of puzzles.

The purpose of my posting was to suggest that there is an alternative - fix the puzzle and search the equivalence class of symmetries.

Gordon