projects skfr-fast-rating and sudoku-multi-purpose-program

Programs which generate, solve, and analyze Sudoku puzzles

projects skfr-fast-rating and sudoku-multi-purpose-program

Postby champagne » Sat Dec 04, 2010 10:34 am

EDIT that thread has been open for the project sudoku-fast-rating, cloning serate.
I opened a new project for my new code

As part of the code is copied from the first project and many features are common, I change the title of that thread and I use it for the new project

====================================================== end of EDIT

I promised to publish shortly the draft of my work in cloning Sudoku Explainer.


A new zip file including the code for the range 6.2 7.0 can be downloaded here
the last update of that file solves puzzles in the range 1.0 ot 7.4 and most of the 7.5.

I faced problem trying to download that file using Internet explorer. Downloading works well using Firefox.

This is a draft, likely containing many bugs and far from having covered the options of the command line.

In the following posts, one can find comments on the corresponding files.


The executable file will not work if the runtime microsoft visual C++ express has not been dowloaded before.
Unhappily, I have no tool to produce directly an executable including the runtime components.


That first post contains comments on how the program is organized and on classes required to start the solver.
All comments have been prepared on my website, so what I am doing here is to summarize the content and to give step by step the link to the corresponding page to load.

I start with preliminary remarks and property reserve. Just note that the zip file is not yet there



That page describe inputs output and commands


That page contains part of the main routine code and an overview on how processing and debugging are organized



general comments and code for input and output files



Handling of the command line and applying filters to the solution.
That part of the code is far for being implemented.
Only what is necessary to run the preliminary test is written so far;



That page contains very general routines
. indexing conversions
. bit fields 16;32;96 bits used in the process
. a small routine for tag to print conversion



That page contains other basic classes dedicated to
. storing a puzzle,
. permanent data, computed once for ever at the start of a batch,
. alternative index used to work on a row column or box



classes describing and processing
. a cell
. the table of cells




Last topic in that post, classes and processing of uniqueness checking

Last edited by champagne on Tue Aug 14, 2012 4:10 pm, edited 13 times in total.
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Sat Dec 04, 2010 10:34 am

This second post is dedicated to the solution from the basic rule to BUGs.

It will start with the missing classes used ot work out the solution, then the main routine to search the solution and, finally, the classes and the code used for each technique.


The class designed to handle the solution is called JDK.
Here some comments on it and the general code.



Now we start with the solution.
First the 2 subroutines of the main routine



followed by the main function in JDK going step by step thru the solving techniques



the code for candidates locked in row/box or column/box
the code for locked sets and hidden locked sets
and the code for XWings and other fishes



the code for XYWings and XYZWIngs



the code for URs ULs in 3 pages






and finally the code for BUGs



all the code necessary to rate puzzle in the range 1.0 6.2 is now there.
The next post will cover the steps using the basic tagging infrastructure.
Last edited by champagne on Sun Dec 05, 2010 2:37 pm, edited 2 times in total.
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Sat Dec 04, 2010 10:35 am

This third post is dedicated to the solution in the range 6.2 to 7.0 of Sudoku Explainer ratings.

Here starts the use of the tagging process, so most of the post will be dedicated to a presentation of classes used in that process;

Some features include reservations for next steps and some code existing in my solver that has good chances to be re used later.

we start with a general of the tagging process adjusted to SE specificaions



And now the "class" in use in that process

Here the list of these "class" and detailed description of the bit field for tags and of the container for a path



here the container for chains waiting for final selection and IPT a class indexing candidates




TZPTLN the table of candidates, a key table with three pages of description





TZLN the table of strong links and the search of partial pieces of path




TDB the central process of the tagging method in 2 pages




TZCF TCHOIX

TCF the first one holding
. a table of weak links in tags terms
. the central process described above

TCHOIX, the second one to manage sets, in that process
. sets of candidates of a cell
. sets of candidates of a specific digit in a row/column/box




and to close that post, the functions calling the stuff previously described

Last edited by champagne on Mon Dec 20, 2010 12:46 pm, edited 2 times in total.
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Sat Dec 04, 2010 10:35 am

