The New Sudoku Players' Forum

[lksudoku]

2) Yes, but if the draft is internal, than why bother

item 2) I don't catch your point. For sure, I assume the draft (which one it is) has been published.

Paul's code was sent to me some time ago, and I assume it was sent to you also, however, since then I got no updated version (and I assume neither did you), and the code (current and older modified by me for SE) is internal in the sense that only me you and Paul hold it (maybe you do not hold the SE clone modification though), no other person has access to the executable or sources

Suppose now that I will continue modifying that code to match all SE (not likely to happen though), and only me Paul and maybe you will hold that version, this means I modified a clone but the clone is internal for only 3 people to use

I rather create a clone which is open to everyone

[PIsaacson]

...only me Paul and maybe you will hold that version, this means I modified a clone but the clone is internal for only 3 people to use...

It's not quite fair to state that "the clone is internal for only 3 people to use...". Excluding myself as a given, only you and Champagne have actually taken up my offer, sent me a PM and got a snap-shot of the code via e-mail. It's still a "moving target" and I'm not comfortable posting the code for general release, hence the exclusivity.

I've promised to keep you current with additional snap-shots, and I will e-mail both of you one soon. Just be ready for the fact that over 20% of the code you've already received has been extensively changed. I believe I've merged in all of your bug fixes and suggested changes to conform more closely with SE, but as you'll see, the changes are conditional upon a conformance parameter within the sudoku.ini file on a method by method basis, or controlled by an override global run-time switch.

Although SE doesn't have any ALS techniques, I decided just for kicks to merge in my ALS engine which detects fairly complex rank-0 doubly-linked ALSs and DBs. I still think that whatever this turns into, it should still include as many "modern" techniques as possible. Again for any of you programmers out there: If you have a technique (how about a really fast Sue-de-Coq) that you would like to contribute, I'd be more than happy to take your algorithm/code/design and modify it to fit into my current frame-work or send you a snap-shot so you can play with it. I'm trying to find time to document how to write a conforming C++ sudoku technique to make it easier to contribute, but as gsf states in his sudoku man page (and this has become my mantra of late, so thanks Glen): "It's easier to solve than to generate, and easier to generate than to rate, and much easier to code than to document."

Cheers,
Paul

[RW]

Therefore the only difference (below 6.5) is in the puzzle

001002003020010400300900070006000004010090030800000900030004007004050090600700200 4258 6.00 5.60

Which is the puzzle I mentioned in which there are 3 possible UR type 1, and choosing two of them yields 6.00 rating while choosing the third one yields a 5.60 rating

This rating difference cannot be avoided because it depends on the choice of a UR out of a list of more than one, when choosing one destroys the other (and all choices are correct for the specific step as they have the same rating)

This could be easily fixed in an updated version. In the case of UR type 1, you don't need to consider the target cell at all. Three corners of an UR type 1 always eliminates both UR candidates, even if they are not present in the target cell anymore. So basically a code that looks for UR type 1 should only look for the three corners. Once they are found, it eliminates the candidates from the target cell, if they are present.

In the case of UR type 4, the code should look for the pair 'ab' and the strong link on 'a' or 'b' that together could create the UR. Once found, the other candidate is eliminated from the strong link cells, if they are present.

These two fixes should correct the rating for this particular puzzle.

In the case of UR type 2 and 3, the cells with extra candidates do not need both candidates a and b to perform the elimination. As long as one has 'a' and the other has 'b' the elimination can be done, thus the solver shouldn't look for anything more than this pattern:

Code: Select all

ab | aX
ab | bX

There is still the problem that may occur if one UR cell is somehow solved, which in the case of a UR type 1 leads to this pattern:

Code: Select all

A  | B
B  | aX

where none of the cells A and B are given. To fix this problem, the solver needs to keep track of which cells are among the original given cells and which are solved cells and treat them differently when applying uniqueness techniques. Any solved cell A can be treated as a candidate pair ab when looking for uniqueness eliminations. In the case above, the solver would then see the three corners of the UR type 1.

If it makes things faster, you could say that any solved cell A can be treated as a candidate pair ab where b is a candidate present in that cell in the initial grid (before any eliminations), or even restrict the value of b to any candidate that has been eliminated from that cell with a technique rated 4.2 or higher. The lower rated techniques cannot destroy a potential UR (neither can Jellyfish or Quads, so candidates eliminated by these could also be excluded). Actually, I don't think even an XY-wing can solve a cell in a potential UR without also solving itself, thus making the UR elimination, but I'm not 100% sure about this. But this restriction of candidate b is not necessary, because even if B is a given candidate in the same unit, you won't find any UR anyway.

These same rules can be applied to BUG-lites. Using these fixes, you will always find these URs, even if they don't appear at the time in the solving path.

RW

