Canonical sudoku algorithm?

Lummox JR · Posted: Sun Mar 26, 2006 2:49 am Post subject: Canonical sudoku algorithm?

I'm interested in implementing canonicalization in my sudoku generator/solver. I checked out one thread, and another on the players' forums, but nowhere is the actual algorithm spelled out. The best I can find is source code, which is difficult to understand and therefore difficult to trust (even if it's known to work). Canonicalization is a fairly sticky problem.

I know of course the basic operations you can perform to keep an equivalent grid. What I don't get is how to navigate through these to find a canonical form. It's one thing to canonicalize a solution grid, but then that doesn't tell you how to rearrange the givens, whether by position and/or digit. The fact that both are mutable suggests that it might be possible for two different canonical solution grids to hold equivalent givens. That is, there might be two or more operative paths from a solution grid to its canonical form, and in order for the givens to also be canonical, the same path must apply to all equivalent puzzles. If this is actually the case, could anyone explain why?

Soultaker · Posted: Sun Mar 26, 2006 11:34 am Post subject:

It's very simple, really. Given a puzzle (an empty grid with some hints) and a solution (a filled in grid), you figure out how to transform the solution into it's canonical form. This is transformation is simply a permutation of cell locations and a permutation of symbols. You can easily perform the same transformation to the original puzzle as well to bring it into normalized form.

This is where you're mistaken:

Lummox JR · Posted: Sun Mar 26, 2006 7:38 pm Post subject:

Yes, that was what I was thinking about the canonical form, that two different transformations might result. I'd love to see a proof of that, and moreover some details of the actual algorithm involved so I could figure out how to implement it myself.

Soultaker · Posted: Sun Mar 26, 2006 9:15 pm Post subject:

I think I didn't describe it properly. There might be different transformations on the solution grid that result in the same canonical solution, but these also transform the puzzle to a unique form. Does this answer your question? (I'm afraid not, but I'm not sure what to get into.)

Lummox JR · Posted: Sun Mar 26, 2006 11:41 pm Post subject:

That's my point of confusion. I don't get how you could apply different transformations to the solution grid and still bring the givens together in the same unique form. If digits are permuted first and then columns and rows, then a form of the puzzle that changed columns and rows might escape canonicalization. If column and row realignment comes first, then a puzzle with different digits could invalidate such an algorithm. So to my mind it seems that depending on the preferred transformation order, some permutation of the original puzzle would lead to a different canonical form. It doesn't seem like permuting the solution grid is quite enough.

But then, I don't know the algorithm, so I don't know how it works or how it would avoid this problem. Just seeing source code doesn't help. What I'd like most is to find a link explaining the algorithm itself.

vidarino · Posted: Mon Mar 27, 2006 7:26 am Post subject:

Soultaker · Posted: Mon Mar 27, 2006 2:44 pm Post subject:

vidarino: what I worry about with that approach is that you might miss a chance to normalize the grid with a combination of operations. For example, swapping to columns and then swapping two rows may create an even 'smaller' grid, but if neither of those operations gives you an immediate improvement, your algorithm does neither and returns a non-optimal solution.

In addition, as Lummox JR also said, you arbitrarily choose a permutation of symbols based on the first row of the initial solution. Why not swap a few rows and columns and then permute the symbols? It may result in an entirely different grid.

From my calculations (and those of others) there are about 3.3 million different valid permutations of cells (not symbols). After picking one of those, the best symbol permutation is fixed by the symbols in the top row. So, I think a correct algorithm tries all 3.3 million permutations and then picks the lowest. However, it's easy to apply the same permutation to the original puzzle.

This is ofcourse not very efficient (and for larger grids it's even worse) so the question is if there are any 'shortcuts' allowed. I'm not sure of this yet.

Lummox JR · Posted: Mon Mar 27, 2006 5:16 pm Post subject:

Ah, but how is such an algorithm achieved, and why would it work on givens and not just the solution? This is the burning question. I know gsf has implemented an algorithm, but from his source code it's difficult to understand the algorithm itself, let alone why (or if?) it works on givens.

Soultaker · Posted: Mon Mar 27, 2006 5:28 pm Post subject:

For clarity; the (naive) algorithm I proposed was: try each of the 3 million or so possible permutations on the solution grid and determine which one results in the lexicographically smallest solution. Apply this same transformation to the original puzzle to bring it into normal form.

(By definition, a puzzle is in normal form if no transformation of the puzzle existst that results in a lexicographically smaller solution. A permutation is permissable only if you can apply it to any valid puzzle to obtain another valid puzzle.)

vidarino · Posted: Mon Mar 27, 2006 5:52 pm Post subject:

Lummox JR · Posted: Mon Mar 27, 2006 6:20 pm Post subject:

Transformation from one solution grid to a canonical form could be done in a number of different ways via different steps. Givens comprise only part of the solution, so depending on how those transformations were done, two equivalent puzzles could conceivably have the same canonical solution grid while still having two different sets of givens.

If two isomorphic solution grids have the same canonical form (as they should, if it's truly canonical), there's no guarantee the transformations involved would provide a canonical set of givens--merely two isomorphic puzzles with the same solution. If the first step of canonicalization is to relabel the digits in box 1, for instance, then a puzzle that had been flipped horizontally would have to go through a different set of transformations (besides just adding a horizontal flip) to reach canonical form than one that had not. If the first step was rearranging columns and/or rows, then a puzzle that had had its digits permuted would go through a different set of rearrangements.

It does not necessarily follow that a process to find a canonical form of the solution grid also yields a canonical puzzle. You can compare this to sorting terminology, where a sort guarantees the results are in order, but only a stable sort guarantees that equivalent items remain in the same relative order they started. A sudoku puzzle may have three 9's, and the transformations will tell you which 3 givens correspond to them, but that result could be different for other forms of the same puzzle, if the transformation process is not stable.

I could probably figure out a way of canonicalizing the solution. That's a difficult problem but there are some resources to figure out out. What's not an easy problem is finding such an algorithm that also canonicalizes the givens.

The only idea I have contrary to this is that maybe the concept of equivalent puzzles with the same solution is bogus. (Though obviously, non-equivalent or merely similar puzzles could share a solution.) The only way to be sure is to answer the question: Is there any sequence of valid sudoku transforms that can be applied to a solution to produce the very same solution, that does not ultimately involve simply undoing the transforms? If the answer to that is no, then indeed any canonicalization of the solution will affect the givens also.

Soultaker · Posted: Mon Mar 27, 2006 6:25 pm Post subject:

daj95376 · Posted: Mon Mar 27, 2006 7:45 pm Post subject:

I may be a simple country boy, but I don't understand the reason for all the discussions on finding a canonical normal form (CNF) to compare solutions.

If two puzzles have identical CNFs for their solutions, that does not mean the puzzles are identical.
(an example)

If your puzzle requires multi-coloring to solve it ...
and another puzzle only needs naked/hidden singles to solve it ...
then I don't care if their solutions have matching CNFs.

To me, Sudoku is all about 'solving the puzzles' and not about 'comparing the solutions'.

Lummox JR · Posted: Mon Mar 27, 2006 7:56 pm Post subject:

Daj, my interest is in a canonical puzzle form, not canonical solutions. That is, to detemine if two puzzles are equivalent. Two non-equivalent puzzles--with the same canonical solution or without--will almost definitely need different solve methods. However two equivalent puzzles should require the exact same methods. If you flip a puzzle around, if you exchange two of its rows within the same 9x3 stack, if you rearrange the 3x9 "tower" sections of blocks, the puzzle will be superficially different but is still solved the same way.

Soultaker · Posted: Mon Mar 27, 2006 8:05 pm Post subject:

You can safely replace almost definitely with definitely. Two 'equivalent' puzzles have the same basic properties and require the same solution techniques; they are essentially the same puzzle cleverly disguised.

edit:
Never mind what I said here... I had a bug in my code. Wink