Jump to content
  • Advertisement
Sign in to follow this  

9x9 Sudoku -- generate unique signature for all variations of a grid

This topic is 2783 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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,

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.


Just learned the word "symmetry" from the wiki, it's a more accurate word.
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.

Share this post

Link to post
Share on other sites
I believe it's quite difficult to give common algorithm mathematically (maybe that's why nobody answered :rolleyes:).

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.

Share this post

Link to post
Share on other sites
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.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!