[Edit: Alternatively all problems mentioned above can be fixed in one sweep by having all uniqueness techniques treat all candidates eliminated by techniques rated 4.2 or higher (excluding Jellyfish and Quads) as candidates that may or may not be present. Though I'm not sure how easy this is to implement...]

[lksudoku]

This could be easily fixed in an updated version. In the case of UR type 1 ...

What you suggest is close to changing form unique loops to unavoidable sets, but I am not sure if this is the correct handling as some users may want to just find UR/UL and not unavoidable sets which are harder to find

The lower rated techniques cannot destroy a potential UR

Not necessarily, theoretically, choosing one UR (or UL) may result in a sequence of lower rated techniques that will evetually destroy another UR/UL

Basically I think this is a common property to all uniqueness based techniques as already discussed in the Bugs, Quirks and Other Remarks thread

I think that the best solution for this property is to implement what Danny suggested, which is, to find all current rating moves simultaneously before applying them (otherwise known as batch mode)

This way, in the UR/UL cases, all of them will be found in the first time, and then applied simultaneously, and so, the order in which the UL/UR are applied will not matter, this will also solve the BUG possible problem (again uniqueness based technique)

Maybe I will add this solution to the SE serate program, adding this solution to Paul's C/C++ code is a little more complicated but can be done

[champagne]

I think that the best solution for this property is to implement what Danny suggested, which is, to find all current rating moves simultaneously before applying them (otherwise known as batch mode)

This way, in the UR/UL cases, all of them will be found in the first time, and then applied simultaneously, and so, the order in which the UL/UR are applied will not matter, this will also solve the BUG possible problem (again uniqueness based technique)

Maybe I will add this solution to the SE serate program, adding this solution to Paul's C/C++ code is a little more complicated but can be done

I would agree with that except that the rating constraint is to take only moves having the same rating.

I faced that problem as others. To produce in the same time all UR/UL having an equal rating, I am working during all that search on a stored and untouched copy of PMs.

champagne

[RW]

What you suggest is close to changing form unique loops to unavoidable sets, but I am not sure if this is the correct handling as some users may want to just find UR/UL and not unavoidable sets which are harder to find

In the case of Uniqueness patterns with solved cells, yes, you have to think a bit about unavoidable sets to find them. These are extremely rare, so I don't think they need to be implemented. If they are they should be implemented as a separate technique, because they are very different from basic UR's/UL's.

My first proposals for fixes are not related to unavoidable sets IMO. It's all about considering the minimum amount of information required for an elimination. Currently SE requires a deadly pattern hidden among the candidates to make uniqueness eliminations. All uniqueness tutorials also teaches us to look for UR's this way. It is WRONG! If a solver requires a deadly pattern among the candidate, he will miss eliminations because he is requiring unnecessary information. To use any technique correctly, you must first know the minimum conditions that must be met to allow the elimination. Currently, SE doesn't know these. The minimum conditions for UR type 1-4 are listed in my post above.

The lower rated techniques cannot destroy a potential UR

Not necessarily, theoretically, choosing one UR (or UL) may result in a sequence of lower rated techniques that will evetually destroy another UR/UL

If a potential uniqueness pattern is altered by a lower rated technique (strictly speaking, any technique that eliminates a candidate from a target unit), the whole pattern falls apart and the eliminations that could have been made by the potential uniqueness pattern are directly made by lower rated techniques. To alter the uniqueness pattern to such a small degree that it is still yields useful eliminations (eliminations that cannot be made in an easier way), you need a technique that eliminates a candidate from one target cell, not a target unit = most techiques rated 4.2 up.

I think that the best solution for this property is to implement what Danny suggested, which is, to find all current rating moves simultaneously before applying them (otherwise known as batch mode)

This way, in the UR/UL cases, all of them will be found in the first time, and then applied simultaneously, and so, the order in which the UL/UR are applied will not matter, this will also solve the BUG possible problem (again uniqueness based technique)

This only fixes the problem with different ratings between different permutations. If the UR's appear at different times in the solving path, you won't find the second one. Neither will you find a UR where one candidate from the target cell can been eliminated by a XY-wing. These will not cause rating differences between your different versions, but they will still cause SE to overrate a lot of puzzles.

RW

[daj95376]

The problem with discussing URs is their sensitivity to overlapping and subsequent effects -- even from other techniques. As for the puzzle mentioned by LK, concurrent/batch doesn't help the potential UR Type 4 elimination that follows. At this point, the traditional definition fails and an approach such as RW suggested is needed to take its place.

Code: Select all

 from my solver at the point of concurrent UR Type 1
 +-----------------------------------------------------------------------+
 |  49     69     1      |  468    7      2      |  56     568    3      |
 |  5      2      7      |  368    1      368    |  4      68     9      |
 |  3      46     8      |  9      46     5      |  1      7      2      |
 |-----------------------+-----------------------+-----------------------|
 |  79     59     6      |  12358  28     138    |  78     12     4      |
 |  47     1      2      |  4568   9      68     |  78     3      56     |
 |  8      45     3      |  12     46     7      |  9      12     56     |
 |-----------------------+-----------------------+-----------------------|
 |  1      3      9      |  28     28     4      |  56     56     7      |
 |  2      7      4      |  16     5      16     |  3      9      8      |
 |  6      8      5      |  7      3      9      |  2      4      1      |
 +-----------------------------------------------------------------------+
 # 43 eliminations remain

 r46c48  <12> UR Type 1.2225             <> 12   r4c4
 r47c45  <28> UR Type 1.2225             <> 28   r4c4
 r17c78  <56> UR Type 1.2223             <> 56   r1c8


Code: Select all

 +--------------------------------------------------------------+
 |  49    69    1     |  46    7     2     |  5     8     3     |
 |  5     2     7     | *38    1    *38    |  4     6     9     |
 |  3     46    8     |  9     46    5     |  1     7     2     |
 |--------------------+--------------------+--------------------|
 |  79    59    6     | *3+5   28   *38+1  |  78    12    4     |
 |  47    1     2     |  4568  9     68    |  78    3     56    |
 |  8     45    3     |  12    46    7     |  9     12    56    |
 |--------------------+--------------------+--------------------|
 |  1     3     9     |  28    28    4     |  6     5     7     |
 |  2     7     4     |  16    5     16    |  3     9     8     |
 |  6     8     5     |  7     3     9     |  2     4     1     |
 +--------------------------------------------------------------+
 # 31 eliminations remain

 r24c46  <38> UR Type 4.2223             <> 8    r4c6 *


My solver looks for UA-4 patterns in non-clue cells and then checks to see if a UR-type elimination can be derived.

Code: Select all

 after detecting this UA-4 pattern
 <38> bivalues in [r2] and X-Wing on <3>
 is acceptable to my UR Type 4
 +-----------------------------------+
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |  .  .  .  |  8  .  3  |  .  .  .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |-----------+-----------+-----------|
 |  .  .  .  |  3  .  8  |  .  .  .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |-----------+-----------+-----------|
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 |  .  .  .  |  .  .  .  |  .  .  .  |
 +-----------------------------------+


Regards, Danny

[lksudoku]

The problem with discussing URs is their sensitivity to overlapping and subsequent effects -- even from other techniques. As for the puzzle mentioned by LK, concurrent/batch doesn't help the potential UR Type 4 elimination that follows. At this point, the traditional definition fails and an approach such as RW suggested is needed to take its place.

Batch/concurrent solving will not always yield the lowest possible rating out of all the possible paths, as shown, however, it will make sure all isomorphisms have equal ratings, and random choice of move will not effect the rating, thus when a clone has several different unique moves of the same lowest rating, it will not have to choose the same move as SE does

The RW approach does yield lowest rating, but I am not sure it remains in the same definition as UR/UL

[EDIT:]And that makes me think of another approach, and that is:
When there are several UR/UL moves of the same rating and one of them should be chosen, the status of the puzzle will be saved and then all different moves will be tried, one after the other thus exploring all possible paths, and at the end, take the minimal rating out of all the different choices

[tarek]

I want to thank everyone involved in this project. I'm hoping that I'll find the time to participate more actively in this process.

Batch/concurrent solving will not always yield the lowest possible rating out of all the possible paths, as shown, however, it will make sure all isomorphisms have equal ratings, and random choice of move will not effect the rating, thus when a clone has several different unique moves of the same lowest rating, it will not have to choose the same move as SE does

I found that the simplest solution to the ismorphism bias (this has been mentioned by others in the hardest sudokus thread) is to solve & rate using the min-lex version of the puzzle.

From experience in other threads (Superior, Pure fish, ...) .... The solving path issue has always been a headache & my feeling is that batch solving could be the FAIREST of them all . This should be for rating purposes.

Another issue is to see if batch mode & method heirararchy can be configurable to satisfy wider tastes. if that happens, we should be using the method heirarchy & batch mode options from in the Patterns game when citing SE ratings.

tarek

[RW]

The RW approach does yield lowest rating, but I am not sure it remains in the same definition as UR/UL

The problem is that the current definitions are poorly formulated. It all dates back to a long time ago when uniqueness techniques were first discovered and people didn't quite know how to handle uniqueness patterns with missing candidates. The safest option (and the obvious option) was to define them with all candidates of the deadly pattern present. Back in 2006 I proved once and for all that uniqueness patterns with missing candidates are still valid, but the patterns were never redefined. It now seems that this should be done, because programming the patterns according to current definitions will cause trouble like this. By optimizing the patterns to only contain the essential information required to perform the eliminations, we could avoid most of this trouble.

Though the definitions should be updated, it is definitely still the same technique, only a bit more polished.

RW

[PIsaacson]

My two cents on the above puzzle: The problem is not with UR processing. It's with the selection of a solution path that leads to different BUGs later in the puzzle. Here's my full solution log leading to the 5.6 rating stemming from finding a solution path that leads to a BUG type 1 instead of type 4 as in the SE solution path which resulted in the 6.0 rating:

Code: Select all

001002003020010400300900070006000004010090030800000900030004007004050090600700200 puzzle 1 starting
 4579      456789    1        |4568      4678      2        |568       568       3       
 579       2         5789     |3568      1         35678    |4         568       5689     
 3         4568      58       |9         468       568      |1568      7         12568   
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 2579      579       6        |12358     2378      13578    |1578      1258      4       
 2457      1         257      |24568     9         5678     |5678      3         2568     
 8         457       2357     |123456    23467     13567    |9         1256      1256     
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 1259      3         2589     |1268      268       4        |1568      1568      7       
 127       78        4        |12368     5         1368     |1368      9         168     
 6         589       589      |7         38        1389     |2         1458      158 
   
  1)  1.2 r3c9 <= 2 hidden single in b3
  2)  1.2 r3c7 <= 1 hidden single in b3
  3)  1.2 r2c9 <= 9 hidden single in b3
  4)  1.2 r6c3 <= 3 hidden single in b4
  5)  1.2 r9c6 <= 9 hidden single in b8
  6)  1.2 r8c7 <= 3 hidden single in b9
  7)  1.2 r9c5 <= 3 hidden single in b8
  8)  1.2 r9c8 <= 4 hidden single in b9
  9)  1.5 r7c3 <= 9 hidden single in c3
 10)  1.5 r5c3 <= 2 hidden single in c3
 11)  1.5 r2c3 <= 7 hidden single in c3
 12)  1.2 r1c5 <= 7 hidden single in b2
 13)  1.5 r9c9 <= 1 hidden single in r9
 14)  2.0 r8c2 <= 7    direct hidden pair b7x14.<12>
 15)  1.5 r6c6 <= 7 hidden single in r6
 16)  2.3 r2c1 <= 5 naked single
 17)  1.5 r3c6 <= 5 hidden single in r3
 18)  1.5 r9c3 <= 5 hidden single in c3
 19)  1.0 r3c3 <= 8 full house in c3
 20)  1.0 r9c2 <= 8 full house in r9
 21)  2.8 r4c7 <> 5 locked candidates type 2 (claiming) b6/c9
 22)  2.8 r4c8 <> 5 locked candidates type 2 (claiming) b6/c9
 23)  2.8 r5c7 <> 5 locked candidates type 2 (claiming) b6/c9
 24)  2.8 r6c8 <> 5 locked candidates type 2 (claiming) b6/c9
 25)  3.4 r4c8 <> 8    hidden pair r46c8.<12>
 26)  3.4 r6c8 <> 6    hidden pair r46c8.<12>
 27)  4.4 r5c9 <> 8 xyz-wing at r5c7.<678> 1) r4c7.<78> 2) r5c6.<68>
 28)  1.5 r8c9 <= 8 hidden single in c9
 29)  2.6 r1c7 <> 8 locked candidates type 1 (pointing) b6/c7
 30)  2.6 r7c4 <> 6 locked candidates type 1 (pointing) b9/r7
 31)  2.6 r7c5 <> 6 locked candidates type 1 (pointing) b9/r7
 32)  2.8 r5c7 <> 6 locked candidates type 2 (claiming) b6/c9
 33)  3.0 r6c5 <> 2    naked pair r47c5.<28>
 34)  3.4 r6c4 <> 456  hidden pair r6c48.<12>
 35)  3.2 r1c2 <> 4 x-wing r36\c25
 36)  4.4 r8c4 <> 2 xyz-wing at r7c4.<128> 1) r6c4.<12> 2) r7c5.<28>
 37)  1.5 r8c1 <= 2 hidden single in r8
 38)  1.0 r7c1 <= 1 full house in b7
 39)  4.5 r4c4 <> 12   unique rectangle type 1 1/2 r4c48 r6c48
 40)  4.5 r1c8 <> 56   unique rectangle type 1 5/6 r1c78 r7c78
 41)  1.2 r1c7 <= 5 hidden single in b3
 42)  1.2 r2c8 <= 6 hidden single in b3
 43)  1.0 r1c8 <= 8 full house in b3
 44)  1.2 r7c8 <= 5 hidden single in b9
 45)  1.0 r7c7 <= 6 full house in b9
 46)  4.5 r4c4 <> 8    unique rectangle type 4 3/8 r2c46 r4c46
 47)  4.5 r4c6 <> 8    unique rectangle type 4 3/8 r2c46 r4c46

 49        69        1        |46        7         2        |5         8         3       
 5         2         7        |38        1         38       |4         6         9       
 3         46        8        |9         46        5        |1         7         2       
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 79        59        6        |35        28        13       |78        12        4       
 47        1         2        |4568      9         68       |78        3         56       
 8         45        3        |12        46        7        |9         12        56       
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 1         3         9        |28        28        4        |6         5         7       
 2         7         4        |16        5         16       |3         9         8       
 6         8         5        |7         3         9        |2         4         1       
