Group theory and sudoku 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)


*

*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)$ 


*Permute the three stacks

*Permute the three bands;

*Permute the three columns within a stack

*Permute the three rows within a band

*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
 A: 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 : 


*

*sudoku by Glenn Fowler (gsf)  

*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.
