The New Sudoku Players' Forum

[ronk]

Whenever there has been mention of changing the ratings there seems to be quite a lot of resistance. A lot from Ron - a perception, sorry if I am mistaken - and yet Ron you said, in the 5th post of this thread :

In the end, duplicating the solution path of Sudoku Explainer will, I believe, be the most difficult challenge. If that doesn't happen, ratings would assuredly change. However, if the compiled Explainer is really fast, we might not mind recalculating some ratings.

Why the change?

I don't believe I've changed my position. When I wrote "recalculate some ratings" I was thinking some ratings ... some ratings ... at ER>10 or even ER>11. I certainly wasn't thinking of changing ratings as low as ER=4.6, as seems to have already happened.

The project may be bogged down now trying to duplicate SE ratings, but IMO it would get bogged down a lot worse trying to reach a consensus on rating assignments for new techniques.

[BryanL]

I don't believe I've changed my position. When I wrote "recalculate some ratings" I was thinking some ratings ... some ratings ... at ER>10 or even ER>11. I certainly wasn't thinking of changing ratings as low as ER=4.6, as seems to have already happened.

Fair enough.

The project may be bogged down now trying to duplicate SE ratings, but IMO it would get bogged down a lot worse trying to reach a consensus on rating assignments for new techniques.

It seems that there will be some change - however subtle, to some techniques.

My thinking is to bring it out into the open. Have a wholesale acceptance that "some" ratings may be changed for the better. Once that is agreed, everyone can discuss those areas and give their input, logical or otherwise, and then a decision will be reached. Most, if not all, here, follow a scientific method in their approach and the cream will rise to the top.

An example that I feel needs attention is that of batch processing in some areas.

I will seed the discussion by saying that for sure batch processing would slow down the whole rating system if applied unilaterally. But I think - from what I have read - it is only needed in the areas of uniqueness tests and maybe also some chain techniques? So would only be used there.
I also feel that application of method in these areas is just as important as the methods themselves - as previously indicated where multiple solution paths exist with different ratings. This could be a tough one and some trial and error needed until a generally accepted or best fit method appears.

So these things get discussed until the most acceptable approach is found. And the guys putting in the real coding effort - and anyone that follows - has a solid, agreed upon, foundation to work from.

And for a second point - and honestly I don't care either way - but for completeness, the couple of holes in the direct versus indirect hidden pairs and locked candidates can be cleaned up so there is no ambiguity. What I mean is that if a hidden pair is in a row/col and also a box, an exposed single in either the row/col or box will give a direct hidden pair rating. Similar, if opposite logic, for direct locked candidates.

A fallout of this process could be a clean up of the odd definition of some of the solving techniques on some of the sites like Sudopedia. I can't say there are any that are wrong - just from a couple of recent discussions I have read there seems to be some ambiguity with some of them...

Bryan

[PIsaacson]

I will seed the discussion by saying that for sure batch processing would slow down the whole rating system if applied unilaterally.

Not necessarily so. Using my scorer's runtime param -E0 (quasi-batch accoring to LK) vs -E1 (SE exiting strategy) shows that the SE like approach scores about 680 puzzles/second and takes 53.8 seconds, while the -E0 option scores 1030 puzzles/second and takes 35.6 seconds for the royle17 collection. Since the -E0 option was supplied as a runtime param, it overrode the sudoku.ini file settings and forced all techniques to continue processing until they could make no further progress rather than return upon the first successful assignment/elimination.