bug grid type 1 r5c4 45
 49        69        1        |46        7         2        |5         8         3       
 5         2         7        |38        1         38       |4         6         9       
 3         46        8        |9         46        5        |1         7         2       
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 79        59        6        |35        28        13       |78        12        4       
 47        1         2        |45+68     9         68       |78        3         56       
 8         45        3        |12        46        7        |9         12        56       
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 1         3         9        |28        28        4        |6         5         7       
 2         7         4        |16        5         16       |3         9         8       
 6         8         5        |7         3         9        |2         4         1       

 48)  5.6 r5c4 <> 45   bug type 1 r5c4.<45+68>
 49)  1.2 r6c5 <= 4 hidden single in b5
 50)  1.2 r1c4 <= 4 hidden single in b2
 51)  1.2 r3c2 <= 4 hidden single in b1
 52)  1.0 r3c5 <= 6 full house in r3
 53)  1.2 r1c2 <= 6 hidden single in b1
 54)  1.0 r1c1 <= 9 full house in r1
 55)  1.2 r5c1 <= 4 hidden single in b4
 56)  1.0 r4c1 <= 7 full house in c1
 57)  1.2 r4c2 <= 9 hidden single in b4
 58)  1.0 r6c2 <= 5 full house in c2
 59)  1.2 r4c4 <= 5 hidden single in b5
 60)  1.2 r4c6 <= 3 hidden single in b5
 61)  1.2 r2c4 <= 3 hidden single in b2
 62)  1.0 r2c6 <= 8 full house in r2
 63)  1.2 r6c4 <= 1 hidden single in b5
 64)  1.2 r4c5 <= 2 hidden single in b5
 65)  1.0 r7c5 <= 8 full house in c5
 66)  1.0 r7c4 <= 2 full house in r7
 67)  1.2 r5c4 <= 8 hidden single in b5
 68)  1.0 r8c4 <= 6 full house in c4
 69)  1.0 r5c6 <= 6 full house in b5
 70)  1.0 r8c6 <= 1 full house in c6
 71)  1.2 r4c8 <= 1 hidden single in b6
 72)  1.0 r4c7 <= 8 full house in r4
 73)  1.0 r5c7 <= 7 full house in c7
 74)  1.0 r5c9 <= 5 full house in r5
 75)  1.0 r6c8 <= 2 full house in c8
 76)  1.0 r6c9 <= 6 full house in r6
