The New Sudoku Players' Forum

[PIsaacson]

Upon closer examination of SE and after trying to emulate it with a C++ framework of techniques that I already had plus modifying some to emulate things like "direct hidden ...", it became obvious that unless I could exactly duplicate the SE anomalies and bugs the scores would never match. Take the following as an example:

Code: Select all

000000019300600000000000000600080500040000300000010000480000070000200400010900000

 2578      2567      245678   |34578     23457     234578   |2678      1         9
 3         2579      1245789  |6         24579     1245789  |278       2458      24578
 125789    25679     12456789 |134578    234579    12345789 |2678      234568    2345678
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 6         2379      12379    |347       8         23479    |5         249       1247
 125789    4         125789   |57        25679     25679    |3         2689      12678
 25789     23579     235789   |3457      1         2345679  |26789     24689     24678
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 4         8         23569    |135       356       1356     |1269      7         12356
 579       35679     35679    |2         3567      135678   |4         35689     13568
 257       1         23567    |9         34567     345678   |268       23568     23568

  1) r7c7 <= 1 hidden single in c7
  2) r8c6 <= 1 hidden single in b8
  3) r3c4 <= 1 hidden single in b2
  4) r2c3 <= 1 hidden single in b1
  5) r5c1 <= 1 hidden single in b4
  6) r4c9 <= 1 hidden single in b6
  7) r9c6 <= 8 hidden single in b8
  8) r1c4 <= 8 hidden single in b2
  9) r9c5 <= 4 hidden single in b8
 10) r8c5 <= 7 hidden single in b8
 11) r8c8 <= 9 hidden single in b9
 12) r6c7 <= 9 hidden single in b6
 13) r7c3 <= 9 hidden single in b7
 14) r4c2 <= 9 hidden single in b4
 15) r3c1 <= 9 hidden single in b1
 16) r3c3 <= 8 hidden single in b1
 17) r1c3 <= 4 hidden single in b1
 18) r6c1 <= 8 hidden single in b4
 19) r8c9 <= 8 hidden single in b9
 20) r5c8 <= 8 hidden single in b6
 21) r2c7 <= 8 hidden single in b3
 22) r7c9 <= 2 hidden single in r7
 23) r8c1 <= 5    direct hidden pair r8c23.<36>
 24) r8c3 <= 6    direct hidden pair r9c13.<27>
 25) r8c2 <= 3 full house in r8
 26) r9c7 <= 6    direct hidden pair r9c89.<35>
 27) r1c2 <= 6 hidden single in r1
 28) r3c6 <= 4    direct hidden pair b3x89.<36>
 29) r2c6 <= 7    direct hidden pair r1c56.<35>
 30) r2c5 <= 9 hidden single in b2
 31) r5c6 <= 9 hidden single in b5
 32) r3c5 <= 2    direct hidden pair r1c56.<35>
 33) r5c3 <= 2 hidden single in r5
 34) r9c1 <= 2 hidden single in b7
 35) r1c1 <= 7 full house in c1
 36) r9c3 <= 7 full house in b7
 37) r2c2 <= 2 hidden single in b1
 38) r3c2 <= 5 full house in b1
 39) r6c2 <= 7 full house in c2
 40) r1c7 <= 2 hidden single in b3
 41) r3c7 <= 7 full house in c7
 42) r6c3 <= 5 hidden single in b4
 43) r4c3 <= 3 full house in c3
 44) r5c9 <= 7 hidden single in b6
 45) r4c4 <= 7 hidden single in b5
 46) r6c4 <= 4 hidden single in b5
 47) r6c6 <= 3 hidden single in b5
 48) r1c5 <= 3 hidden single in b2
 49) r1c6 <= 5 full house in r1
 50) r4c6 <= 2 hidden single in b5
 51) r4c8 <= 4 full house in r4
 52) r7c6 <= 6 full house in c6
 53) r2c9 <= 4 hidden single in b3
 54) r2c8 <= 5 full house in r2
 55) r5c5 <= 6 hidden single in b5
 56) r5c4 <= 5 full house in r5
 57) r7c4 <= 3 full house in c4
 58) r7c5 <= 5 full house in c5
 59) r6c8 <= 2 hidden single in b6
 60) r6c9 <= 6 full house in r6
 61) r3c8 <= 6 hidden single in b3
 62) r3c9 <= 3 full house in r3
 63) r9c8 <= 3 full house in c8
 64) r9c9 <= 5 full house in r9
