Sudoku subgrid canonicalization tool

Programs which generate, solve, and analyze Sudoku puzzles

Sudoku subgrid canonicalization tool

Postby dobrichev » Tue May 26, 2015 4:21 pm

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!
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Sudoku subgrid canonicalization tool

Postby Serg » Thu May 28, 2015 9:27 pm

Hi, Mladen!
dobrichev wrote: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.
dobrichev wrote: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).
dobrichev wrote: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
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Sudoku subgrid canonicalization tool

Postby dobrichev » Fri May 29, 2015 5:54 am

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.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Sudoku subgrid canonicalization tool

Postby coloin » Sun May 31, 2015 12:24 am

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
coloin
 
Posts: 1633
Joined: 05 May 2005

Re: Sudoku subgrid canonicalization tool

Postby dobrichev » Sun May 31, 2015 5:51 pm

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.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Sudoku subgrid canonicalization tool

Postby coloin » Sun May 31, 2015 8:47 pm

dobrichev wrote:......................... 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
coloin
 
Posts: 1633
Joined: 05 May 2005


Return to Software

cron