locked 4
Last edited by champagne on Sat Dec 04, 2010 10:36 am, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Sat Dec 04, 2010 10:36 am

locked 5
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Sat Dec 04, 2010 10:36 am

locked 6
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Sat May 21, 2011 5:45 am

I did not publish in that thread for long.

Many reasons for that, among them :

a long trip
a lot of work for the first implementation

I played the game 141 doing most of the pre rating work using a first version of serate. It gave pretty good results.

In that first version covering from the start to multi chains, many problems appeared in meeting SE search of the shortest path.

Others "bugs" appeared as well at any step in the process. SE misses very often the "shortest path".

I did not see many people showing interest for that project and having time to dedicate to the implementation.
At the end, we re start that project with a new design for the chains.


The project is named skfr sudoku fast rating
http://code.google.com/p/skfr-sudoku-fast-rating/

we did not keep the link to serate, although it remains basically a "quasi cloning" first version.
serate has to many bugs and we don't intend to reproduce most of them.

The project is hosted in google projects database. The project is now open, but still empty.

The design will be revised to be done of separate modules to ease re use in other programs

The target remains to reach a ratio 1 to 100 as order of magnitude in the performance, which seems reasonable.

The programming language is C++




patrice joined the team and brings a good knowledge of JAVA and serate.
Jöel is to-day travelling, but will join as soon as he is back

Anybody willing to come with us is welcome

champagne

ps: The thread as such is dead. I will use it to inform the forum when significant steps will be achieved.
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Sat Sep 10, 2011 7:49 am

dobrichev wrote:Hi champagne,

Your solver is impressive.

champagne wrote:If you are interested in knowing more about my own solver, I can develop


I downloaded version labeled "Version: V1.0.0 dated June 24th 2011", and after some reverse engineering found the basic command line syntax. It runs about 30-200 times faster than SE, processing a batch of 300K non-average puzzles in 1h 23'.

Some basic documentation is welcome. It is up to you in choosing where or whether to open a discussion.

Cheers,
MD


Let me first summarize what has been done.

I have my own solver written in C++ using windows to define options for a batch.
That solver has no "on line solving capability".

That solver is also much faster than serate but works on a completely different set of rules in the high ratings.

The idea of creating a clone for serate came last year and has been discussed long

team-project-c-or-c-explainer-like-rating-program-t30083.html

When it appeared to me that nothing would come out of that discussion, I started (as PIsaacson) to draft something out of my own code.

You likely know all the story as you have been part of the discussion.

I thought first I could re use most of my code, but it appeared quickly that the philosophy was so different that I had to make a new lay out following SE strategy.

What remains from my code in skfr is

. basic principles to handle a puzzle
. the code for the lowest ratings.

Helped by Patrice, we made changes in the code to make it easier to include in other software and to produce the documentation out of the source code.

To open the team work to others, we created a project in the Google data base

In fact, it seems not so easy to find somebody

. No reluctant to work in a team
. Having some free time to dedicate to the team
. Willing to invest in the Sudoku software

So I am in fact the main actor up to now, grasping the free time of Patrice.

If you meet the three pre requisite you are welcome and can come with us.

Documentation

As i told earlier, trying to follow the best practices, we intend to include the documentation in the files.

Patrice is the leader in that field but he is very occupied for the time being and I'll ask him to comment more precisely if you want to go deeper.

The command line syntax is described in the file opsudocmd.h

this is the last status of that file (I just updated the project data base to have it correct on line)