764835219321697854958124763693782541142569387875413926489356172536271498217948635 puzzle 1 givens 17 score 2.0          0.1156 ms
Alpha (x86_64-w64-mingw32-g++) Sudoku Explainer C++ engine ver 1.0 C:\msys\home\Paul\scorer\sudoku.exe -bv -E1
1 out of 1 solved leaving 0 unsolved using 0 queues size 0 17.00 avg givens 2.00 avg scores
total cpu time =           0.2379 milliseconds
  solving rate =        4204.2807 puzzles/second
                           0.2379 msecs/puzzle

          full_house updates/calls 18/64               28.13% eff       0.0226 msec tot       0.0004 msec/call       0.0013 msec/update
   hidden_single_box updates/calls 36/46               78.26% eff       0.0354 msec tot       0.0008 msec/call       0.0010 msec/update
       hidden_single updates/calls 4/10                40.00% eff       0.0088 msec tot       0.0009 msec/call       0.0022 msec/update
     direct_pointing updates/calls 0/6                  0.00% eff       0.0062 msec tot       0.0010 msec/call       1.#INF msec/update
     direct_claiming updates/calls 0/6                  0.00% eff       0.0102 msec tot       0.0017 msec/call       1.#INF msec/update
  direct_hidden_pair updates/calls 6/6                100.00% eff       0.0244 msec tot       0.0041 msec/call       0.0041 msec/update

Now enter the puzzle into SE and manually advance using F2

Code: Select all

000000019300600000000000000600080500040000300000010000480000070000200400010900000

I agree 100% up to the first direct hidden pair, after which SE somehow misses the 1st available one, finds the second one (in my solution path), skips the others and instead finds a higher (2.6) rated pointing locked pair. The net result is that instead of the lower 2.0 final rating by finding all the available direct hidden pairs, SE over rates this puzzle at 2.6.

So, I've become frustrated with trying to exactly match SE and instead decided to fall back to what my professor of CS 101 said regarding code optimization: "Look for the low hanging fruit!" So, here's the top 20 after profiling the current SE java source code in NetBeans:

Code: Select all

Hot Spots - Method                                        Self time [%]   Self time    Invocations

diuf.sudoku.Grid$Region.getPotentialPositions                  56.53    772589.631 ms    131739038
diuf.sudoku.solver.rules.AlignedExclusion.getHints              9.82    134161.571 ms          453
diuf.sudoku.solver.rules.chaining.Chaining.getOnToOff           4.86     66360.479 ms      6497399
diuf.sudoku.Cell.getHouseCells                                  3.26     44596.633 ms      8657946
diuf.sudoku.solver.rules.chaining.Chaining.getOffToOn           3.01     41145.584 ms     24638899
diuf.sudoku.Cell.hasPotentialValue                              2.96     40485.213 ms   1390827357
diuf.sudoku.Cell.copyTo                                         2.18     29836.832 ms     91877490
diuf.sudoku.solver.rules.chaining.ChainingHint.getChain         1.64     22423.427 ms      3060167
diuf.sudoku.Grid.getRegionAt                                    1.24     16900.163 ms    134328003
diuf.sudoku.solver.rules.chaining.ChainingHint.getAncestorCount 1.13     15495.180 ms      2460304
diuf.sudoku.Grid$Block.getCell                                  1.01     13859.998 ms    552213743
diuf.sudoku.tools.Permutations.nextBitNums                      0.93     12695.616 ms     82641432
diuf.sudoku.solver.rules.chaining.Chaining.doChaining           0.91     12452.146 ms       565297
diuf.sudoku.Grid$Column.getCell                                 0.83     11394.673 ms    549626542
diuf.sudoku.tools.LinkedSet.contains                            0.81     11038.626 ms     68192762
diuf.sudoku.Grid$Row.getCell                                    0.76     10328.371 ms    548850347
diuf.sudoku.Grid.copyTo                                         0.73      9964.736 ms      1134290
diuf.sudoku.solver.rules.chaining.Chaining.doForcingChains      0.61      8321.746 ms       529516
diuf.sudoku.solver.rules.chaining.Potential.hashCode            0.58      7904.065 ms    345755845

