Determinant of essentially different sudoku grids

Programs which generate, solve, and analyze Sudoku puzzles

Determinant of essentially different sudoku grids

Postby Norse » Tue Sep 22, 2020 4:59 pm

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?
Norse
 
Posts: 2
Joined: 25 August 2020

Re: Determinant of essentially different sudoku grids

Postby Mathimagics » Wed Sep 23, 2020 2:32 am

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.
Last edited by Mathimagics on Wed Sep 23, 2020 6:44 am, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1905
Joined: 27 May 2015
Location: Canberra

Re: Determinant of essentially different sudoku grids

Postby Mathimagics » Wed Sep 23, 2020 5:26 am

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 62 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 1905
Joined: 27 May 2015
Location: Canberra

Re: Determinant of essentially different sudoku grids

Postby Mathimagics » Wed Sep 23, 2020 6:35 am

Norse wrote: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].
User avatar
Mathimagics
2017 Supporter
 
Posts: 1905
Joined: 27 May 2015
Location: Canberra

Re: Determinant of essentially different sudoku grids

Postby Norse » Wed Sep 23, 2020 6:58 am

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
Norse
 
Posts: 2
Joined: 25 August 2020

Re: Determinant of essentially different sudoku grids

Postby Mathimagics » Thu Sep 24, 2020 6:00 am

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)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1905
Joined: 27 May 2015
Location: Canberra


Return to Software