What batch processing does differently is to generate a solution path which is an aggregate of multiple SE solution paths. More coding/testing is needed to determine whether or not batch processing can score exactly the same as a single (I won't use the word random) SE solution path out of the many possible solution paths.

And for a second point - and honestly I don't care either way - but for completeness, the couple of holes in the direct versus indirect hidden pairs and locked candidates can be cleaned up so there is no ambiguity. What I mean is that if a hidden pair is in a row/col and also a box, an exposed single in either the row/col or box will give a direct hidden pair rating. Similar, if opposite logic, for direct locked candidates.

LK and I exchanged some ideas regarding this, so I've added a "conformance" parameter to the sudoku.ini configuration file. Some techniques, such as those quoted above, are sensitive to the conformance parameter and will process differently depending on the degree of conformance specified. Currently conformance is either an on/off condition, but it has the capability to describe various "flavors" of conformance if necessary.

Although it may not seem like it at times, I fully agree that the goal of an SE clone is to score exactly the same as SE. But, I'm also developing a framework that provides the options to explore alternative scoring approaches. Using the sudoku.ini configuration file, you can specify the order of execution for techniques, their base score, their exiting strategy, expanding depth constraints for things like UR loops or any depth sensitive chaining technique including ALS chains (try to find those with SE), conformance criteria and trace logging levels. Since there was very little consensus on content or direction, I felt like the best thing was to provide as flexible of a tool as possible. Meanwhile, I'm still waiting for that flood of algorithms from fellow sudoku coders...

Cheers,
Paul

[champagne]

The project may be bogged down now trying to duplicate SE ratings, but IMO it would get bogged down a lot worse trying to reach a consensus on rating assignments for new techniques.

I have a very simple view on that after so many people digged in SE code and found many many "strange" things.

Either we want to stick to the existing SE rating and the best way is "not to change" the code except may be turning more to a batch processing.

Expected performance ratio somewhere in the range 1 to 5. Not very exciting.

Or we are really looking for a significant improvement in speed, say a ratio 1 to 100 as a target.

Then the process must be deeply changed and adjustments in the rating are unavoidable.

I don't know if the target 1 to 100 is realistic, I make tests in that direction, staying as close as possible of SE specs.

champagne

[tarek]

My impression from the beginning is that this project is after:

1. Creating a C++ clone of SE because it makes things quicker than JAVA (even if it's a 2x improvement )

The techniques, Heirarchy & score Ratings are clear in seperate files which will make it easy to change any of these 3 variables in the future.

2. The next step would be to fix the bugs.

3. The third step is to introduce changes to improve speed (At this point we already have a program that satisfies points 1 &2).

4. The final step is to add several options to improve the quality of solving & rating (batch processing, min-lex & change or add techniques.

I know I'm arriving pretty late in this process. I'm hoping however that the above is what has been carried out because it will allow a functional program if the process stopped at any of the stages.

tarek

[JasonLion]

Meanwhile, I'm still waiting for that flood of algorithms from fellow sudoku coders...

More people will get involved when there is an accepted framework released under an open source license that they feel comfortable with. I'm just guessing, but I suspect that "accepted" probably means two or three people working on the same source code that is posted publicly and where source submissions from outside the core group are being accepted into the main branch relatively rapidly, at least in most cases. The choice of an open source license that will encourage contributions is a little less obvious, but equally important.

My take is that we are on the edge of critical mass, but not quite there. There are a couple of people working on the project, who appear to have made a lot of progress. But there isn't an effective framework for working together. I assume that many people are like me: Waiting until the dramatic amounts of progress that have already been made by others are released in a form where we can contribute without having to duplicate all of the work that has already been done.

I don't know if the target 1 to 100 is realistic, I make tests in that direction, staying as close as possible of SE specs.

I am fairly sure that a speedup of better than 20 times is going to happen. The SE source code is massively inefficient, both in algorithm design and in coding details. SE does straightforward brute force searches for each technique with little to no attempt to prune the search space. Likewise the fine grained coding details seem to be aimed at logical simplicity rather than trying to take even the simplest optimizations into account.

I will seed the discussion by saying that for sure batch processing would slow down the whole rating system if applied unilaterally.

My experience is the same as PIsaacson's. My ratings solver (not at all SE compatible) is also faster in batch mode than it is in "apply first technique found" mode. There are a few techniques that are faster in find first mode, but there are enough other techniques that are faster in batch mode to more than make up for it.

[PIsaacson]

More people will get involved when there is an accepted framework released under an open source license that they feel comfortable with.

Jason,

My code is currently copyrighted with the GNU GPL, but my framework includes a modified version of Brian Turner's BB brute-force solver which contains a simple copyright declaration:

Code: Select all

/****************************************************************\
**  (c) Copyright Brian Turner, 2008-2009.  This file may be    **
**      freely used, modified, and copied for personal,         **
**      educational, or non-commercial purposes provided this   **
**      notice remains attached.                                **
\****************************************************************/

I also use the canon function extracted from Glenn Fowler's (gsf) sudoku.c in one branch of my code that always forces scoring on the minlex version of the puzzle. I believe his code is covered under http://www.opensource.org/licenses/cpl1.0.txt so if I want to be compatible, I need to confirm that there's no conflict between any of these.

I haven't released the code for general usage because I'm making so many changes/decisions each week, plus I haven't documented it at all. When I have sufficient stability and documentation, I'll create a project on SourceForge, "SudokuExplainer Clone" or some other catchy title.

Cheers,
Paul

[edit] P.S. My brain needed a few cups of coffee before it noticed the qualifier "accepted" framework. Considering the degree of difficulty in obtaining consensus here, what constitutes "accepted"??? Should I post a brief description of my current framework design and see what happens??? I love chaos theory...

[ronk]

I also use the canon function extracted from Glenn Fowler's (gsf) sudoku.c in one branch of my code that always forces scoring on the minlex version of the puzzle.

If canonicalization is built into a solver/rating clone, I think there should be a command-line option to turn it off. For one thing, rating many different morphs of a single puzzle is an excellent test of the robustness of an algorithm's implementation. For another, it permits side-by-side comparison with Sudoku Explainer on the same terms.

[PIsaacson]

Ron,

Thanks for the input! This is exactly the kind of feedback that I need/desire. Your wish is my command...

Cheers,
Paul

[JasonLion]

GPL and CPL are not compatible, while Brian Turner's license most likely is compatible with GPL. In the long run that will all need to be worked out, perhaps even require replacing some code. But in the short run it can be worked around by distributing the code in two or three separate pieces that are designed to be used together.

Accepted isn't at all the same as consensus. You can earn a lot of acceptance by doing a lot of coding and getting that code out there for people to play with. Some degree of accepting input from others is also required, but nothing like consensus. For example, many people want an exact clone of SE ratings. But not everyone working on, or using, the project needs to agree with that. I could, for example, write a solving technique that is not SE compliant, and others could avoid using it with a simple configuration setting. By allowing things like that configuration setting, the project can serve different needs/interests at the same time and thus gain wide support even when consensus is absent.

The key barrier to others working on the project right now is getting a framework in place that people can plug their solving technique implementations into. It is easy for many people to write different solving techniques in parallel, as long as the framework remains relatively stable. Talking a little bit about how your framework works, especially from the point of view of a solving technique author, would be a great place to start. Others may well have some valuable input that is simplest to take into account early on.

[champagne]

regarding the licence, the situation is very simple on my side.

My code is 100% home made and covered by no licence so far (I know I should have done it, to protect myself against anybody licensing my code, I just put a property reserve in the first post of the thread I opened.)


I red Paul's comments about its own code and the difficulty to write documentation and to work in the same time. I face the same problem.

As i'll disappear soon for more than 2 months, I put as first priority to deliver a partial draft with enough comments to give the possibility to anybody to use it (either the code or just some ideas).

I am currently stabilizing the draft in the area 6.5 7.xx and preparing comments. Delivery of that part will start soon.
If I have some more time, I'll produce a first step towards the more complex situations just to show what i have in mind;

champagne

[PIsaacson]

Jason,

Here's a brief description of my framework:

Code: Select all

My framework can be divided into several logical pieces:

1) The grid object which contains the current puzzle state and various low level methods such as

   a) Perform a single candidate elimination from a cell
   b) Perform multiple candidate eliminations from a cell
   c) Perform an assignment of a value to a cell

   The grid.cpp file contains the primary grid object definition.