001002003020010400300900070006000004010090030800000900030004007004050090600700200;5.6/1.2/1.2


Step 48 in my solution path is the key to what is different. At the same point in the SE solution, there is no possible BUG type 1 due to prior processing of different URs at steps 38-39 in my solution log. You'll have to single-step in SE to see how closely we match until that point. Plus, hit the "get all hints" both for the UR steps and for the BUG steps to see how picking a different UR can lead to a different BUG.

This is what I have called in prior posts a problem with presentation order. Given multiple solution paths, what algorithm can we devise that always detects the lowest scoring one? The best I can devise is one that I've included in another scoring engine that I worked on based on nrczt chains. It works like the following:

You need to have a set of techniques that are applied in ascending score order:

1) Start a scoring cycle with the lowest scoring technique.
2) If the current selected technique is successful (produces an assignment/elimination), set max_score to the techniques score and continue with that technique as long as it does not advance/promote the score again (batch processing).
3) When step 2 terminates, drop back to the lowest level - goto step 1.
4) If step 2 is unsucessful, advance to the next higher scoring technique - goto step 2.
5) If there are no higher techniques to use at step 4, then the puzzle is unsolvable by the available set of techniques.

This corresponds to my SE emulators -E0 exiting strategy and it allows techniques to run unconstrained (batch processing) if they produce scores that are <= the current max_score. This ensures that all possible assignments/eliminations are processed at every step that increases a score, so the score should advance in the slowest possible fashion. It's not the "shortest" solution path since you're overshooting by a large margin, but I'm hypothesizing that it should include the shortest possible solution path within the constraints of the applied techniques. Can this be proved or disproved by some means???

