GridChecker, an exhaustive puzzle enumerator

Programs which generate, solve, and analyze Sudoku puzzles

Re: GridChecker, an exhaustive puzzle enumerator

Postby ronk » Sat Nov 10, 2012 5:46 am

Afmob wrote: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!
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Sun Jul 14, 2013 5:20 pm

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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: GridChecker, an exhaustive puzzle enumerator

Postby dobrichev » Sun Jul 14, 2013 8:52 pm

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

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Mon Jul 15, 2013 9:53 pm

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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Pattern minlexing

Postby dobrichev » Thu Oct 03, 2013 9:40 pm

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

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Fri Oct 04, 2013 7:15 am

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.]
Last edited by Serg on Tue Oct 08, 2013 11:50 am, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: GridChecker, an exhaustive puzzle enumerator

Postby dobrichev » Fri Oct 04, 2013 1:20 pm

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

How the GridChecker works

Postby dobrichev » Sun Jul 03, 2016 7:14 pm

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

Re: GridChecker, an exhaustive puzzle enumerator

Postby champagne » Tue Jul 05, 2016 6:59 am

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
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

re: GridChecker produced a puzzle with 0 answers

Postby Pat » Tue Oct 03, 2017 7:37 am

Pat (2017.Feb.5) wrote:
dobrichev wrote:

    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
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re: GridChecker, an exhaustive puzzle enumerator

Postby dobrichev » Sat Oct 07, 2017 4:45 pm

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

Re: GridChecker, an exhaustive puzzle enumerator

Postby enxio27 » Thu Nov 09, 2017 5:07 pm

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.
User avatar
enxio27
 
Posts: 268
Joined: 13 November 2007

Re: GridChecker, an exhaustive puzzle enumerator

Postby champagne » Thu Nov 09, 2017 6:29 pm

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.
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Re: GridChecker, an exhaustive puzzle enumerator

Postby enxio27 » Thu Nov 09, 2017 7:05 pm

champagne wrote: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).
User avatar
enxio27
 
Posts: 268
Joined: 13 November 2007

Re: GridChecker, an exhaustive puzzle enumerator

Postby champagne » Thu Nov 09, 2017 7:52 pm

enxio27 wrote:
champagne wrote: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.
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Software