The New Sudoku Players' Forum

[Red Ed]

((Reposted later in the hope that it attract a reply.))

[StrmCkr]

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.

daj95376

but the overhead of keeping that ideal in motion across every implemented solving technique explodes exponentially in relation to time.
this is the issue i've noticed in my batch mode solver that applies every possible elimination for a given technique before it moves to the next (how ever it finds all the valid moves with zero eliminations).

however when rating a puzzle perhaps this is worth mentioning again if considering the above approach.
Rating theory

[daj95376]

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.

but the overhead of keeping that ideal in motion across every implemented solving technique explodes exponentially in relation to time.
this is the issue i've noticed in my batch mode solver that applies every possible elimination for a given technique before it moves to the next (how ever it finds all the valid moves with zero eliminations).

There appears to be a miscommunication here. I was not discussing "every implemented solving technique" ... only those with a 2.0 rating. And, my premise was that all of the eliminations had already been found for that rating ... as in the list ronk mentioned.

Bottom Line: I don't know what SE is doing internally ... and it doesn't sound like anyone else has a much better understanding. If your goal is to exactly match the current SE ratings,that pretty much leaves hoping that a C/C++ clone of SE will run significantly faster than the Java version. Otherwise, someone needs to start suggesting specifics for an alternate goal.

Personally, I'd suggest discarding any thought of resurrecting a faster version of SE and proceed straight to defining a hierarchy of techniques that are well-defined on a new rating scale. Then, everyone can try to implement a version of their own solver that match this hierarchy -- which is what I suspect many are hoping to do anyway!

[ronk]

There appears to be a miscommunication here. I was not discussing "every implemented solving technique" ... only those with a 2.0 rating. And, my premise was that all of the eliminations had already been found for that rating ... as in the list ronk mentioned.

There is no list when solving (a batch of) puzzles using the command-line and there is no list when single-stepping through a single puzzle using the GUI. Only one move is executed, so what would be the point in making a list of moves?

A list is produced only by clicking "Get All Hints" before applying a move. For one thing, this allows the user to alter the solution path from Explainer's normal path.

[lksudoku]

what would be the point in making a list of moves

A list of moves can be usefull for several reasons:

- parallelism of different calculations
- efficiency, sometimes computing all the moves at once takes less time then computing them one after the other, or does not add a significant time, hence you may get additional info for little cost

and I am sure that there are other advantages

[ronk]

what would be the point in making a list of moves

A list of moves can be usefull for several reasons:

- parallelism of different calculations
- efficiency, sometimes computing all the moves at once takes less time then computing them one after the other, or does not add a significant time, hence you may get additional info for little cost

You apparently neglected to consider the premise to my statement.

[StrmCkr]

There appears to be a miscommunication here. I was not discussing "every implemented solving technique" ... only those with a 2.0 rating. And, my premise was that all of the eliminations had already been found for that rating ... as in the list ronk mentioned.

i think you might have miss read my intentions.

i was meaning that when the same principle of find all moves of a specific type is used completely through out the development of each technique type
at each step of solving your length of time to find all those moves greatly increases. {making the solver a batch mode over singular search functions}

Code: Select all

Personally, I'd suggest discarding any thought of resurrecting a faster version of SE and proceed straight to defining a hierarchy of techniques that are well-defined on a new rating scale. Then, everyone can try to implement a version of their own solver that match this hierarchy -- which is what I suspect many are hoping to do anyway!

i agree, hence my link to an post on my thoughts on what a rating program should be able to do...

[Pat]

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>




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

sorry but what you call a "Direct Hidden Pair"

28) r3c6 <= 4 direct hidden pair b3x89.<36>

is not a Direct Hidden Pair as defined by Nicolas Juillerat
-- you're going from one house (b3) to a different house (r3)

Direct Hidden Pair

Direct Hidden Pair is a special case of the more general Hidden Pair technique -- the Hidden Pair immediately reveals a Hidden Single in the same region.

[ronk]

what you call a "Direct Hidden Pair"

28) r3c6 <= 4 direct hidden pair b3x89.<36>

is not a Direct Hidden Pair as defined by Nicolas Juillerat

Agreed, but how did you get past the earlier step ...

24) r8c3 <= 6 direct hidden pair r9c13.<27>

... when there is pair <36> in both r8c2 and r8c3?

[PIsaacson]

Pat,

The b3x89 notation defines exactly the same cells as r3c89. I use the b.x. notation when I find something that is aligned in 2 sectors with the b representing the box number while the x represents the offset within the box starting at top left = 1 to bottom right = 9. I maintain that the elimination at r3c6 does indeed qualify since it shares the same row. I guess I should have altered the notation to indicate the pair using a "matching" notation.

Cheers,
Paul

[Pat]

The b3x89 notation defines exactly the same cells as r3c89.

I maintain that the elimination at r3c6 does indeed qualify since it shares the same row.

the cells are indeed r3c89
but your "hidden" duo {3,6}
exists only in b3
( and not in r3 )

[Pat]

what you call a "Direct Hidden Pair"

28) r3c6 <= 4 direct hidden pair b3x89.<36>

is not a Direct Hidden Pair as defined by Nicolas Juillerat

Agreed, but how did you get past the earlier step ...

24) r8c3 <= 6 direct hidden pair r9c13.<27>

... when there is pair <36> in both r8c2 and r8c3?

sure, that too is not a Direct Hidden Pair
( the "hidden" duo is in r9 or in b7,
the resulting "hidden single" is in a different house -- c3 )

i was only trying to give one example
so i happened to skip the first available example

well not just happened --
my example was chosen because that's the one which pushes the rating above 2.0
( whereas step #24 can be bypassed )

[PIsaacson]

[the cells are indeed r3c89 but your "hidden" duo {3,6} exists only in b3 ( and not in r3 )

The impact of the hidden duo in b3 reduces the 4's in r3 and allows for the direct assignment r3c6 <= 4. It truly is a direct hidden pair in b3x89, and I stand corrected about altering the notation, but the impact indeed extends beyond just box 3. It's possible for the eliminations to impact b3, r3, c8 and c9, all of which I currently check. I interpreted "region" to mean any impacted area instead of just the containing sector.

At this point, I'm no longer trying to exactly match SE since I've hit so many other areas where SE simply skips potential assignments and eliminations within various techniques. I just used direct hidden pairs as an example as it gets worse with some of the more advanced logic.

Cheers,
Paul

[Red Ed]

Anyway, ignoring why/how SE operates as it does, no one has commented on the profiling output.

That profiling job was run on what input? Lots of middling-difficulty puzzles? One hardish puzzle? If you ran the profiling job on everything ever posted in the patterns game then would you get the same percentages or would you expect chains to dominate by virtue of the existence of ER 10+ puzzles?

[PIsaacson]

Ed,

The profiling was run against the top50000 collection. It looked like it would take many days to run the complete profile, so I only posted the top 20 offending procedures using a snapshot after about 8 hours (ref getHints count which is called at the end of each puzzle). I've run the same thing against tarek's pearly6000 which contains many > 11.0 ratings, and the top 10 profiling offenders after letting it run for over 24 hours are nearly identical, but with differences in the self-time percentages. It looks like the very lowest level routines are called so often that they greatly influence the results. One possible quick 10% fix would be to skip getHints if SE is batch processing since you probably don't need any hints. I think this is residue from the F9 score and show all techniques used.

Cheers,
Paul