The New Sudoku Players' Forum

[Red Ed]

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.

[dobrichev]

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


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]

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]

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.

[ronk]

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?

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

Thanks.

[dobrichev]

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

[Serg]

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

[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?

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.

[Serg]

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?

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

[dobrichev]

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?

[Serg]

Hi, Mladen!

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]

Hi, dobrichev!

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?

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

[dobrichev]

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.

[Afmob]

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.

[dobrichev]

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.