The New Sudoku Players' Forum

[Mathimagics]

Does anybody know of software that can canonicalise a 9x9 Latin Square?

I have a set of (some hundreds of) ED Sudoku grids and want to determine whether they are ED as Latin Squares ...

[creint]

After looking in the history of this forum I found this post:
http://forum.enjoysudoku.com/canonical-puzzle-form-t3054.html

Permutations could be fast but I think I found a problem.
A box can also be transformed to a row but I could not find a permutation that does this job.
Every value is still connected to same constraint when doing this transformation.
Following examples are with the default grid, could have picked a different grid but manually transposing all boxes takes time.

Checked my box puzzle:

Code: Select all

123......456......789............................................................

Should give same canonical form as columns puzzle:

Code: Select all

1........2........3........4........5........6........7........8........9........

Same for the default sudoku with only 1 solution:

Code: Select all

...456789...789123...123456234567891567891234891234567345678912678912345912345678

Code: Select all

.........456789123789123456234567891567891234891234567345678912678912345912345678

But the program CanSubgrid.win32.v1.2.exe from http://forum.enjoysudoku.com/sudoku-subgrid-canonicalization-tool-t32476.html gave different results.
Tried Gridchecker.exe too, also different results.

Is missing permutations not a big problem with all canonicalization/calculations currently done?
These extra permutations are not to hard to implement for sudoku.
Graph canonicalization could also be a solution for dynamic constraints, but how to implement that?

For latin squares there should be no problem using only row/column/number permutations.

[Mathimagics]

It was interesting to look back on that discussion.

I realise now that in my usual rush, I failed to point out that I want to compare COMPLETE grids (Latin Squares), not partially complete ones (puzzles or subgrids).

Over the years since that discussion took place, I think we all agree now that the standard CF (Canonical Form) for a complete Sudoku grid is the same as with the standard mathematical definition of isotopy classes for Latin Squares. If one LS can be transformed into another by permuting the rows, columns and relbalelling, the two grids are isotopic, ie in the same equivalence class.

So a CF for Latin Squares would be the minlex candidate from 9! x 9! possible transformations, so we have 362,880 ^ 2 = 131,681,894,400 valid transformations, and on the surface it would seem we need to check all of these, normalise the resulting grid (map row 1 to 123456789) and choose the minlex candidate.

That's a much harder task than doing the same for Sudoku grids, where we have just 3,359,232 transformations to check.

We can speed things up by not completely evaluating each transformation. We need only produce the first row, from which we obtain the normalisation mapping, then we apply the transformation cell by cell, knowing we can "bail out" by comparing the partial results with the best candidate found so far.

If the transformations can be stored as cell-mappings, this becomes particularly efficient, as we know for each transformation exactly where each cell goes to (or comes from). But a table of 132 billion x 81-byte mappings is probably a little bit too large to fit in memory.

I am not convinced that graph canonicalisation has much to offer here, perhaps it might be useful for puzzles, but not for complete grids.

[Serg]

Hi, Mathimagics!
Why do you ignore transposing as VPT for Latin Squares?

I think, the situation with LS canonicalization is not so bad. The common canonical form for LS is reduced form, when numbers in the first row and in the first column are placed in right order (1,2,3,...,N). So, during LS canonicalization, we must check all N rows as the first row of LS (N ways). Then we should permute all columns (N! ways). Then the only relabelling can provide right order of numbers in the first rows. The only rows permutation can provide right order of numbers in the first column.

1. Transposing - 2 ways.
2. Move a row up to be the first row - N ways.
3. Permute columns - N! ways.

Totally 2*N*N!. For N=9 we get 2*9*9! = 6531840 VPT - only twice Sudoku VPTs.

Serg

[Mathimagics]

Hi Serg!

Why do you ignore transposing as VPT for Latin Squares?

Sorry, I got that info from WikiPedia, which defines isotopy classes that don't include transposition, see A040082. Brendan McKay is the source of the Wiki isotopy class definition and tables, and he did not include transposition. Well he did, but in a separate OEIS sequence: see here A000528.

Now that reports the group size with transpose as 57,810,418,543.

Now I have found the GAP definition for LS9 that I made at some stage, with the group defined by 9 permutations, one for transposition plus 8 for the row (or col) permutations. However, now that I check, GAP is telling me that this group only has 26,336,378,800 members over 495 conjugacy classes. So I must have stuffed up my definition somehow. Are you able to replicate the group size given at OEIS? I presume that the error is mine.

Regarding reduced Latin Squares, that might be one canonical form that is convenient for other purposes, but I do not think it is suitable for distinguishing between ED grids. Grids equivalent under this CF are not necessarily equivalent under VPT's, surely?

Cheers
MM

[Serg]

Hi, Mathimagics!

Why do you ignore transposing as VPT for Latin Squares?

Sorry, I got that info from WikiPedia, which defines isotopy classes that don't include transposition, see [A040082. Brendan McKay is the source of the Wiki isotopy class definition and tables, and he did not include transposition. Well he did, but in a separate OEIS sequence: see here [A000528.

Yes, it looks strange ... Brendan McKay in the first link says about "isotopy classes" and doesn't take transposition into account. But in the second link he says about "Latin squares types" and takes transposition into account.