The data definitions from grid.cpp are listed here for reference:

 1 class grid_t
 2 {
 3 public:
 4
 5    int       solved;               // value from 0-81 to indicate completion 
 6    int       errors;               // count of any errors performed by invalid elimations/assignments (always tracked)
 7    int       updates;              // current count of running total updates performed by the techniques
 8    int       last_updates;         // used for debugging to see if it's necessary to display the grid or not when tracing
 9
10    char      given[9][9];          // values base 1 with zero being an un-assigned cell
11
12    int       rc_cands[9][9];       // RC space with bits 0-8 used for candidates
13    int       rn_cands[9][9];       // RN space with bits 0-8 used for col indexes
14    int       cn_cands[9][9];       // CN space with bits 0-8 used for row indexes
15    int       bn_cands[9][9];       // BN space with bits 0-8 used for box offset indexes
                                      //    0-2 for upper row 3-5 for middle row and 6-8 for bottom row
16
17    inline int update_mbit (int d, int r, int c);
18    inline int update_mbits (int mask, int r, int c);
19    inline int update_cell (int d, int r, int c);
20
21    int full_house (int depth);
22    int naked_single (int depth);

2) The driving code is contained in the sudoku.cpp file.  This is the main compilation unit and it uses #include to source in all the *.cpp files which include all the techniques and various common initialization code methods.  It is responsible for processing the run time arguments using getopt_long and for reading the configuration sudoku.ini file to establish which techniques will be used in what order and with what operational constraints.  There is a driver loop that uses a function pointer table to the methods and calls each method in order and with parameters defining:

   a) Exiting strategy set either by a param in the sudoku.ini file for each technique, or by a global override as a runtime param
   b) Conformance level set the same way as in (2a) above
   c) The max allowed depth for this call set by 3 params in the sudoku.ini file, or by a global override as a runtime param

