## GridChecker, an exhaustive puzzle enumerator

Programs which generate, solve, and analyze Sudoku puzzles

### Re: The tool

dobrichev wrote:
Red Ed wrote:
dobrichev wrote:But yet the most fragile point is reordering. Minor changes in remapping logic lead to difference in execution time more than two times.
I don't think it's necessary to change the remapping logic. Explicitly (for some small R):
blah blah blah
Now that you've got all the P[.] saved, run through them in random order.

Done in almost the same way, and included in version 1.6 available here.
Thanks Not sure how much it's helped (in a quick test - probably too quick - I couldn't see a lot of difference), but it's good of you to test the idea.
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: GridChecker, an exhaustive puzzle enumerator

ronk wrote:dobrichev, you might be interested in this solution grid. Hunting for a 17; at 2.4 hrs, ETTF=72+ hrs @ 2.8 GHz. Run aborted.

Code: Select all
`123456789457189632896327451234861975578934126619275348345612897781593264962748513`

Yes, it is a good candidate for the slowest grids list.
From the grids having known 17s, SFB goes slower.
There are several grids w/o (known) 17s which are slower.
Code: Select all
`SFB, 3 17s, all 2-digit UA are of size 18, confirmed by GridChecker there are no more 17s, ~107h5897326146218543797439168258351297464175682932963471589684715323726954811542839672xU4,1xU6 having common clue r4c3 with one of the U4s{28,29,58,59}{41,43,91,93}{43,46,47,53,56,57}Not checked for 17s, estimated time ~170h @ 2.8GHz1234567894567892317982136452391748565746289136813954273678415928159623749425371680xU4,3xU6, two of them sharing clue at r5c2, confirmed by improved old Checker there are no 17s, 12d9h{31,32,51,52,91,92}{34,36,54,56,94,96}{52,54,59,62,64,69}1234567894567892317892315642349681758671254939153748263486179525928436176715923480xU4,3xU6, two of them sharing clue at r1c4{11,14,17,21,24,27}{12,14,18,32,34,38}{13,16,23,26,33,36}3 known UA with valency 7#7={15,17,22,23,24,25,29,31,32,34,37,39,41,42,49,51,53,54,55,56,66,67,69,75,76,79,81,84,85,86,92,97}#7={15,16,17,22,23,24,25,29,31,32,34,37,39,41,42,49,51,53,54,55,56,66,67,69,76,79,81,84,85,86,92,97}#7={11,12,16,17,19,24,26,27,29,33,35,37,41,44,46,48,55,56,57,58,63,64,67,69,72,78,79,83,85,86,88,93,98,99}confirmed by GridChecker there are no 17s, ~87h123456789456789132789213645275941368638527914941638257394175826517862493862394571`

ronk wrote:Is there an easy way to determine the version via the command line, like a 'GridChecker -V' maybe?

No. You can take a look at the download page where all versions are available with short comments for changes.

There are about 30 - 40 command line parameter candidates. Prior to introducing more parameters I still have to decide whether this should be a stand-alone tool (like gsf's one) or set of tools (like dukso's collection), whether to make it portable, to split it into modules applicable to be integrated at source code level, to implement COM interfaces allowing methods to be called from script languages, etc, etc.

Actually currently available versions have no major differences. I am publishing the tool when I decide it is relatively stable, assigning next version for reference. Of course soon or later this should be put in order.

Cooperation and feedbacks are welcome.
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

### Re: The tool

Red Ed wrote:
dobrichev wrote:Not sure how much it's helped (in a quick test - probably too quick - I couldn't see a lot of difference), but it's good of you to test the idea.

Nevertheless ETTF stabilizes.

For the several grids I tested:
On slow grids within first minutes there are huge fluctuations.
After 1-2% done ETTF is within +/-30%, which was not the case before.
After ~10% done ETTF is within +/- 10%, which is reasonable.
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

### New version 1.7

The new version 1.7 is here.

A multithread version - the job is split into all available processors and is executed in parallel.
A bug, which caused puzzle duplicates in rare cases, has been fixed.

Running w/o command line parameters displays usage and version number.

MD.
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

### Re: New version 1.7

dobrichev wrote:The new version 1.7 is here.

A multithread version - the job is split into all available processors and is executed in parallel.

That should be quite useful for JPSangin at the moment. I'll run it too ... as soon as I'm not doing three other things simultaneously. In the future, is there a chance for user control of the number of processors used?

dobrichev wrote:Running w/o command line parameters displays usage and version number.

Thanks.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: New version 1.7

ronk wrote:In the future, is there a chance for user control of the number of processors used?

You can do it on the fly by setting Task Manager -> Processes -> Set Afinity.

You can set environment variable
Code: Select all
`set OMP_NUM_THREADS[=num]`

to control the number of threads.

Default is one thread per logical CPU, i.e.
1 for P4 w/o HT
2 for P4 w/ HT
2 for dual core w/o HT
4 for dual core w/ HT, etc.

To avoid freezing of other applications, the best way is to set the process priority to low (Task Manager -> Processes -> Set Priority).

To avoid overheating, the best way is to limit the threads to 1, in the console window, before running the application.
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

### Re: GridChecker, an exhaustive puzzle enumerator

Hi, dobrichev!
Is it possible to run gridchecker for puzzle canonicalization in such way that output (canonic) puzzles will be sorted and duplicates will be removed?

Serg
Serg
2018 Supporter

Posts: 768
Joined: 01 June 2010
Location: Ukraine

### Re: GridChecker, an exhaustive puzzle enumerator