Now that reports the group size with transpose as 57,810,418,543.

Sorry, but it's not group size, as far as I understand. It's number of non-equivalent Latin squares. (Usually transformations, not objects, form groups.)

Now I have found the GAP definition for LS9 that I made at some stage, with the group defined by 9 permutations, one for transposition plus 8 for the row (or col) permutations. However, now that I check, GAP is telling me that this group only has 26,336,378,800 members over 495 conjugacy classes. So I must have stuffed up my definition somehow. Are you able to replicate the group size given at OEIS? I presume that the error is mine.

You says about number of transformations, but OEIS sequences says about number of Latin squares.

Regarding reduced Latin Squares, that might be one canonical form that is convenient for other purposes, but I do not think it is suitable for distinguishing between ED grids. Grids equivalent under this CF are not necessarily equivalent under VPT's, surely?

Why? I think, canonical form is directly produced by chosen VPT group. (More precisely speaking, canonical form is determined by metric (rule to produce a number from object) and chosen VPT group.)

Thinking about WikiPedia page about Latin squares... I think we should account not only transposition, but all "paratopic" transformations. It will replace "2" by "6" in my formula about number of LS VPTs (6*N*N! instead of 2*N*N!). And this number should be "group size" for LS VPT.

Serg

[Serg]

Hi, Mathimagics!
Thinking a bit more about permitted VPTs for Latin squares ...
Remembering old discussion - should we take into account content-dependent Sudoku VPTs, I think we should still take into account transposing only from the group of "paratopic" transformations, when we are talking about Latin squares VPTs. Transposing is content-independent VPT (and "Do nothing" is content-independent VPT), but other 4 "paratopic" transformations are content-dependent. So, I think, number of VPTs for reduced Latin squares is 2*N*N!

BTW, all numbers of LS in OEIS sequences concern Latin squares in reduced form, as far as I understand.

Serg

[Mathimagics]

Usually transformations, not objects, form groups.

Groan ... yet another blunder on my part ...

In fact, I think that I might well have made exactly the same schoolboy error on a previous occasion.

Cheers
MM

PS: I will think hard (which is something of a challenge for me) on everything you said regarding use of the reduced forms, but I suspect that you are correct ...

[Serg]

Hi, Mathimagics!
I see my posts looks very chaotic. Therefore I am writing my point of view once more (more detailed).

Let someone has 2 Sudoku solution grids - A and B. He wonders if these solution grids will be equivalent if they are treated as Latin squares. That is can A be transformered to B by some permutations of rows, some permutations of columns, transposition and relabelling?

I think we should find their LS minlex forms and compare those forms. If LS minlex forms are the same - grids are equivalent.

LS minlex form is very similar to Sudoku minlex form. One can calculate metric by treating the first row as 9-digit number, concatenating it (at the right side) with second row 9-digit number, etc. We should search for LS minlex form, appling arbitrary rows/columns permutations, transposition and relabelling to Latin squares A and B, and calculating metrics. It turns out, LS minlex form is a kind of LS reduced form, i.e. has the first row and the first column in right order.

So, while searching for minlex form, we should try reduced form's VPTs (group produced by any combinations of transformations below):

1. Transposition - 2 ways.
2. Cyclic shifts of rows up (r1 --> r9, r2 --> r1, r3 --> r2, etc.) - 9 ways.
3. Columns permutations - 9! ways.

2*9*9! transformations in total.

After reduced form's VPT applying we should transform resulting grid to reduced form - by relabelling the first row and permuting the rest rows (to provide right order of the first column).

So, we should try 2*9*9! VPT to A and B, and should keep minimal metrics observed. Those minimal metrics are LS minlex forms for grids A and B. If these grids have the same minlex forms, they are equivalent.

Serg

[Edited. I wrote about necessity to get LS reduced form after reduced form's VPT application.]
[Edited2. I deleted extra reduction of original grids to LS reduced form before applying reduced form's VPT. Thanks to Mathimagics for his remark.]

[Mathimagics]

Hi Serg,

I have a real problem with that methodology, as I think that conversion to reduced form is really part of the "normalisation" step that we would apply AFTER applying a VPT.

The canonicalisation algorithm should be applied to both A and B and the results compared.

The canonicalisation process is basically this:

• For each VPT, apply the transform to A (or B), normalise the result (ie relabel so row 1 = 123456789, and sort the rows). This gives a reduced form.

• Select the minlex "winner" from this list of reduced forms.

This is, I think, a standard generic approach used in most canonicalisation methods ... including Sudoku. (In Sudoku "normalise" is just the relabelling, we do not sort the rows, of course).

[Serg]

Hi, Mathimagics!

I think that conversion to reduced form is really part of the "normalisation" step that we would apply AFTER applying a VPT.

I agree with you. That normalisation BEFORE applying a VPT was extra step. I edited my previous post.

Serg

[Mathimagics]

And I agree with you that the transformation count is just 2N x N!. We permute the columns, no need to permute the rows (just N different choices for row 1).

Ok, we got there in the end! Thanks for your patience!

And for 9x9 squares we have 2 x 9 x 362880 = 6,531,840 VPT's ...

And the number of ED grids should be 57,810,418,543 which is from sequence A000528, not 115,618,721,533 which is from A040082 (and used in the Wikipedia page).