Group theory and sudoku

Question

I am given two Sudoku $S_1$ and $S_2$ and I have two check whether $S_1$ can be turned into $S_2$ with the symetry operators.

The two Sudoko are in a "legal" state. So a given cell (numbers $1...9$) can only occur once in a row, column and 3x3 block)

1. Value permutations: Let $v_1.....v_n \in \{1...9 \} $ be the values of $S_1$
   $\pi$ be any bijective map $\pi: V \rightarrow V $ where $V=\{v_1 ...v_n\}$

A value permutation is the new Sudoko obtained by setting $v_i$ =$\pi(v_i)$

2. Permute the three stacks
3. Permute the three bands;
4. Permute the three columns within a stack
5. Permute the three rows within a band
6. Any reflection or rotation.

Essentially, I have to check if $S_2$ can be turned into $S_1$ given these operations

The BruteForce-Way of doing this would be to generate all the symetries of $S_1$ and see if $S_2$ belongs to that set. What would be a more efficient way of checking this ?

Would appreciate any ideas/hints

Answer 1

Let's consider, first, full sudoku grids $S_1$ and $S_2$.
Call $\mathbf G$ the group of symmetry operators.
$\mathbf G$ has $9!\,2\cdot 6^8 =9!\; 3,359,232$ elements.
$S_1$ and $S_2$ are equivalent $(\sim)$ if it exists a transformation $f \in \mathbf G\ $ such that $S_2 =f(S_1)$
The best way to check if $S_1\sim S_2$ is to use a canonalization form.
A canonalization is a rule defining how to choose one and only one element in an equivalence class.
For instance, one can pick the minlex element :
If $S_1=\{a_1 ,...,a_{81}\}$, the minlex equivalent is the one such that the string $\{a'_1 ,...,a'_{81}\}$ is minimum.
Then, for any $S_2 \sim S_1$, its minlex form will be $\{a'_1 ,...,a'_{81}\}$ too. Reciprocally, if two grids don't have the same minlex form, they are not equivalent.

The advantage of minlex form is that it can be used for any subgrids (i.e. puzzles) - just replace blank by zero -, or for patterns (0 or 1)
Two very efficient programs are used by the sudoku community :

1. sudoku by Glenn Fowler (gsf)
2. gridchecker by Mladen Dobrichev (dobrichev)

They are very fast, 50,000 grids/second (?), but I am not able to give full details of their algorithms.

To uderstand how a canonalization works, you may have a look at this post.
It's a different canonalization form requiring only 648 transformed grids to check.
It works for full grids and for valid puzzles by solving the puzzles before.