I'm interested in permutations on 4x4 Sudokus i.e. ways of rearranging the numbers so that the solution is still "the same". For instance if you mirror a Sudoku horizontally the solution remains essentially the same. You just have to mirror the positions in the old solution.
I have now 4 concrete permutations that span a set of 1024 permutations that can distort a Sudoku without changing it.
I have already asked whether it is possible to find a smaller base in the general case: it is not
Now I present a concrete example:
My permutations are (one-line notation)
- swap row 1 and 2: $(5\; 6\; 7\; 8\;\; 1\; 2\; 3\; 4\;\; 9 \dots 16)$
- swap upper and lower blocks: $(9\dots 16\;\; 1\dots 8)$
- rotate anti-clockwise by 90°: $(13\; 9\; 5\; 1\;\; 14\; 10\; 6\; 2\;\; 15\; 11\; 7\; 3\;\; 16\; 12\; 8\; 4\;)$
- rotate blocks anti-clockwise: $(9\; 10\; 1\; 2\;\; 13\; 14\; 5\; 6\;\; 11\; 12\; 3\; 4\;\; 15\; 16\; 7\; 8\;)$
There are other size 4 bases, I found 56 in total that generate all 1024 permutations. With dynamic programming I tried every possible base of size 3 and found none. But now I'm wondering could I have seen this coming?
If you look at the commutator factor group, it has the structure $Z_2^4$ (though one can argue how easy this is to see without a cojmputer). Thus (by a dimension argument) you cannot generate the factor (and thus the group) with fewer than 4 elements.
In general this only gives a lower bound, but for groups of prime power order this is (by Burnside's basis theorem) the minimum order.
BTW, there is a further symmetry, namely permuting the entries of the Sudoku (e.g. swapping every 1 and every 2).