Code: Select all
 * warning: all commands using the signs < > must be given within " "  eg "-d<6.2"
 *
 * <li>-d   stop if not diamond also --diamond</li>
 * <li>-p   stop if not pearl also --pearl</li>
 * <li>-D   same as diamond possible deviation 0.2</li>
 * <li>-P   same as pearl possible deviation 0.2</li>
 * <li>-d>  stop if ED lower than    -d&gtxx.y</li>
 * <li>-d<  stop if ED higher than   -d&ltxx.y</li>
 * <li>-p>  stop if EP lower than    -p&gtxx.y</li>
 * <li>-p<  stop if EP higher than   -p&ltxx.y</li>
 * <li>-r<  stop if ER higher than   -r&ltxx.y</li> 
 *
 * only one of the following limitations should be given,
 * the last one in the command line will act
 * <li>--NoMul stop evaluation at "multi chains" (excluded) internal code 1</li>
 * <li>--NoDyn stop evaluation at "dynamic" (excluded) internal code 2</li>
 * <li>--NoDPlus stop evaluation at "dynamic plus" (excluded) internal code 3</li>
 * <li>--NoNest1 stop evaluation at "Nested level 1" (excluded) internal code 4</li>
 * <li>--NoNest2 stop evaluation at "Nested level 2" (excluded) internal code 5</li>
 * <li>--NoNest3 stop evaluation at "Nested level 3" (excluded) internal code 5</li>
 *
 * <li>-Q   Quick classification for nested level </li>
 *
 * <li>-t   allow printing of the solution (test mode)</li>
 * <li>-n()xx.y  if after n cycles highest rating still lower than xx.y
 *      forces split mode</li>
 * <li>-e  elapsed time per puzzle (total for benchmark allways given)</li></ul>
 * The following options are processed outside that class<ul>
 * <li>-i input file also --input=</li>
 * <li>-s split treatment if dm or dl (or both) defined and forced if -n() defined</li>
 


you can find also in that thread the preliminary doc I prepared, but meantime, many names have changed.

comments on skfr V 1.0.0

basically, that release covers the ratings up to level 2 in serate. (nested forcing chains)
in fact, the code does not cover all cases processed by serate;
reversely the process go deeper in the search of the "shortest path" and rates very often .1 or .2 below serate for the chains.

This is the first draft for the code and many tests have stiil to be done.
We have identified several areas of improvement and the final code should be significantly faster in the high ratings.

The speed ratio we have seen is in the order of magnitude you got.

Version V.1.1.0 should differ from that one mainly on the following points:

. adjustment of the process for the level 2
. validation of the process for the commands --NoMul .....

Version including level 3 of serate (nested multi chain) should not be to long to create.


I'll comment in the next post on my own solver.

champagne
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Sat Sep 10, 2011 8:15 am

My own solver

First of all, my solver in part of my personal tool handling all available services in the Sudoku field.
This is in some way similar to what Glen achieved in his program, but I have not the same "services" included

The solver differs from serate mainly for chains handling.

It does not take care of the "length" (at least not directly)

It processes
. groups of candidates
. "Almost Hidden Sets" or "Almost cells"
a group of cells in the same row/column/box with only one free candidate
(BTW complementary to an ALS)
. "AAHS" or "AC2"
a group of cells in the same row/column/box with 2 free candidate
. with a special handling for
SK loop
EXOCET
. symmetry of given
. Allan Barker model in specific conditions.

Contrary to Sudoku Explainer, the process is not "left oriented".

My solver build progressively more and more complex aggregates generating new weak links and try to find new chains using these aggregates.

"AC" and "AC2" are providing new strong links.


That program could be shared with anybody running a PC. It had been compiled using Microsoft Visual C++ express platform, as for skfr.

Contrary to skfr, nothing has been done to make the sources accessible to others and the print is not so easy to decipher.

What I would like to do is the following :

1) to use the google project skfr to deliver the sources
2) to create a new project named skmpp (sudoku multi purpose program)
3) to integrate slowly a cleaned version of my code sharing as much as possible the code fo skfr
I likely would start in that case with the generation of puzzles and keep the solver for the last step.
I have nearly no re design to do in the first case,
I have to think more on how to merge both solvers skfr and skmpp.
4) In the move of my solver to smpp, I would introduce more "nice logic" similar to the "Indirect XWing" in serate.
This should lead to much nicer paths for some puzzles with a reasonable rating.

These are just ideas thrown in the bath.

The final result will depend on how much time I can dedicate to that, unless somebody want to share the burden.

champagne
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Test Cases

Postby dobrichev » Sun Sep 11, 2011 11:28 am

Hi,

Are there some test puzzlesets for
- regression testing
- performance testing?

Assuming the top N hardest puzzles incorporate variety of hard and not-so-hard techniques is making them a candidate for performance testing.