Here's the main driving loop from sudoku.cpp

709    // Loop through all the methods incrementing level depth as needed
710
711    int update = 1;
712
713    while (grid->solved < 81 && update != 0)
714    {
715       for (int np = 0; np < max_procs; np++)
716       {
717          sw_exiting = (sw_exiting_forced ? sw_exiting : proc_ptr[np].pexiting);
718          sw_se_conform = (sw_se_conform_forced ? sw_se_conform : proc_ptr[np].pconform);
719          pdepth = proc_ptr[np].pdepth;
720
721          if (pdepth == 0)
722          {
723             grid->updates += update = (grid->*proc_ptr[np].pmethod) (chain_max);
724
725             if (puzzle_pearl_found == false && init_updates != grid->updates)
726                puzzle_pearl_found = true, puzzle_pearl_score = puzzle_score;
727
728             if (puzzle_diamond_found == false && init_solved != grid->solved)
729                puzzle_diamond_found = true, puzzle_diamond_score = puzzle_score;
730          }
731          else
732          {
733             int pmin = proc_ptr[np].pmin;
734             int pmax = proc_ptr[np].pmax;
735             int pstep = proc_ptr[np].pstep;
736
737             if (sw_nrc_forced && pdepth == 2)
738             {
739                pmin = chain_min;
740                pmax = chain_max;
741             }
742
743             for (int step = pmin; step <= pmax; step += pstep)
744             {
745                int depth = (pdepth == 2 ? steps[step] : step);
746
747                grid->updates += update = (grid->*proc_ptr[np].pmethod) (depth);
748
749                if (puzzle_pearl_found == false && init_updates != grid->updates)
750                   puzzle_pearl_found = true, puzzle_pearl_score = puzzle_score;
751
752                if (puzzle_diamond_found == false && init_solved != grid->solved)
753                   puzzle_diamond_found = true, puzzle_diamond_score = puzzle_score;
754
755                if (update)
756                   break;
757             }
758          }
759
760          if (update)
761             break;
762       }
763    }

