The New Sudoku Players' Forum

[ronk]

If we use some kind of canonicalization method, we choose the smallest or largest puzzle from a finite number of isomorphic puzzles and only one puzzle can be the smallest/largest. But if a puzzle has automorphisms there might be multiple, different transformations which lead to the same canonical puzzle.

Well said!

[Serg]

Hi, Mladen!
I tried to use GridChecker for patterns canonicalization, but didn't managed to do it. Maybe I use your tool incorrectly. Please, help me.

Problem.
Input file contains patterns in linear form, "." symbol denotes empty cell, "1" symbol denotes cell containing clue. I need to get output file with sorted canonicalized patterns without duplicates (duplicates must be removed). I use command line:

gridchecker --similar --subcanon --puzzles input.txt --mspuzzles output.txt

GridChecker works fine unless input file contains pattern with 81 clues:

Code: Select all

111111111111111111111111111111111111111111111111111111111111111111111111111111111


If input file contain this pattern, GridChecker crashes (v. 1.15) or hangs (v. 1.19) - checked for Windows 32-bit and Windows 64-bit. Problem is reproduced even input file contains problem pattern alone.

Serg

[dobrichev]

Hi Serg,

Thank you for this bug identification.

There is an empirically found "MAXANS" size of a "stack" which evolution was 3456, then 5184 (in the original Michael Deverin's code, then 120000 (in gridchecker's code), and the final candidate is 3359352 (in order to minimize 81x1). Memory of size 2*sizeof(short)*60*MAXANS is allocated once ant then reused.

Minimizing patterns is untypical usage of puzzle minlex algorithm. It unnecessary cares for relabelling. For sorting and duplicates removal it uses uncompressed 81-bytes fields instead of bitmaps which limits the maximal number of distinct patterns in a batch to available/addressable RAM.

As a fast and dirty fix, I will recompile the tool with this larger MAXANS. Wait for PM.

A much better solution is to clone the puzzle minlexing code and simplify it by removing the relabeling part and use bitmaps for the resultset. This of course will take some time for coding and testing and I can't guarantee you that it is achievable within a week or two.

[Serg]

Hi, Mladen!
I've gotten your special utility "patminlex", intended for patterns canonicalization, and checked it. The utility works well. Thank you for your help!

Serg

[dobrichev]

JPF found more bugs in the pattern minimization, and they are not easy to fix in the Michael Deverin's code.

Finally I wrote a separate tool available here and here which works faster, consumes less memory, and is hopefully correct.

Cheers,
MD

[Serg]

Hi, Mladen!
I've downloaded and checked your tool for patterns canonicalization. It works well. Command line to run (MS Windows):

CanPattern.win32.v1 <input_file >output_file

Input file can contain patterns or puzzles. Puzzles are converted to patterns (substituting any digit by "1") and then canonicalized. The tool is very fast - 700000 patterns were canonicalized during 3.4 sec (modern Intel Core i5 CPU).

Thank you for useful tool!

Serg

[Edited. CanPattern.win32.v1 speed is limited by disk I/O. So, sometimes I saw 3.4 sec for test execution time, sometimes - 2.4 sec - depending on Windows file cache performance.]

[dobrichev]

Hi Serg,

Thank you for the interest and for the usage explanation.

I would like to add, that the processing is throttled down by the disk and disk cache I/O.
With artificially reduced i/o (by minlexing each input puzzle for several times) I achieved performance of over 1M patterns/sec on Core i3 550 CPU @ 3.2 GHz.

I see a room for improvement in the logic that would eventually result in 20% less CPU cycles, but this improvement wouldn't improve the user experience since the reduction of the execution time will be negligible.

[dobrichev]

I added in the opening post of this topic an explanation posted in 2010 in the now lost Sudoku Programmers Forum "How the GridChecker works".
This information can help champagne and others who are interested in puzzles enumeration for a given solution grid.
On Jan 01, 2012 Gary McGuire and team announced that There is no 16-clue puzzle and to my knowledge currently their approach is the best, in orders of magnitude faster. Their public program code is optimized for 16-clue search, but potentially can be tuned for 17-clue search.

[champagne]

Hi mladen,

As you know, I wanted to start with more UAs than the lot supplied by the McGary blueprints of size<=12 (119 uas in my test)

I applied the process described in your opening post to the bands 1+2 and for the multi floors of size 6 {123456 123457 .... 456789} 84 possibilities

It works fast an gives back what I needed.

in some milliseconds, I got a 1500 UAs table where the limit is for UAs of size 21.

This will be my start for the test, but I suspect that a wider table could be even better.

Thanks for help

[Pat]

Today somehow this puzzle with no solutions appeared in my list,
and I don't know how it happened.

1..2....3.4..3..5...6...2..2....1.7..8..7.5.....4.......3.8.....5.7...649......2.

By chance the puzzles with no solution also can't be rated and this saved me.

once upon a time, i ran your software without specifying --minimals
and it did produce puzzles with 0 answers

i have now posted a nice example
-- may help in diagnosing

[dobrichev]

Hi Pat,

Thank you for this excellent example.

I reproduced this error in the current version v1.30 (2017-07-12)

It should be easy to trace.
I will update you when a fixed version is available.
Unfortunately recent versions are for Linux and porting back to Windows would take some extra effort.

Cheers,
Mladen

[enxio27]

Has anyone compiled gridchecker for Windows using an AMD processor? Apparently the only compiled version I can find requires an Intel processor. I don't have the ability to compile the source code, and I also don't currently have a Linux box set up.

[champagne]

I am not expert in gridchecker use, but it is one program that I included in my pattern game process to produce a canonical on pattern version (without redundancy) of the generated puzzles.

I am using gridchecker.v12 (mladen produced many versions of the code over years) and it is compiled using microsoft visual c++

Depending on what you want to do, this program could be what you are looking for.

[enxio27]

I am not expert in gridchecker use, but it is one program that I included in my pattern game process to produce a canonical on pattern version (without redundancy) of the generated puzzles.

That's what I'm hoping to try with it.

I am using gridchecker.v12 (mladen produced many versions of the code over years) and it is compiled using microsoft visual c++

I think the latest is up to v1.9, but I found only the source code, and I have no way to compile it. I found one version that was already compiled for 32-bit Windows, but it won't work with any processor except Intel (I have an AMD).

[champagne]

I am not expert in gridchecker use, but it is one program that I included in my pattern game process to produce a canonical on pattern version (without redundancy) of the generated puzzles.

That's what I'm hoping to try with it.

I am using gridchecker.v12 (mladen produced many versions of the code over years) and it is compiled using microsoft visual c++

I think the latest is up to v1.9, but I found only the source code, and I have no way to compile it. I found one version that was already compiled for 32-bit Windows, but it won't work with any processor except Intel (I have an AMD).

The AMD processor is not a problem except for a limited number of new instructions.
mladen updated the code with the last intel features and some versions of the AMD processors didn't have the adequate set.

I had, about three years ago to change my own AMD processor the reach a full compatibility with the intel set of instructions used by mladen.

If you want to test your AMD compatibility, the easiest way would be to use my .exe. what can be done using mails or through a file loaded in a shared place.