No. of inequivalent sudokus

hv at crypt.org hv at crypt.org
Sat Aug 13 17:02:12 CEST 2005


"N. J. A. Sloane" <njas at research.att.com> wrote:
[...]
:allowing (i quote)
:
:    Relabelling entries;
:    Reflection;
:    Rotation;
:    Permutation of blocks of columns 1-3, 4-6 and 7-9;
:    Permutation of blocks of rows 1-3, 4-6 and 7-9;
:    Permutation of columns 1-3;
:    Permutation of rows 1-3;
:    Permutation of columns 4-6;
:    Permutation of rows 4-6;
:    Permutation of columns 7-9;
:    Permutation of rows 7-9.
:
:So there's a new sequence here:
:
:0    1    2      3
:1    1    x   5472730538
:
:where x is some small number!  My question is, what is x?
:Using analogues of the above transformations, how many
:inequivalent 4 X 4 grids are there?
:
:Hugo van der Sanden sent me an upper bound x <= 6, since any 4X4 
:grid is equivalent to one of:

Let me label them:
 A    B    C    D    E    F

:1234 1234 1234 1234 1234 1234
:3412 3412 3421 4312 4321 4321
:2143 2341 2143 2143 2143 2413
:4321 4123 4312 3421 3412 3142
:
:but this can surely be reduced. So is x 1, 2 or 3?

x is 2.

I don't visualise these well, but I had time to write some code which
found:

A => permute columns (1-2), relabel (1-2) => E
B => mirror antidiagonal, relabel (1-2-3) => C
B => rotate -90', relabel (1-3-4) => D
B => permute columns (1-2), permute rows (3-4), relabel (1-2) => F

So {A, E} are identical, and {B, C, D, F} are identical.

There is no way to transform A to B: the pattern of opposing pairs in A
(12/21 and 34/43 vertically; 13/31 and 24/42 horizontally) is matched
in only one axis in B (13/31 and 24/42 horizontally), and there is no
transformation that can change that. So A and B are truly distinguishable,
and a(2) = 2.

Hugo





More information about the SeqFan mailing list