Cheers,
Paul

[PIsaacson]

Here's a test using my own code against itself with and without the -E0 option. Without it, it attempts to emulate SE by selecting just one (the first encountered in my code) assignment/elimination and then always dropping to the lowest level technique, vs with the -E0 exiting strategy of staying within a technique to completion as long as it doesn't advance the score (again).

Code: Select all

$ r 515
sudoku -b -f '%g %n %.2r %.2d %.2p %.2e' < ../bernhard/royle17.txt > c:/temp/log1

Alpha (x86_64-w64-mingw32-g++) Sudoku Explainer C++ engine ver 1.0
C:\msys\home\Paul\se_cpp\sudoku.exe -b -f %g %n %.2r %.2d %.2p %.2e
36628 out of 36628 solved leaving 0 unsolved using 43 queues size 34x244 depth 4/32 avg givens 17.00 avg scores 2.54
total cpu time =       47059.6722 milliseconds
  solving rate =         778.3310 puzzles/second
                           1.2848 msecs/puzzle

          full_house updates/calls 688184/2440245      28.20% eff     326.7434 msec tot       0.0001 msec/call       0.0005 msec/update
   hidden_single_box updates/calls 1361927/1752061     77.73% eff     469.1100 msec tot       0.0003 msec/call       0.0003 msec/update
       hidden_single updates/calls 247511/390134       63.44% eff     122.1341 msec tot       0.0003 msec/call       0.0005 msec/update
     direct_pointing updates/calls 10454/142623         7.33% eff     180.1443 msec tot       0.0013 msec/call       0.0172 msec/update
     direct_claiming updates/calls 0/132169             0.00% eff     191.3084 msec tot       0.0014 msec/call       1.#INF msec/update
  direct_hidden_pair updates/calls 33331/132169        25.22% eff     761.5770 msec tot       0.0058 msec/call       0.0228 msec/update
        naked_single updates/calls 2145/98944           2.17% eff      44.0527 msec tot       0.0004 msec/call       0.0205 msec/update
direct_hidden_triple updates/calls 640/96799            0.66% eff     598.0364 msec tot       0.0062 msec/call       0.9344 msec/update
     locked_cands_t1 updates/calls 68923/96160         71.68% eff      52.7650 msec tot       0.0005 msec/call       0.0008 msec/update
     locked_cands_t2 updates/calls 7094/27237          26.05% eff      36.6793 msec tot       0.0013 msec/call       0.0052 msec/update
          naked_pair updates/calls 13035/20143         64.71% eff      63.0854 msec tot       0.0031 msec/call       0.0048 msec/update
              x_wing updates/calls 1178/16435           7.17% eff      26.6931 msec tot       0.0016 msec/call       0.0227 msec/update
         hidden_pair updates/calls 11051/15974         69.18% eff      31.2379 msec tot       0.0020 msec/call       0.0028 msec/update
        naked_triple updates/calls 1005/13519           7.43% eff      64.3352 msec tot       0.0048 msec/call       0.0640 msec/update
           swordfish updates/calls 857/13288            6.45% eff      28.7470 msec tot       0.0022 msec/call       0.0335 msec/update
       hidden_triple updates/calls 513/13028            3.94% eff      34.2322 msec tot       0.0026 msec/call       0.0667 msec/update
             xy_wing updates/calls 2820/12936          21.80% eff      76.4226 msec tot       0.0059 msec/call       0.0271 msec/update
            xyz_wing updates/calls 765/10807            7.08% eff      37.9434 msec tot       0.0035 msec/call       0.0496 msec/update
           ur_type_1 updates/calls 1120/10099          11.09% eff      27.3352 msec tot       0.0027 msec/call       0.0244 msec/update
           ur_type_2 updates/calls 127/9539             1.33% eff       1.5358 msec tot       0.0002 msec/call       0.0121 msec/update
           ur_type_4 updates/calls 1260/9412           13.39% eff       3.1712 msec tot       0.0003 msec/call       0.0025 msec/update
           ur_type_3 updates/calls 161/8782             1.83% eff      15.2448 msec tot       0.0017 msec/call       0.0947 msec/update
      ur_loop_type_1 updates/calls 72/51945             0.14% eff    1108.3449 msec tot       0.0213 msec/call      15.3937 msec/update
      ur_loop_type_2 updates/calls 141/51211            0.28% eff    7440.2798 msec tot       0.1453 msec/call      52.7679 msec/update
      ur_loop_type_4 updates/calls 18/51017             0.04% eff    1703.7368 msec tot       0.0334 msec/call      94.6520 msec/update
      ur_loop_type_3 updates/calls 4/50996              0.01% eff    3203.8727 msec tot       0.0628 msec/call     800.9682 msec/update
          naked_quad updates/calls 28/8499              0.33% eff      52.9689 msec tot       0.0062 msec/call       1.8917 msec/update
           jellyfish updates/calls 20/8495              0.24% eff      23.7514 msec tot       0.0028 msec/call       1.1876 msec/update
         hidden_quad updates/calls 0/8485               0.00% eff      25.6728 msec tot       0.0030 msec/call       1.#INF msec/update
          bug_type_1 updates/calls 1156/8485           13.62% eff      86.4347 msec tot       0.0102 msec/call       0.0748 msec/update
          bug_type_2 updates/calls 105/7907             1.33% eff       0.6818 msec tot       0.0001 msec/call       0.0065 msec/update
          bug_type_4 updates/calls 14/7854              0.18% eff       0.4319 msec tot       0.0001 msec/call       0.0309 msec/update
          bug_type_3 updates/calls 1/7847               0.01% eff       0.8511 msec tot       0.0001 msec/call       0.8511 msec/update
        aligned_pair updates/calls 46/7846              0.59% eff    1742.3408 msec tot       0.2221 msec/call      37.8770 msec/update
             x_cycle updates/calls 6520/30531          21.36% eff    6168.0525 msec tot       0.2020 msec/call       0.9460 msec/update
             y_cycle updates/calls 2269/19844          11.43% eff    2463.8309 msec tot       0.1242 msec/call       1.0859 msec/update
            xy_cycle updates/calls 2614/7510           34.81% eff    2547.4606 msec tot       0.3392 msec/call       0.9745 msec/update
      aligned_triple updates/calls 65/396              16.41% eff    2448.4478 msec tot       6.1829 msec/call      37.6684 msec/update
              nishio updates/calls 189/1301            14.53% eff    6769.4024 msec tot       5.2032 msec/call      35.8169 msec/update
       forcing_chain updates/calls 142/507             28.01% eff    7152.1911 msec tot      14.1069 msec/call      50.3675 msec/update


