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