Firstly, please let me explain what's a symmetry (don't know what's the common used Sudoku term, if you know, tell me).
For unsolved Sudoku, with solvable givens (and unique solution), if one grid (A) becomes equivalence of another grid (B) after any steps and combinations of following operations, A is a symmetry of B because both A and B have the same essential. That's because of that following operations don't really change the grid.
1, Permutations of the 9 symbols, (such as change 1 to 5, 5 to 2, and 2 to 1)
2, Transposing the matrix (that is, exchanging rows and columns),
3, Permuting (ie. rearranging) rows within a single block,
4, Permuting (ie. rearranging) columns within a single block,
5, Permuting the blocks row-wise,
6, Permuting the blocks column-wise.
The operations were quoted from here,
http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php
The signature I want to generate is to represent a grid. For any unique grid, the signature should be unique. If we don't consider the symmetry (that's to say, just treat symmetry as different grid), that's quite easy to generate the signature by just packing all empty cell (as 0) and all givens in order, or use MD5, etc.
My question is, how to generate signature so that all symmetries of a grid have the same signature?
That's to say, if two grids have different signatures, they can't be translated to each other by above operations.
Or a "variant" question, how to make all symmetric grids to a unique grid form in a certain algorithm? Any symmetry of a grid is fed to the algorithm, the output should be always a same grid for all symmetries.
Thanks
EDIT
Just learned the word "symmetry" from the wiki, it's a more accurate word.
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku
There is also algorithm (out of my math knowledge) to detect two grids are symmetries, but that doesn't explain to to make unique grid to represent all symmetries.
9x9 Sudoku -- generate unique signature for all variations of a grid
Author
I believe it's quite difficult to give common algorithm mathematically (maybe that's why nobody answered 
).
But after some deep thinking and understanding, I think translating the symmetry grids under certain rules (rules on relationship between rows and columns, bands and stacks) may generate unique grid.
I will try it later.
).But after some deep thinking and understanding, I think translating the symmetry grids under certain rules (rules on relationship between rows and columns, bands and stacks) may generate unique grid.
I will try it later.
There is a simple brute-force solution: Generate all the grids equivalent to the given grid, convert each one to a number and add them together.
A more practical solution might be trying to transform a grid in its class that is minimum in some sense. For instance, you could try to find the lexicographically smallest equivalent grid. Or perhaps you can first sort the blocks so the list of how many hints appear at each one is as small as possible lexicographically. Then, within the equivalent grids that have that distribution of the number of givens per box, try to find smallest one.
Once you have your minimum grid, compute some hash of it.
It might take a bit of work, but you should be able to get this working.
A more practical solution might be trying to transform a grid in its class that is minimum in some sense. For instance, you could try to find the lexicographically smallest equivalent grid. Or perhaps you can first sort the blocks so the list of how many hints appear at each one is as small as possible lexicographically. Then, within the equivalent grids that have that distribution of the number of givens per box, try to find smallest one.
Once you have your minimum grid, compute some hash of it.
It might take a bit of work, but you should be able to get this working.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
