Canonicalization

[Emerentius]

Sudokus can be transformed in ways that do not affect the number of solutions or the applicability of solution strategies and thus their difficulty. One example is relabeling by switching 1 and 2 everywhere. The crate already contains a shuffle function that performs such transformations in a random manner. It should also contain a function to map all equivalent sudokus to the same sudoku, the canonical form.

Todo: Canonicalizations for

• [x] solved sudokus
• [x] unsolved sudokus based on their (unique) solution
• [ ] unsolved sudokus, preserving the pattern of clues

[david-fong]

I'm currently doing some work on a related problem: Checking if two Sudokus are equivalent. Perhaps the thinking can be useful? here it is

[Emerentius]

I must admit I had trouble trying to understand the approach you're taking there (and it seems the link is dead now). I think the algorithm was for fully solved sudokus? For both solved and uniquely solvable sudokus I already have a canonicalization implementation that is apparently decently fast, >20,000 sudokus/s on my laptop (I thought it was only ~1k/s).

I don't have a good idea of what to do for unsolved sudokus that have zero or more than one solution. Neither do I have a good approach for a pattern preserving canonicalization.

My current algorithm uses the lexicographically minimum sudoku as canonical form and uses the minlex property to cut down the search space substantially.