Serg wrote:Is it possible to run gridchecker for puzzle canonicalization in such way that output (canonic) puzzles will be sorted and duplicates will be removed?

gridchecker --similar --subcanon --puzzles in.txt --mspuzzles can_sorted_no_duplicates.txt

Limitations:
- the result should fit in memory (i.e. it is inapplicable for huge files).
- input is one puzzle per row, max 2000 symbols per row, all symbols after 81-th are ignored.
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

### Re: GridChecker, an exhaustive puzzle enumerator

Hi, dobrichev!
dobrichev wrote:
Serg wrote:Is it possible to run gridchecker for puzzle canonicalization in such way that output (canonic) puzzles will be sorted and duplicates will be removed?

gridchecker --similar --subcanon --puzzles in.txt --mspuzzles can_sorted_no_duplicates.txt

It works fine, thank you! Is it possible to see some run statistics (number of processed puzzles, number of output puzzles, etc.)?

Serg
Serg
2018 Supporter

Posts: 768
Joined: 01 June 2010
Location: Ukraine

### Re: GridChecker, an exhaustive puzzle enumerator

Serg wrote:Is it possible to see some run statistics (number of processed puzzles, number of output puzzles, etc.)?

It is possible by adding counters in the source code and recompiling.
The number of duplicates found, which is displayed to stderr in this syntax, is more an exception.
Historically, there are counters, progress, etc. in the functionalities concerning enumeration of the puzzles in a fixed grid, which was the initial purpose of this tool.

I can send you the recent source files - very dirty and unstable code which still should be useful for extraction of algorithm implementations.
Or, maybe it is time to spend several days in building a publicly accessible repository like for skfr?
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

### Re: GridChecker, an exhaustive puzzle enumerator

dobrichev wrote:
Serg wrote:Is it possible to see some run statistics (number of processed puzzles, number of output puzzles, etc.)?

It is possible by adding counters in the source code and recompiling.
The number of duplicates found, which is displayed to stderr in this syntax, is more an exception.
Historically, there are counters, progress, etc. in the functionalities concerning enumeration of the puzzles in a fixed grid, which was the initial purpose of this tool.

I can send you the recent source files - very dirty and unstable code which still should be useful for extraction of algorithm implementations.
Or, maybe it is time to spend several days in building a publicly accessible repository like for skfr?

Thank you for fast reply. Gridcheker's statistics would be useful, but is not mandatory. I think it isn't worth special implementation.

Thanks, Serg
Serg
2018 Supporter

Posts: 768
Joined: 01 June 2010
Location: Ukraine

### Re: GridChecker, an exhaustive puzzle enumerator

Hi, dobrichev!
Serg wrote:Hi, dobrichev!
dobrichev wrote:
Serg wrote:Is it possible to run gridchecker for puzzle canonicalization in such way that output (canonic) puzzles will be sorted and duplicates will be removed?

gridchecker --similar --subcanon --puzzles in.txt --mspuzzles can_sorted_no_duplicates.txt

It works fine, thank you! Is it possible to see some run statistics (number of processed puzzles, number of output puzzles, etc.)?

It was surprise for me, but gridchecker (version 1.15) shows run statistics already in this running mode! It writes execution time and number of duplicates removed (it is namely that statistics I'd like to see). Gridchecker processed 20000 puzzles (canonicalization, sorting and duplicates removal) for 13 seconds. Fine result!

Serg
Serg
2018 Supporter

Posts: 768
Joined: 01 June 2010
Location: Ukraine

### Re: GridChecker, an exhaustive puzzle enumerator

I am surprised that you was surprised. As you can see from my previous answer, I assumed that you run this command, saw what is happening (duplicates), but need more statistics.
My contribution to canonicalization algorithm is very small. Michael Deverin is the author. There is still bug in the algorithm - it returns always the same result (it is deterministic), but very rare the result isn't the lowest lexicographical morph.
Recently I adopted the algorithm for parallel processing (more precisely, a thread-safe processing). It isn't published yet.
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

### Re: GridChecker, an exhaustive puzzle enumerator

It wouldn't call it a bug but a misconception. Deverin's algorithm first minimises the pattern and afterwards the givens by exploiting possible pattern automorphisms. But this doesn't necessarily lead to the smallest lexicographical puzzle, for instance

Code: Select all
`. . . . . . . . 1. . . . . . . 2 . . . . . . 3 . . . . . . . 4 . 5 . .  . . 6 . . . 3 . . . . 7 8 1 . . . . . 1 . . 2 . . . 4. 3 . . . . . 7 . 9 5 . . . . . . . `

Code: Select all
`. . . . . . . . 1. . . . . . . 2 . . . . . . 3 . . . . . . . 4 . 5 . .  . . 6 . . . 3 . . . . 7 8 2 . . . . . 3 . . . . . 7 . . 2 . . 1 . . . 49 5 . . . . . . . `

The latter has a lexicographically smaller pattern but the first is lexicographically smaller.

Edit: The second example is false. See my following post for the correct version.
Last edited by Afmob on Thu Nov 08, 2012 11:36 am, edited 1 time in total.
Afmob

Posts: 132
Joined: 28 June 2011

### Re: GridChecker, an exhaustive puzzle enumerator

If I am not wrong, the algorithm is a mixture of pattern-row-min-lex and lexicographical-min-lex.
A pure pattern min-lex algorithm should work faster but is somehow not popular.
dobrichev
2016 Supporter

Posts: 1816
Joined: 24 May 2010

PreviousNext