Paul@pgisaacs2 ~/se_cpp
$ r 516
sudoku -b -f '%g %n %.2r %.2d %.2p %.2e' < ../bernhard/royle17.txt > c:/temp/log2 -e0

Alpha (x86_64-w64-mingw32-g++) Sudoku Explainer C++ engine ver 1.0
C:\msys\home\Paul\se_cpp\sudoku.exe -b -f %g %n %.2r %.2d %.2p %.2e -e0
36628 out of 36628 solved leaving 0 unsolved using 134 queues size 34x244 depth 4/32 avg givens 17.00 avg scores 2.54
total cpu time =       32185.0167 milliseconds
  solving rate =        1138.0451 puzzles/second
                           0.8787 msecs/puzzle

          full_house updates/calls 368890/778147       47.41% eff     148.2024 msec tot       0.0002 msec/call       0.0004 msec/update
   hidden_single_box updates/calls 1267676/596541     212.50% eff     387.9609 msec tot       0.0007 msec/call       0.0003 msec/update
       hidden_single updates/calls 651611/194712      334.65% eff     219.1048 msec tot       0.0011 msec/call       0.0003 msec/update
     direct_pointing updates/calls 10959/67504         16.23% eff     106.0732 msec tot       0.0016 msec/call       0.0097 msec/update
     direct_claiming updates/calls 0/59187              0.00% eff      98.7578 msec tot       0.0017 msec/call       1.#INF msec/update
  direct_hidden_pair updates/calls 42339/59187         71.53% eff     479.3865 msec tot       0.0081 msec/call       0.0113 msec/update
        naked_single updates/calls 2122/36277           5.85% eff      19.0895 msec tot       0.0005 msec/call       0.0090 msec/update