3) The techniques themselves written as methods and using a defined structure:

   a) Each technique is contained in a *.cpp file named the same as the technique in lower case only for compatibility with non-case sensitive OSes such as Windows.

   b) Each technique's entry is grid_t::technique_name (depth) where depth is controlled by the sudoku.ini depth params for depth limited type of functions.

   c) Upon receiving control, the technique must use the start_stats (technique_name) macro to track time usage and calls

   d) The technique must declare three local ints:

      int change;
      int update = 0;
      int exiting = 0; 

   e) The technique must use the standard low level methods to manipulate the grid

      change = update_mbit (digit, row, col);  with digit/row/col containing the values 0-8 for the base 0 indexes used in the grid object
      change = update_mbits (mask, row, col);  with row/col base 0 indexes and the mask containing bits 0-8 set to the candidates to eliminate
      change = update_cell (digit, row, col);  with digit/row/col containing the base 0 indexes described above   

   f) After calling one of the above, the technique must:
     
      update += change;        // increment the success count

           
      float temp_score = proc_tbl[technique_name_enum].pscore;  // test if the score is advanced
      puzzle_score = (change && temp_score > puzzle_score ? temp_score : puzzle_score);

      if (sw_verbose && (change || errors))   // test whether to list the actual step via formatting the output
      {
         printf (".......", params)           // all output follows a standard format given later
      }

   g) After testing for printing, the technique must check the exiting strategy:

      if (change && exit_check (digit, row, col))
         goto technique_name_exit;

naked_single.cpp is listed here in full as an example:
     
 1 int grid_t::naked_single (int depth)
 2 {
 3    start_stats (naked_single);
 4
 5    int change = 0;
 6    int update = 0;
 7    int exiting = 0;
 8
 9    // Test all the cells for naked single
10
11    for (int n = 0; n < 81; n++)
12    {
13       int r = n / 9;
14       int c = n % 9;
15
16       if (given[r][c] != 0)
17          continue;
18
19       int mask = rc_cands[r][c];
20
21       // RC space single value - only value left for this cell so it's a naked single
22
23       if (cands2n[mask] == 1)
24       {
25          int d = next_bit (mask);
26
27          change = update_cell (d, r, c);
28          update += change;
29
30          float temp_score = proc_tbl[naked_single_enum].pscore;
31          puzzle_score = (change && temp_score > puzzle_score ? temp_score : puzzle_score);
32
33          if (sw_verbose && (change || errors))
34             printf ("%3d) %4.1f r%dc%d <= %d naked single\n", ++stepno, temp_score, r + 1, c + 1, d + 1);
35
36          if (change && exit_check (d, r, c, exiting))
37             goto exit_naked_single;
38       }
39    }
40
41 exit_naked_single:
42
43    end_stats (naked_single);
44
45    return (update);
46 }

4) Fitting a technique into the framework after writing it requires:

  a) Modifying sudoku.cpp to #include the source and adding lines to initialize the proc_tbl and to create the statistics functions
  b) Modifying grid.cpp to include the necessary method definitions       
  c) Modifying grobal.h to include the necessary macros to define the statistics counters


Does this help???
Paul

[dobrichev]

2 suggestions:
- replace float with a user defined type, it probably will change in the future.
- store all globals into a structure/class, and add it as a parameter to necessary macros/functions - one more level of indirection but easier backtracking/debugging/parallelization.

[ronk]

2 suggestions:
- replace float with a user defined type, it probably will change in the future.
- store all globals into a structure/class, and add it as a parameter to necessary macros/functions - one more level of indirection but easier backtracking/debugging/parallelization.

Indeed, in the third post of this thread ...

internally the rating number would be integers (se rating * 10) to avoid floating point anomalies

[tarek]

Indeed, in the third post of this thread ...

internally the rating number would be integers (se rating * 10) to avoid floating point anomalies

In case you want to add several techniques in the future with a required "different rating", you may find that integers of (se rating * 100) would allow new ratings xx.xx & keep the original look, feel & ratings.

tarek