GridChecker, an exhaustive puzzle enumerator

Programs which generate, solve, and analyze Sudoku puzzles

Re: The tool

Postby Red Ed » Sat Aug 07, 2010 6:47 pm

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

Postby dobrichev » Sun Aug 08, 2010 7:43 am

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, ~107h
589732614621854379743916825835129746417568293296347158968471532372695481154283967

2xU4,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.8GHz
123456789456789231798213645239174856574628913681395427367841592815962374942537168

0xU4,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}
123456789456789231789231564234968175867125493915374826348617952592843617671592348

0xU4,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, ~87h
123456789456789132789213645275941368638527914941638257394175826517862493862394571

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: 1302
Joined: 24 May 2010

Re: The tool

Postby dobrichev » Sun Aug 08, 2010 7:55 am

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: 1302
Joined: 24 May 2010

New version 1.7

Postby dobrichev » Mon Aug 09, 2010 10:44 am

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: 1302
Joined: 24 May 2010

Re: New version 1.7

Postby ronk » Mon Aug 09, 2010 2:51 pm

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

Postby dobrichev » Mon Aug 09, 2010 3:49 pm

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.
set OMP_NUM_THREADS=1
dobrichev
2016 Supporter
 
Posts: 1302
Joined: 24 May 2010

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Tue Oct 30, 2012 7:22 am

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

Re: GridChecker, an exhaustive puzzle enumerator

Postby dobrichev » Tue Oct 30, 2012 8:49 am

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: 1302
Joined: 24 May 2010

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Tue Oct 30, 2012 9:21 pm

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

Re: GridChecker, an exhaustive puzzle enumerator

Postby dobrichev » Wed Oct 31, 2012 8:54 am

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: 1302
Joined: 24 May 2010

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Wed Oct 31, 2012 9:45 am

Hi, Mladen!
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
2017 Supporter
 
Posts: 501
Joined: 01 June 2010
Location: Russia

Re: GridChecker, an exhaustive puzzle enumerator

Postby Serg » Tue Nov 06, 2012 10:42 am

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

Re: GridChecker, an exhaustive puzzle enumerator

Postby dobrichev » Tue Nov 06, 2012 11:15 am

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: 1302
Joined: 24 May 2010

Re: GridChecker, an exhaustive puzzle enumerator

Postby Afmob » Tue Nov 06, 2012 11:43 am

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 . . . 4
9 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: 130
Joined: 28 June 2011

Re: GridChecker, an exhaustive puzzle enumerator

Postby dobrichev » Tue Nov 06, 2012 11:58 am

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: 1302
Joined: 24 May 2010

PreviousNext

Return to Software