The New Sudoku Players' Forum

[dobrichev]

I just updated the recent version of the sudoku subgrid canonicalization tool on https://github.com/dobrichev/sudoku-minlexing-tool.
It was tested on 64-bit Linux and should compile on 32/64-bit Windows too.
The input is 81 chars per line, not necessarily valid puzzle. The symbols after the 81th position are ignored. Symbols from '1' to '9' are treated as givens, the rest as non-givens. For pattern canonicalization, all cells can be represented as '1' in the input.
The output is the original puzzle, followed but tab, then the canonical form, then tab, and the number of non-trivial automorphisms.
The canonical form is "minimal lexicographical representation of the pattern" and then minimal re-labeling representation within that pattern. It differs from general minimal lexicographical representation but is deterministic, simple and fast.
The performance is > 300K subgrids per thread per second. Although it can canonicalize full solution grids, it is highly inefficient for this task compared to alternatives like GSF's tool.

Enjoy!

[Serg]

Hi, Mladen!

I just updated the recent version of the sudoku subgrid canonicalization tool on https://github.com/dobrichev/sudoku-minlexing-tool.
It was tested on 64-bit Linux and should compile on 32/64-bit Windows too.
...
The output is the original puzzle, followed but tab, then the canonical form, then tab, and the number of non-trivial automorphisms.

Thank you for new tool! But I am not quite sure - what program did you mean? There are 3 executables and 1 "main.cpp" file in your "sudoku-minlexing-tool-master.zip" file. I tried "CanSubgrid.win32.v1.2.exe" in Windows XP environment (64-bit CPU). Tool works well for puzzles having moderate number of clues, but outputs canonic form only, without "the number of non-trivial automorphisms", etc.

The performance is > 300K subgrids per thread per second.

I got performance approx. 100000 puzzles/sec for blue's double diagonal symmetric minimal puzzles (50781 puzzles).

Although it can canonicalize full solution grids, it is highly inefficient for this task compared to alternatives like GSF's tool.

It is true. Bunch of 1088 solution grids was processed (by CanSubgrid.win32.v1.2.exe) during 208 seconds on my notebook, but GridChecker processed those grids during 8.8 seconds, i.e. 24 times faster.

Serg

[dobrichev]

Hi Serg,

These executables are the same we discussed here. Consider them obsolete.
The latest binary is compiled for Linux. You should compile main.cpp.

[coloin]

Very good.
Would it be possible to have a max canonicalizing tool ?
I have a feeling that it might be better for some tasks ....maybe ?
Cheers
C

[dobrichev]

Hi Coloin,
The code is in public domain and everybody can modify it to produce max-lex. In the initial version, the code that produces the large lookup table is included.
Knowing how many bugs I fixed in this simple tool, I have no plans to do max-lex only to see what happens.

BTW, I found that Deverin's canonicalization code produces ordered puzzle sets that are compressed better than the puzzles represented in this canonical form.
Advantage of this form is that the puzzles with same pattern are ordered next to each other.

[coloin]

......................... produces ordered puzzle sets that are compressed better.......

Yes perhaps do the thinking before the coding ......
I was thinking of max lexing the first band and then min lexing the next two.
Would that compress our clues up even more ?
Only an idea.... C