So, the biggest "bang for the buck" is to improve GetPotentialCandidates. But, that means changing the Grid and Region objects to implement a better structure for tracking candidate values. In my C++ grid object, I retain the 4 spaces (RC, RN, CN, BN) as 9x9 arrays of integers with each integer containing the 9 bits to fully define each 9x9x9 or 729 bit full view. This incurs some additional overhead during candidate assignments/eliminations, but pays off in spades during all subsequent algorithms for detecting things such as the GetPotentialCandidates. I'm starting to think that if you really want to retain an exact replication of SE scoring, then attacking the low hanging fruit (in addition to running X64 Java if you have a 64 bit OS) is the way to go.

Cheers,
Paul

[champagne]

I agree 100% up to the first direct hidden pair, after which SE somehow misses the 1st available one, finds the second one (in my solution path), skips the others and instead finds a higher (2.6) rated pointing locked pair. The net result is that instead of the lower 2.0 final rating by finding all the available direct hidden pairs, SE over rates this puzzle at 2.6.
Cheers,
Paul

I am doing a similar approach using my own code and got also unexplained (so far) lower rating from my "clone" of SE.

I was suspecting a bug in the "hidden set giving a single", what you established.

One positive point is that the first benchmark I made out of about 46000 puzzles rating in the range 1.2 to 3.8 gave a ratio of 1/8 in run time and an average speed of 320 puzzles per second with my "clone".

Much to early to get any conclusion, but a significant improvement will come at the end.

I am for the time being checking the UR, UL code to meet SE specifications.

Another point is that I am slowly rating my data base of hardest with SE. I already have a nice collection of ratings in the range 10.0 11.9. If anybody is interested in getting a provisionnal sample file, I will publish intermediate results.

champagne

[ronk]

I agree 100% up to the first direct hidden pair, after which SE somehow misses the 1st available one, finds the second one (in my solution path), skips the others and instead finds a higher (2.6) rated pointing locked pair. The net result is that instead of the lower 2.0 final rating by finding all the available direct hidden pairs, SE over rates this puzzle at 2.6.

I disagree that "SE somehow misses the 1st available one." If you uncheck "Filter hints with similar outcome" and click "Get all hints", SE does find your 1st direct hidden pair. It's the 4th "direct hidden pair" listed, but it applies the 1st listed.

SE seems to first search for direct hidden pairs in boxes, then columns, and then rows. What search order did you use? (Obviously, the order of digit pairings has to be considered eventually as well.)

I've become frustrated with trying to exactly match SE ...

You're frustrated at the ER=2.0 level? There isn't much chance of this project succeeding then, is there?

[champagne]