direct_hidden_triple updates/calls 595/34613            1.72% eff     274.5712 msec tot       0.0079 msec/call       0.4615 msec/update
     locked_cands_t1 updates/calls 120221/34115       352.40% eff      41.9099 msec tot       0.0012 msec/call       0.0003 msec/update
     locked_cands_t2 updates/calls 8030/18571          43.24% eff      29.7531 msec tot       0.0016 msec/call       0.0037 msec/update
          naked_pair updates/calls 13431/16229         82.76% eff      57.4845 msec tot       0.0035 msec/call       0.0043 msec/update
              x_wing updates/calls 1098/13417           8.18% eff      22.8532 msec tot       0.0017 msec/call       0.0208 msec/update
         hidden_pair updates/calls 12054/13033         92.49% eff      26.4465 msec tot       0.0020 msec/call       0.0022 msec/update
        naked_triple updates/calls 1007/11111           9.06% eff      52.8661 msec tot       0.0048 msec/call       0.0525 msec/update
           swordfish updates/calls 836/10896            7.67% eff      23.0929 msec tot       0.0021 msec/call       0.0276 msec/update
       hidden_triple updates/calls 502/10691            4.70% eff      27.6274 msec tot       0.0026 msec/call       0.0550 msec/update
             xy_wing updates/calls 3314/10610          31.23% eff      68.9044 msec tot       0.0065 msec/call       0.0208 msec/update
            xyz_wing updates/calls 715/8842             8.09% eff      30.8249 msec tot       0.0035 msec/call       0.0431 msec/update
           ur_type_1 updates/calls 1134/8219           13.80% eff      22.5490 msec tot       0.0027 msec/call       0.0199 msec/update
           ur_type_2 updates/calls 233/7681             3.03% eff       1.1769 msec tot       0.0002 msec/call       0.0051 msec/update
           ur_type_4 updates/calls 1242/7583           16.38% eff       2.7156 msec tot       0.0004 msec/call       0.0022 msec/update
           ur_type_3 updates/calls 149/7008             2.13% eff      12.3140 msec tot       0.0018 msec/call       0.0826 msec/update
      ur_loop_type_1 updates/calls 72/41349             0.17% eff     847.6414 msec tot       0.0205 msec/call      11.7728 msec/update
      ur_loop_type_2 updates/calls 200/40710            0.49% eff    6743.2003 msec tot       0.1656 msec/call      33.7160 msec/update
      ur_loop_type_4 updates/calls 18/40535             0.04% eff    1346.9142 msec tot       0.0332 msec/call      74.8286 msec/update
      ur_loop_type_3 updates/calls 4/40514              0.01% eff    2511.9899 msec tot       0.0620 msec/call     627.9975 msec/update
          naked_quad updates/calls 28/6752              0.41% eff      40.8374 msec tot       0.0060 msec/call       1.4585 msec/update
           jellyfish updates/calls 17/6748              0.25% eff      18.7291 msec tot       0.0028 msec/call       1.1017 msec/update
         hidden_quad updates/calls 0/6738               0.00% eff      19.8968 msec tot       0.0030 msec/call       1.#INF msec/update
          bug_type_1 updates/calls 1054/6738           15.64% eff      65.5146 msec tot       0.0097 msec/call       0.0622 msec/update
          bug_type_2 updates/calls 87/6211              1.40% eff       0.5800 msec tot       0.0001 msec/call       0.0067 msec/update
          bug_type_4 updates/calls 14/6165              0.23% eff       0.3458 msec tot       0.0001 msec/call       0.0247 msec/update
          bug_type_3 updates/calls 1/6158               0.02% eff       0.7176 msec tot       0.0001 msec/call       0.7176 msec/update
        aligned_pair updates/calls 48/6157              0.78% eff    1284.1878 msec tot       0.2086 msec/call      26.7539 msec/update
             x_cycle updates/calls 11712/22226         52.70% eff    4563.8155 msec tot       0.2053 msec/call       0.3897 msec/update
             y_cycle updates/calls 3102/13390          23.17% eff    1778.6925 msec tot       0.1328 msec/call       0.5734 msec/update
            xy_cycle updates/calls 4334/4803           90.24% eff    1890.5640 msec tot       0.3936 msec/call       0.4362 msec/update
      aligned_triple updates/calls 72/246              29.27% eff    1341.1280 msec tot       5.4517 msec/call      18.6268 msec/update
              nishio updates/calls 1506/711           211.81% eff    3413.9044 msec tot       4.8016 msec/call       2.2669 msec/update
       forcing_chain updates/calls 4218/240          1757.50% eff    3393.2936 msec tot      14.1387 msec/call       0.8045 msec/update


$ compare c:/temp/log1 c:/temp/log2 - SE score on the right, -E0 score on the left
 
700100000000700300000008400200000050000030600100000000060000010030040000000500070 34433  6.60  6.50
Run time 1) 46.30 2) 31.47

Paul@pgisaacs2 ~/se_cpp
$ compare c:/temp/log2 c:/temp/log1 - SE score on the left, -E0 score on the right