This is not the case for regression tests. They could be used for such purposes only if the whole solution path is dumped and compared between different releases, which seems impracticable.

Any suggestions?

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Test Cases

Postby champagne » Sun Sep 11, 2011 5:38 pm

dobrichev wrote:Hi,

Are there some test puzzlesets for
- regression testing
- performance testing?

Assuming the top N hardest puzzles incorporate variety of hard and not-so-hard techniques is making them a candidate for performance testing.

This is not the case for regression tests. They could be used for such purposes only if the whole solution path is dumped and compared between different releases, which seems impracticable.

Any suggestions?

Cheers,
MD


Good question.

One problem with serate is that the path is not directly visible. This is something one can overcome to a certain extent with the low ratings, but it becomes a true problem for higher ratings.

Patrice made some modifications in serate to extract the path in html form. This will help.

Performance testing and first validation for skfr have been done so far using the pattern game results.
We have there a wide variety of situations although the sample is biased due to the pattern game rules.

For higher rating, we can use the data base of "potential hardest" as source to create a sample file.

The regression test file is harder to build. I red in the pattern game that gsf had prepared one. May be we should ask him what he did. I am afraid we will have to detect puzzles covering each piece of code and to build slowly the most efficient one.

champagne
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby dobrichev » Wed Sep 14, 2011 7:03 pm

Hi champagne,

The latest version R19 of skfr failed to rate this puzzle
Code: Select all
.......12....13..4..42..5....14...5..3..6....7....8.....29....1.6..7....8.....9..


Original SE in UI mode rated it 11.0, making it a candidate for your hardest collection.

Is there a known upper limit for skfr application (excluding bugs and still undiscovered harder puzzles)?

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Cloning Sudoku Explainer thru tagging

Postby champagne » Wed Sep 14, 2011 8:40 pm

dobrichev wrote:Hi champagne,

The latest version R19 of skfr failed to rate this puzzle
Code: Select all
.......12....13..4..42..5....14...5..3..6....7....8.....29....1.6..7....8.....9..


Original SE in UI mode rated it 11.0, making it a candidate for your hardest collection.

Is there a known upper limit for skfr application (excluding bugs and still undiscovered harder puzzles)?

Cheers,
MD


r19 is limited to level 2 in Sudoku Explainer.

This is "dynamic chains plus nested forcing chains"

Level 3 "dynamic chains + nested forcing chains + nested region eliminations" is written, but not yet tested and not delivered to the google project.

Level 4 "dynamic chains + nested dynamic" has still to be investigated.

A "level 5" exists with two level of nesting, but I have doubt it has never been used.

Level 2 is a 9.5 base. The upper limit can pass the rating 11.0, but most of the puzzles of that family are in the range 10.0 10.5.
If SE finds an elimination at level 2, it does not search for a shorter rating at level 3

For the time being, i use skfr to select puzzles and I submit the un rated puzzles to Sudoku Explainer.

When level 3 will be tested, I'll start to replace the SE rating by the skfr rating in the data base.

I delayed tests of level 3 to revise my process for non minimal puzzles after you recently published your 10.4.

I am very close to have quite interesting results to post using your example.

champagne

PS I'll check to morrow how SE solve your puzzle. The level 2 has not yet reached the beta test state and I am not 100% sure I covered all the process of SE at level 2
champagne
2017 Supporter
 
Posts: 5639
Joined: 02 August 2007
Location: France Brittany

Re: Cloning Sudoku Explainer thru tagging

Postby ronk » Thu Sep 15, 2011 1:33 am

champagne wrote:I delayed tests of level 3 to revise my process for non minimal puzzles after you recently published your 10.4.

That's an interesting comment. Why should a rating program "care" whether or not a puzzle is minimal?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Pat » Thu Sep 15, 2011 8:01 am

ronk wrote:
champagne wrote:I delayed tests of level 3 to revise my process for non minimal puzzles after you recently published your 10.4.

That's an interesting comment. Why should a rating program "care" whether or not a puzzle is minimal?

it doesn't

    champagne's comment -- "to revise my process for non minimal puzzles" -- refers to his other activities, not to the rating software
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Next

Return to Software