The New Sudoku Players' Forum

[Norse]

Does anyone know if essentially different sudoku solution grids in minlex-form have unique determinants.
That is, if two arbitrary solution grids are essentially different, do they necessarily have to have a different determinant if they are in minlex-form?

If not, is there some other way to uniquely identify essentially different solution grids?

[Mathimagics]

Nobody has really studied this area as far as I know.

For standard Sudoku (9 x 9), it is highly likely that the determinants of ED grids are unique, but that's about all one can say.
[ EDIT ] Wrong (again) ... see post below

This fairly recent paper looks interesting, if only you could get access to it without paying for the privilege.
[ EDIT ] Now available, see post below

A quote from the abstract:

We show that non-trisotopic latin squares with equal permanents and equal determinants exist for all orders n≥9 that are divisible by 3.

A new word for us - 2 Latin Squares are trisotopic if they are isotopic, or transpose-isotopic. This corresponds to our Sudoku definition of essentially different.

[Mathimagics]

I have an update to this question.

I contacted Ian Wanless, one of the authors of the paper linked above (he's at Monash University), and he gave the following example of 2 ED grids which can NOT be distinguished by their determinants:

Code: Select all

147358269258169347369247158471582693582693471693471582714926835926835714835714926
147258369358169247269347158471582693582693471693471582714926835926835714835714926


He added:

det doesn't distinguish them in a very strong sense. Even if you replace each symbol by a variable and calculate a symbolic determinant, both matrices give the same result.

Ian kindly gave permission to share the paper:

perdetLS-JCD.pdf

(184.78 KiB) Downloaded 157 times

[Mathimagics]

If not, is there some other way to uniquely identify essentially different solution grids?

• there is a canonical form that uses a graph derived from the grid, two ED grids will always have essentially different graphs.

• you can also identify a graph by its Minlex Index, which is just a number in the range [1, 5472730538].

[Norse]

Thanks for the very quick answer to the questions.

Is there a canonical way to get the minlex index from a given sudoku. I guess it is not a function on the sudoku, rather than a "lookup" in some table

[Mathimagics]

Sorry, but the Minlex Index is (as far as I know) only possible if you have the right lookup tables. You take your source grid S, get its minlex form M, then search a database of all the ED grids. With fast-access disk, and binary search method, and some suitable tables, this can all be done very quickly.

I'm really not sure what you're after here ... is it an alternative canonical representation, or do you want an absolutely minimal representation of the ED grids.

For the latter, then gsf long ago demonstrated that an average of ~1 byte per grid (yes!) is possible. This compression method is, however, not well documented (for info on how to use his tools, see here)