000000031028000000000000000000208400730000060000500000160070000000400200300000000 201  8.20  8.10
000000107090020000000000004000401500020003060000700000000090030400800000100000000 846  7.20  7.10
000000301400700000000000200020080000000030060500000040001406000030000100000500000 1061  7.20  7.10
000020019800600000500000000090040000600000300000001000010000040700300000000500800 2995  7.10  7.00
000020070080000500010000000000108000700000020000500000200460003300000400000000100 3066  7.20  7.10
000020800500000004010000000208040000000300100000000070000700030600100000400000002 3219  6.60  6.50
000051000030000900000000000020300046700040010000900000105000000000800200004000000 4656  7.20  7.10
000060020500000100000300000062000008000100700040000000700901000300000040000000006 4846  7.10  7.00
000071000030000900000000000020300075600040010000900000104000000000800200007000000 5526  7.20  7.10
000100070900000040000200000020500100700030000400000600010000500800006000000040000 6412  6.80  6.70
000207004030500000600000900150040000020000070000000300800060000000700050000000000 7413  7.20  7.10
000300402000000100800000000900006050000042000000100000000530080001070000020000000 7857  6.80  6.70
000300604870000000000010000000002750400600000300000000010000270000000080000400000 7918  6.80  6.70
000304100800500060900000000030200400000080020010000000600090000070000300000000000 8062  7.30  7.20
000350200901000000000000000250060000000040007000000010000709040030000800000100000 8246  7.10  7.00
000500208640100000000000400028040000000300050000000000500000010000020700300000000 9214  6.60  6.50
000700100620000000003000050700000009000080030100400000000150000400000700000030000 10705  6.80  6.70
000870500300000020600000000070010800400003000000000000080504000000600030000000001 11663  8.40  8.30
002000090300004000000070500800200000040000030000100000050000704000080600000300000 12307  6.80  6.70
003100060080500000000000000007060200200000001000400500000082030040000000500000000 12600  7.20  7.10
010007000500000002000000000047000010000250300000600000000000840000380000205000000 14157  7.20  7.10
010050000000000304000000000900300700000409800000000020403600000000020010000000005 14235  7.20  7.10
010060075008400000000000000750000010000200400000000000402000800000071000300000000 14296  6.60  6.50
013000700000520400080000000000010080900000600200000000050400000700600000000000010 14775  7.20  7.10
030600000000030070200000040006040000000002300080000600700500100400800000000000000 16820  6.60  6.50
036000000020000050000100000700000104000083000000000700000520030104000000000006000 17185  6.80  6.70
048030000000500012000000000000640300500000700100000000000102050030000400000000000 18307  7.10  7.00
050000016400030000000000000067000080201000000000040300000706000500000200000100000 18381  7.20  7.10
050000061400030000000000000067000080201000000000040300000706000500000200000100000 18421  7.20  7.10
050000200600010000000800000070900000000000031000000460000500702300060000100000000 18485  6.80  6.70
050001000060000070000000200100030000200000009000400060000650004800000100000700000 18600  7.20  7.10
051000000000090007000000000400200008000105000030000000300040500700000060000000210 19153  7.10  7.00
060000021000003060000070000304000800000100000700000000010200005000040300600000000 19488  7.20  7.10
060702000000000031000000000500010040080000600000200000000600200300070000104000000 20227  6.60  6.50
060850000400000001000000000000700860100000000000200000032000050000014700000090000 20278  7.20  7.10
061000050000300800040000000506000200000041000000700000300082000000000061000000000 20349  6.80  6.70
070000016400030000000000000068000090201000000000040300000806000500000200000100000 20647  7.20  7.10
070000061400030000000000000068000090201000000000040300000806000500000200000100000 20701  7.20  7.10
070104000600000070000800000702060000000000801000000000010500400000030060200000000 21083  6.60  6.50
070650000400000001000000000000500730100000000000200000032000070000014800000090000 21305  7.20  7.10
080750000400000001000000000000600830100000000000200000032000080000014600000090000 22301  7.20  7.10
100705000000000604000000800705100000000080300200000000000200070060040000030000000 24190  7.30  7.20
200000006000700300000001000500020040070300800000000000037600000000040025000000000 24912  6.60  6.50
200400500000080030000000000000020400100600000000000080038001000000500702090000000 25842  7.20  7.10
209000060000301000000000000000400107600020000800000300030700400000060050000000000 26420  6.80  6.70
300000060000008200007500000000070030200000500040002000080000401000060000000300000 26890  7.60  7.50
300000700000100400000200000000050610082000000000006000010000028700030000000000030 27097  7.10  7.00
300070100080000040000005000700000005000800020001000000620400003000200000000000700 27353  4.70  4.60
320000000000100900000600000080027000000030700000000100005000026100400000000000080 28021  7.30  7.20
450080700100000000000200000003060002700804000000000000062300000000000410000000000 29719  7.20  7.10
500000001030600000000000000040300670070010000000008000102000060000400200800000000 29849  6.80  6.70
500000301040200000000000000020006040000030500800000000000407020300050000001000000 30077  7.80  7.70
600000038000504000000000010030080000000002700010000000507200400000030000200000000 31967  7.20  7.10
600000205000701000000000000000500016040020000000000030000240800107000000300000000 32072  7.20  7.10
600300070000000010040000000050000800000710000100600000000005402003000500700000000 32815  6.80  6.70
700408600000000001300000000050021000400000070000000000002350000000700400010000000 34611  6.60  6.50
700603000800000920000400000040000006900010000000080000000000710060200000000000800 34723  7.20  7.10
790000200000000100000400000005600043200000000000300000034000080100027000000000000 35350  7.20  7.10
800000039000605000000000010030090000000002700010000000706200500000030000400000000 35447  7.20  7.10
Run time 1) 31.47 2) 46.30

Paul@pgisaacs2 ~/se_cpp
$$

If you just look at the statistic for "forcing_chain" you'll see the difference with the first from the SE type of exiting and the second from the -E0 exiting strategy plus it ran considerably faster: 1138 puzzles/second vs 778 puzzles/second.

Comparing the output log ratings, there is one lower scoring solutions from the 1st (SE like) log as opposed to the 2nd log. Conversely, the -E0 log contains 60 puzzles that scored lower by at least 0.1 points. The fact that there is a single puzzle in the first comparison somewhat blows my theory out of the water tha the -E0 exiting strategy always contains the shortest (and lowest??) scoring solution path. I need to look at lots of debug info to see exactly what happened there - hopefully it's a simple bug somewhere.

Cheers,
Paul

[lksudoku]

This corresponds to my SE emulators -E0 exiting strategy and it allows techniques to run unconstrained (batch processing)

What you call your SE emulator, does not perform batch mode correctly, it applies every move once found, so if you have two URs and one destroys the other, the order in which they are found will effect the rating

To have batch mode, you need to apply the move only after all moves are found

[PIsaacson]

...To have batch mode, you need to apply the move only after all moves are found

Or you can operate on a structure that contains the necessary static information and update the grid object knowing that the static structure presents each pattern as if it were the first one found. That pretty much explains why I have so many init functions in the various techniques, especially for chains which operate entirely from an adjacency matrix.

Cheers,
Paul

[David P Bird]

RW is right Avoidable Pattern eliminations are not THAT much more difficult than the Deadly Patterns they are based on – particularly when solving manually when the givens are always obvious. Your problem with the implementation order of UR deductions would then vanish.

Paul, from my manual solving experiences when trying to shorten my solutions:

Having found the step with the hardest rating (the backbreaker) analyse the previous eliminations required to enable that step. Now re-run the solution implementing only these critical path steps to advance the backbreaker as far forward in the solution path as possible. Now it's usual that that each deduction previously made will provide more eliminations than it did before and some steps will be unnecessary.

As this is done run all the lower scoring methods to see which ones eliminate the most candidates at any point and try to implement those first. This will usually take some trial and error as some rather minor preliminary eliminations may be needed to enable a killer closed loop or SdC pattern, which might not have been employed before.

Rank the utility value of minor eliminations according to the new strong links they create and favour any that will connect different sub-nets.

Another tactic is to advance the eliminations needed to resolve key stacks and tiers or possibly a key digit.