SE seems to first search for direct hidden pairs in boxes, then columns, and then rows. What search order did you use? (Obviously, the order of digit pairings has to be considered eventually as well.

Interesting remark, may be a goo clue to match SE results at 100%.

However, if the program is sensitive at that level to the order rows/columns, then the rating can differ for other morphs of the puzzle at he same level. This should have been seen earlier.

The priority for boxes can be seen differently.

champagne

EDIT : as far as I could see, rating 2.0 is only searched in boxes. My "clone" introduced that limitation.

[BryanL]

I disagree that "SE somehow misses the 1st available one." If you uncheck "Filter hints with similar outcome" and click "Get all hints", SE does find your 1st direct hidden pair. It's the 4th "direct hidden pair" listed, but it applies the 1st listed.

I have been frustrated with the order SE finds hints too. I guess Get all hints may be the partial answer.

SE seems to first search for direct hidden pairs in boxes, then columns, and then rows. What search order did you use? (Obviously, the order of digit pairings has to be considered eventually as well.)

I am pretty sure most would search rows, columns and then boxes. We read left to right, top to bottom. Also boxes take on a bit more programming effort and are naturally left till last to implement.

I've become frustrated with trying to exactly match SE ...

You're frustrated at the ER=2.0 level? There isn't much chance of this project succeeding then, is there?

I smile at your comment but have to disagree. To me the ultimate goal is to create a rating solver that provides consistency and doesn't take 4 hours on a modern day PC to find and rate a puzzle with a lot of chains. If it means ditching SE rating so be it.

Edit: I am pretty sure it has been mentioned before, but would like to stress it - that the rating engine should equally rate from whichever direction it takes to search. After all, a hidden pair is a hidden pair. And just because an option like "get all hints" is checked, shouldn't influence the order it finds or rates the solution path.

[daj95376]

I disagree that "SE somehow misses the 1st available one." If you uncheck "Filter hints with similar outcome" and click "Get all hints", SE does find your 1st direct hidden pair. It's the 4th "direct hidden pair" listed, but it applies the 1st listed.

SE seems to first search for direct hidden pairs in boxes, then columns, and then rows. What search order did you use? (Obviously, the order of digit pairings has to be considered eventually as well.)

As an observer on this project, this reply only complicates matters for me.

If SE lists Paul's direct hidden pairs when "Get all hints" is selected, but doesn't eventually apply them to obtain a final rating of 2.0, then I'd conclude there's a bug in the software. Now, I've seen where two concurrent Unique Rectangles co-exist, and the selection of only one prevents the detection of the other one later, but I can't see this happening when dealing with (essentially) basic steps.

Also, it sounds to me like SE selects only one direct hidden pair at a time from it's list of 2.0 rated steps. This may be fine if you're running the GUI and wish to interactively select which 2.0 step is used; but, if you're only interested in rating a puzzle, then it's more efficient to perform all 2.0 rated steps concurrently if they've already been found. This could put a major wrinkle in resolving the keep/discard the GUI debate.

[champagne]

but, if you're only interested in rating a puzzle, then it's more efficient to perform all 2.0 rated steps concurrently if they've already been found.

I fully agree on that.

If the kind of conjecture telling that the difficulty should not be sensitive to the sequence for equivalent moves is correct, it should work this way and this is what I am doing.

Again, if the difficulty was sensitive to the choice between equivalent moves, then different morphs of the same puzzle would have different ratings.

May-be some trouble could come out of the uniqueness techniques, but SE has been used for years and such problems have not been seen as far as I know.


champagne

[ronk]

but, if you're only interested in rating a puzzle, then it's more efficient to perform all 2.0 rated steps concurrently if they've already been found.

I fully agree on that.

If the kind of conjecture telling that the difficulty should not be sensitive to the sequence for equivalent moves is correct, it should work this way and this is what I am doing.

'Moves with equivalent ratings' is not the same as 'equivalent moves'.

[daj95376]

'Moves with equivalent ratings' is not the same as 'equivalent moves'.

Okay. Now, are there multiple move types with a rating of 2.0? If not, then there are equivalent moves that SE is overlooking! The only other explanation is that, after performing one 2.0 rated (equivalent) move, the subsequent application of a lower valued move prevents an alternately present 2.0 (equivalent) move from being detected the next time SE searches for a 2.0 rated move. This could explain why SE then proceeds to find a 2.6 rated step. It also means that every step, in the exact logical order found by SE, must be duplicated if SE ratings are to be maintained. It could also tie the hands of anyone trying to develop a speedier SE-clone.

[AR4793]

Ok, I'll talk like a project manager again...

It really seems to me that there would be a benefit in having a command line version and a GUI version running with the same engine under the hood.

(1) That way the multitude of folks running just the GUI could help find bugs like the ones that are being discussed.

- Need a place to document the bugs and show that the new version fixes them.

(2) There are also no doubt some folks would would love to find puzzles for which the solver gets stuck, and then try to figure out a new technique.

Both of the above points would also help improve the command line version.

The question is - Is the extra work worth the benefits?

[champagne]

Ok, I'll talk like a project manager again...

It really seems to me that there would be a benefit in having a command line version and a GUI version running with the same engine under the hood.

(1) That way the multitude of folks running just the GUI could help find bugs like the ones that are being discussed.

- Need a place to document the bugs and show that the new version fixes them.

For me, the existing SE GUI version is enough for the use you describe. I don't foresee a change in SE rating rules.

If we want a "C" or "C++" version easy to transfert on any computer, a command line version is much easier to set up. With a GUI version, a common compiling platform has to be agreed upon.

Anyway, for testing purpose, it is necessary to have a "print" option giving a detailled result in the new version.

Logging the anomalies (potential bugs) in a separate thread is a good idea. For the time, I have some suspicions, but nothing as precise as what published Paul. My priority is to cover as much as as possible of the low ratings first.

(2) There are also no doubt some folks would would love to find puzzles for which the solver gets stuck, and then try to figure out a new technique.

I never heard of a valid puzzle not rated by SE. Another question is to know whether we'll find a faster way to work "as SE does" in the range 10.5 12.0.

Including new technics is quite another topic. I guess a newcomer in that fiel would restart form existing optimized code and develop freely it's own process. I am just doing the opposite, using my own code to try to produce a "SE rating clone" program;


champagne

[eleven]

Some words from a player's point of view:

We all know, that ratings also for very easy puzzles can be strange for a manual player. A puzzle, which needs 3 naked triples normally is much harder than one which needs an easy-to-spot x-wing or UR. A player never will go through a puzzle like a program, but he takes what he spots where he is looking at in the moment. He would not distinguish, if he puts in a number, because its a pure hidden single or if a simple box-line is needed also. The only preference where to look for a direct hidden pair may be, what was the last unit, where he filled in the 6th number (no matter if its a box,row or column).

So the ratings below say ER 5 are somewhat irrelevant for a player.

Going up to ER 7.2 the rating only is a rough hint for a player, how hard the puzzle is. We know, that some 7.2 puzzles can be solved easily with an w-wing, but others are very hard (up to being annoying unattractive to solve). Looking at the number of chains, which Explainer needs, is a better hint, but also here the difficulty of 2 puzzles "needing" 6 chains can be very different.
There are other solvers (one being JSudoku), which can give players a better feeling, how hard puzzles are in this range.

So i guess, you should not waste much time in thinking about, if the low ER ratings are good enough (to get better ones is a completely different goal). In fact you probably could bind in the original java code for calculating them, because this is the quick part.

All you need is a good solution for the chaining part (Red Ed already stated that). The rest are peanuts, and if someone likes to make a GUI, he can do it nearly independantly.

For a player the hard ratings (above say 8.5) will be an even rougher measure. At least we know, that it will take a bit longer to solve them And in most cases also the solutions are of little interest.

[PIsaacson]

It is not always the case that SE finds a corresponding hidden direct pair at various stages, even using the "Get All Hints". If it were only that simple... It also misses various lower scoring URs, BUGs... and opts for higher scoring techniques fairly often. Even chains are suspect in that while it uses a BFS like technique that should produce "shortest distance" chains, the computation of the scores seems very imprecise, especially for short chains and very long chains.

Code: Select all

  protected double getLengthDifficulty() {
        double added = 0.0;
        int ceil = 4;
        int length = getComplexity() - 2;
        boolean isOdd = false;
        // my comments - The next while loop calculates the below steps array on the fly,
        // but have you ever seen a 1024 or over step chain??? 
        // There are a maximum of 729 candidates, so how can you have more than all of them involved???
        // That's some serious candidate reuse...
        while (length > ceil) {
            added += 0.1;
            if (!isOdd)
                ceil = (ceil * 3) / 2;
            else
                ceil = (ceil * 4) / 3;
            isOdd = !isOdd;
        }

        /* replaced by on-the-fly while loop processing
        final int[] steps = new int[] {4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128,
            192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192};
        int length = getComplexity() - 2;
        double added = 0;
        int index = 0;
        while (index < steps.length && length > steps[index]) {
            added += 0.1;
            index++;
        }
         */
        return added;

Anyway, ignoring why/how SE operates as it does, no one has commented on the profiling output. That seemed far more interesting to me than speculating on whether or not the lower level scoring is accurate. Again, assuming the goal is just to get a faster running SE, then instead of re-inventing the wheel in C++, why not just attack the Java code and see if we can improve SE sufficiently without any major redesign or reimplementation???

Cheers,
Paul

[ronk]

Anyway, ignoring why/how SE operates as it does, no one has commented on the profiling output. That seemed far more interesting to me than speculating on whether or not the lower level scoring is accurate. Again, assuming the goal is just to get a faster running SE, then instead of re-inventing the wheel in C++, why not just attack the Java code and see if we can improve SE sufficiently without any major redesign or reimplementation???

What was the ER distribution of the puzzles solved during the profiling test? Specifically, were there any puzzles with ER>=9.0 (or thereabouts)?

[lksudoku]

My 2 cents

- I would suggest that instead of a command line project, the project will be to form a software library; that library can be used by a command line program in order to test/operate it
- About the compilation environment, I suggest a cross platform library, so that it can compile on any platform and any standard compiler; in order to achieve that, I suggest compiling/linking in strict mode, using ansi C/C++ standard flags only; OS dependent features (if required) should be wrapped by a common interface for all platforms
- Project files storage, Instead of using some website to store files, I suggest using a Software for configuration management
- While creating a new library, it is possible to make it configurable with a varying rating scheme, so that the SE rating is one possible such scheme, perhaps even the default one, but not the only one; this way including new methods later on will not require major refactoring, and users can customize the rating to their preference
- The order in which a puzzle is traversed may have an effect on a human solver, so it could be part of the rating algorithm
- The interface can include a method to start with a puzzle and set of current candidates, to start searching from higher rating techniques