more on whips, braids, T&E...

Advanced methods and approaches for solving Sudoku puzzles

more on whips, braids, T&E...

Postby denis_berthier » Sun Mar 27, 2011 6:53 am


1) References and definitions
can be found in my book, on my website or in the following threads:
- fully supersymmetric chains http://forum.enjoysudoku.com/fully-supersymmetric-chains-t5591.html
- the concept of a resolution rule http://forum.enjoysudoku.com/the-concept-of-a-resolution-rule-and-its-applications-t5600.html
- abominable T&E and lovely braids http://forum.enjoysudoku.com/abominable-trial-and-error-and-lovely-braids-t6390.html
- rating rules / puzzles http://forum.enjoysudoku.com/rating-rules-puzzles-ordering-the-rules-t5995.html
I don't repeat them here.
Sorry, this is not a self contained post.

2) Brief summary of previous results
As I've stated many times in the past, my approach to chains has been based on successive extensions to the well known xy-chains (BTW, does anyone know who introduced xy-chains?).
It is important to remind this at the start, because xy-chains are a very simple pattern and all the elimination theorems for the more complex chains I've introduced can be proved in a very straightforward way as simple extensions of the proof for the xy-case. Actually, I devised these extensions while I was trying to prove the xy-chain case for myself. These extensions can be described as follows:
- allow additional z- and t- candidates, i.e. replace (in the xy-chains) the bivalue condition by "bivalue modulo the target and/or the previous right-linking candidates";
- introduce the 3D (or fully supersymmetric) version of xy-chains: nrc-chains (equivalent to the basic AICs, with no hinges and no subsets) ; extend these in the same way as above; replace (in the nrc-chains) the bivalue/bilocal condition by "bivalue/bilocal modulo the target and/or the previous right-linking candidates";
- generalise the final chain condition to the whip condition (this amounts to introducing lassoes);

- in all the previous steps, the basic chain condition, nrc-continuity (each candidate is nrc-linked to the previous one) was retained ; now, this also can be generalised : in braids, a left linking candidate is allowed to be linked to the target or to a previous right-linking candidate instead of just to the previous one;
- right-linking candidates can be replaced by full patterns (hinges, subsets, SK-loops, ...); we thus get generalised whips and braids: whips(FP) and braids(FP) for any family FP of patterns.

All these chain or net patterns have one property in common, non-anticipativeness or no-look-forward: each new link in the chain being built is allowed based only on previous ones (it doesn't remain there, in expectation of any validation by subsequent ones). This is crucial in terms of complexity.

3) Confluence
In practice, confluence is the property that says: you may use chains (to make eliminations) in any arbitrary order, you will always reach the same final result.
It is relatively easy to see that braid theories have the confluence property. The same is true of braids(FP), provided that family FP itself has the confluence property.
For some time, I thought that whips also had the confluence property, but this is not exactly true. Nevertheless, whips almost have it in the sense that problems of non confluence are very rare: in a sample of 828,144 puzzles generated with the controlled bias generator, I found only 39 cases that led to a different whip rating, i.e. about 5/100,000.

4) T&E vs braids
After introducing braids and after giving the correct precise definition of T&E, I found that elimination by T&E is equivalent to elimination via a braid; this can be extended to T&E(FP) and braids(FP) for any family FP with the confluence property. Here, T&E means T&E(NS+HS, 1), with no recursion (and no guessing). This solved a long standing open question, raised by Ruud: can T&E be written as a (set of) logic rules?

5) Rough T&E classification of puzzles; the T&E conjecture
T&E(FP, n) can be defined in the same way as simple T&E. n is the recursion degree.
At some point in time, someone (anyone knows who?) introduced the conjecture that all the puzzles had at most 2 backdoors; later, Easter Monster disproved this.
A conjecture that I think will hold longer is the T&E conjecture: all the puzzles can be solved at levels 0 (no T&E), 1 or 2.
When I first formulated it, we didn't have a great lot of very hard puzzles; now, with eleven's algorithm, we have millions of SER 11+, and, as was checked by eleven, none of them requires a 3rd level of T&E.
Of course, this isn't a proof. But I fear a formal proof of this conjecture will be as hard as a proof that there's no 16 minimal.

~ 40% of the randomly generated puzzles can be solved at level 0 and almost all the rest at level 1. "Almost all" means that in 10,000,000 puzzles generated with various kinds of random generators (bottom up, top down, controlled bias), I could find none that needed level 2.

Due to point 4 above, the T&E conjecture is equivalent to the following: every puzzle can be solved with NS+HS or with braids or with braids(braids).

6) whips and braids
Perhaps the most surprising result of all this is the resolution power of whips:
- the 10,000,000 puzzles alluded to above can all be solved by whips;
- although braids are in theory much more general than whips, in practice braids lead to a smaller rating only very rarely: in less than 3/1,000 cases.

From a theoretical POV, braids are undoubtedly the good concept: confluence, equivalence with T&E. But, from a practical POV, whips are much more enticing: they satisfy nrc-continuity (chain structure whereas braids look more nettish) and their computational complexity is much lower.

7) why a new thread
I don't plan to launch a new discussion of what has already been discussed at length in the old threads (now restored in pdf, thanks to Jason).
In the past weeks, I had a little time for Sudoku (still very little) and I did what I had wanted to do long ago: a new version of SudoRules, starting from nought and more optimised for whips. The numerical results stated in point 6 were obtained with this faster version.
In the following posts, I'll give a few new examples related to subsumption, rating, ...
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

About subsumption

Postby denis_berthier » Sun Mar 27, 2011 9:22 am



I've shown long ago that most cases of Naked, Hidden or Super-Hidden (Fish) subset patterns are subsumed by whips. But there are very rare cases when this is not the case, in particular for complete quads (i.e. quads that contain the 4 candidates in each of their 4 cells). The following is an interesting such example.
The puzzle comes from the Jellyfish collection, it is #017#Mauricio-002#8#1, with SER = 8:
.............1.....123.456...........23...78..47.6.12...........318.764..58...23.


Code: Select all
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . 1 . | . . . |
| . 1 2 | 3 . 4 | 5 6 . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . 2 3 | . . . | 7 8 . |
| . 4 7 | . 6 . | 1 2 . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . 3 1 | 8 . 7 | 6 4 . |
| . 5 8 | . . . | 2 3 . |
+-------+-------+-------+


I shall use this puzzle to illustrate the well known fact that allowing/disallowing one more rule can have dramatic effects on the classification of puzzles. This is in line with my opinion that there is no unique rating system, but different rating systems depending on different classification goals.

1) "normal" solution with subsets, NRCZT=4
We find an nrczt-rating = 4

Code: Select all
*****  SudoRules version 13.7wter2  *****
.............1.....123.456...........23...78..47.6.12...........318.764..58...23.
nrc-chain[2]  c8n5{r4 r7} - r8n5{c9 c5} ==> r4c5 <> 5
xyz-chain[3]  r6c4{n9 n5} - r5c5{n5 n4} - r9c5{n4 n9} ==> r4c5 <> 9
naked-quads-in-a-block b5{r5c4 r5c5 r6c4 r5c6}{n1 n4 n9 n5} ==> r6c6 <> 9, r6c6 <> 5, r4c6 <> 9, r4c6 <> 5, r4c6 <> 1, r4c5 <> 4, r4c4 <> 9, r4c4 <> 5, r4c4 <> 4
interaction row r4 with block b6 ==> r5c9 <> 4
naked-quads-in-a-block b5{r5c4 r5c5 r6c4 r5c6}{n1 n4 n9 n5} ==> r4c4 <> 1
;;; A
hidden-single-in-row r4 ==> r4c1 = 1
even now, there is a full Jellyfish:
jellyfish-in-columns n9{c2 c8 c3 c7}{r7 r4 r2 r1} ==> r7c9 <> 9, r7c6 <> 9, r7c5 <> 9, r7c4 <> 9, r7c1 <> 9, r4c9 <> 9, r2c9 <> 9, r2c6 <> 9, r2c4 <> 9, r2c1 <> 9, r1c9 <> 9, r1c6 <> 9
nrc-chain[3]  c6n9{r5 r9} - r9c5{n9 n4} - b5n4{r5c5 r5c4} ==> r5c4 <> 9
jellyfish-in-columns n9{c2 c8 c3 c7}{r7 r4 r2 r1} ==> r1c5 <> 9, r1c4 <> 9
singles
GRID 0 SOLVED. LEVEL = NRCZT4_0, MOST COMPLEX RULE = SHQ
495786312
376512894
812394567
189273456
623451789
547968123
264135978
931827645
758649231


2) using only braids, B=10
Suppose we now want a pure braids solution and we de-activate subset rules. Then we get a B-rating = 10. (The B-rating is what I formerly called the pure B-NRCZT-rating)

Code: Select all
*****  SudoRules version 15b.1.8-B  *****
.............1.....123.456...........23...78..47.6.12...........318.764..58...23.
26 givens and 222 candidates
whip[2]  c8n5{r4 r7} - r8n5{c9 .} ==> r4c5 <> 5
whip[3]  r6c4{n9 n5} - r5c5{n5 n4} - r9c5{n4 .} ==> r4c5 <> 9
;;; the following replace most of the NQ eliminations:
whip[4]  b5n7{r4c4 r4c5} - b5n2{r4c5 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c4 <> 5
whip[4]  b5n7{r4c4 r4c5} - b5n2{r4c5 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c4 <> 4
whip[4]  b5n7{r4c4 r4c5} - b5n2{r4c5 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c4 <> 1
whip[4]  b5n7{r4c4 r4c5} - b5n2{r4c5 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c4 <> 9
whip[4]  b5n7{r4c5 r4c4} - b5n2{r4c4 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c5 <> 4
interaction row r4 with block b6 ==> r5c9 <> 4
whip[4]  r6c4{n5 n9} - r5c6{n9 n1} - r5c4{n1 n4} - r5c5{n4 .} ==> r4c6 <> 5
whip[4]  r6c4{n9 n5} - r5c6{n5 n1} - r5c4{n1 n4} - r5c5{n4 .} ==> r4c6 <> 9
whip[4]  r6c4{n5 n9} - r5c6{n9 n1} - r5c4{n1 n4} - r5c5{n4 .} ==> r6c6 <> 5
whip[4]  r6c4{n9 n5} - r5c6{n5 n1} - r5c4{n1 n4} - r5c5{n4 .} ==> r6c6 <> 9
;;; same situation as A, except that r4c6 <> 1 is not obtained
whip[5]  b4n1{r4c1 r5c1} - r5n6{c1 c9} - b6n5{r5c9 r6c9} - r6c4{n5 n9} - r5n9{c4 .} ==> r4c1 <> 5
whip[5]  b4n1{r4c1 r5c1} - r5n6{c1 c9} - b6n9{r5c9 r6c9} - r6c4{n9 n5} - r5n5{c4 .} ==> r4c1 <> 9
whip[5]  r4n1{c1 c6} - b5n8{r4c6 r6c6} - b5n3{r6c6 r4c5} - b5n2{r4c5 r4c4} - b5n7{r4c4 .} ==> r4c1 <> 8
whip[6]  r8c9{n9 n5} - c8n5{r7 r4} - c8n9{r4 r7} - c7n9{r7 r4} - c3n9{r4 r1} - c2n9{r2 .} ==> r2c9 <> 9
whip[6]  r8c9{n9 n5} - c8n5{r7 r4} - c8n9{r4 r7} - c7n9{r7 r4} - c3n9{r4 r2} - c2n9{r1 .} ==> r1c9 <> 9
whip[6]  r9c5{n9 n4} - r5c5{n4 n5} - r8n5{c5 c9} - b9n9{r8c9 r9c9} - b7n9{r9c1 r8c1} - r3n9{c1 .} ==> r7c5 <> 9
braid[6]  b5n5{r5c4 r6c4} - r8c9{n5 n9} - r6n9{c4 c1} - r3n9{c1 c5} - r5c5{n5 n4} - r9c5{n9 .} ==> r5c9 <> 5
whip[7]  r9c5{n4 n9} - r5c5{n9 n5} - r8n5{c5 c9} - r8n9{c9 c1} - r3n9{c1 c9} - r6n9{c9 c4} - r5n9{c4 .} ==> r7c5 <> 4
whip[7]  r9c5{n9 n4} - r5c5{n4 n5} - r8n5{c5 c9} - r8n9{c9 c1} - r3n9{c1 c9} - r6n9{c9 c4} - r5n9{c4 .} ==> r1c5 <> 9
braid[7]  r2c8{n7 n9} - r3c9{n9 n8} - c7n8{r2 r7} - c7n9{r7 r4} - r9n7{c9 c1} - r3c1{n7 n9} - b4n9{r6c1 .} ==> r1c9 <> 7
braid[7]  r2c8{n7 n9} - r3c9{n9 n8} - c7n8{r2 r7} - c7n9{r7 r4} - r9n7{c9 c1} - r3c1{n7 n9} - b4n9{r6c1 .} ==> r2c9 <> 7
braid[7]  r2c8{n7 n9} - r9n7{c1 c9} - r3c9{n7 n8} - c7n8{r1 r7} - c7n9{r1 r4} - r3c1{n7 n9} - b4n9{r6c1 .} ==> r2c1 <> 7
braid[7]  r6c4{n5 n9} - r8c9{n5 n9} - r5n9{c4 c1} - r3n9{c1 c5} - r8n5{c9 c5} - r5c5{n5 n4} - r9c5{n9 .} ==> r6c9 <> 5
interaction block b6 with row r4 ==> r4c3 <> 5
interaction column c3 with block b1 ==> r1c1 <> 5
interaction column c3 with block b1 ==> r2c1 <> 5
whip[4]  c1n5{r5 r6} - r6c4{n5 n9} - r5n9{c4 c9} - r5n6{c9 .} ==> r5c1 <> 1
hidden-single-in-a-block ==> r4c1 = 1
braid[10]  b4n8{r4c2 r6c1} - r6n5{c1 c4} - c5n3{r4 r7} - r6n9{c4 c9} - r8c9{n9 n5} - c5n5{r8 r1} - c5n2{r1 r8} - c5n7{r1 r3} - r3c1{n7 n9} - r8n9{c9 .} ==> r4c5 <> 8
interaction column c5 with block b2 ==> r1c6 <> 8
interaction column c5 with block b2 ==> r2c6 <> 8
whip[7]  b2n8{r1c5 r3c5} - c1n8{r3 r6} - r6n5{c1 c4} - r6n9{c4 c9} - r3n9{c9 c1} - r8n9{c1 c5} - r9n9{c6 .} ==> r1c2 <> 8
whip[8]  b2n8{r1c5 r3c5} - c5n7{r3 r4} - c5n3{r4 r7} - c5n2{r7 r8} - r8c1{n2 n9} - r3n9{c1 c9} - r6n9{c9 c4} - r5n9{c4 .} ==> r1c5 <> 5
braid[5]  r6n3{c9 c6} - c5n3{r4 r7} - r6c4{n9 n5} - r8c9{n9 n5} - c5n5{r8 .} ==> r6c9 <> 9
naked-single ==> r6c9 = 3
naked-single ==> r6c6 = 8
hidden-single-in-a-row ==> r4c2 = 8
whip[2]  r6n9{c4 c1} - b7n9{r9c1 .} ==> r7c4 <> 9
whip[3]  r6n9{c4 c1} - r8n9{c1 c9} - r3n9{c9 .} ==> r5c5 <> 9
whip[3]  r9c5{n9 n4} - r5c5{n4 n5} - r6c4{n5 .} ==> r9c4 <> 9
whip[3]  r6n9{c1 c4} - r5n9{c4 c9} - b9n9{r9c9 .} ==> r7c1 <> 9
whip[4]  b4n9{r6c1 r4c3} - b6n9{r4c9 r5c9} - r8n9{c9 c5} - r3n9{c5 .} ==> r9c1 <> 9
whip[3]  b7n9{r7c2 r8c1} - b4n9{r5c1 r4c3} - b6n9{r4c9 .} ==> r7c9 <> 9
whip[4]  r9n9{c6 c9} - r8n9{c9 c1} - r5n9{c1 c4} - r6n9{c4 .} ==> r7c6 <> 9
whip[4]  b8n9{r9c6 r8c5} - r3n9{c5 c1} - r6n9{c1 c4} - r5n9{c4 .} ==> r9c9 <> 9
interaction row r9 with block b8 ==> r8c5 <> 9
whip[2]  r8n9{c9 c1} - b4n9{r5c1 .} ==> r4c9 <> 9
whip[3]  r6n9{c4 c1} - r3n9{c1 c9} - r8n9{c9 .} ==> r1c4 <> 9
whip[3]  r6n9{c4 c1} - r3n9{c1 c9} - r8n9{c9 .} ==> r2c4 <> 9
interaction column c4 with block b5 ==> r5c6 <> 9
whip[3]  r6n9{c1 c4} - r5n9{c4 c9} - r8n9{c9 .} ==> r1c1 <> 9
whip[3]  r6n9{c1 c4} - r5n9{c4 c9} - r8n9{c9 .} ==> r2c1 <> 9
whip[3]  r6n9{c1 c4} - r5n9{c4 c9} - r8n9{c9 .} ==> r3c1 <> 9
whip[3]  r8n9{c9 c1} - r5n9{c1 c4} - r6n9{c4 .} ==> r3c9 <> 9
singles
GRID 0 SOLVED. B = 10, MOST COMPLEX RULE = Braid[10]
495786312
376512894
812394567
189273456
623451789
547968123
264135978
931827645
758649231


3) Using only whips, W>18
Suppose now we wanted a solution with only whips. Then we would have to accept whips of length > 18. Actually I didn't try longer ones because it didn't seem interesting to go further. This means the W-rating is > 18. (The W-rating is what I formerly called the pure NRCZT-rating).

4) Using g-whips, GW=4
What I now call g-whips is what I formerly called hinged-whips, grouped-whips or whips[BI]. They are the simplest extension of whips, with the FP family = hinges.
One side effect of my new version of SudoRules is that it was relatively easy to program g-whips.
The GW-rating is 4.

Notation: I use an obvious extension of the nrc-notation: r1c123 means the row-segment r1c1 r1c2 r1c3. Notice however that n1r1c123 doesn't mean that n1 must be present in the 3 cells. It means, by convention, that n1 must be present in at least 2 of these 3 cells. The case when n1 is present in only one cell is dealt with as a simple candidate. This is in conformance with my general approach that simplest patterns are used before more complex ones. (BTW, my implementation of g-whips is strongly dependent on my implementation of whips.)

Code: Select all
*****  SudoRules version 15b.1.12-GW  *****
.............1.....123.456...........23...78..47.6.12...........318.764..58...23.
26 givens and 222 candidates
whip[2]  c8n5{r4 r7} - r8n5{c9 .} ==> r4c5 <> 5
whip[3]  r6c4{n9 n5} - r5c5{n5 n4} - r9c5{n4 .} ==> r4c5 <> 9
g-whip[3]  b6n9{r4c7 r456c9} - r3n9{c9 c5} - r8n9{c5 .} ==> r4c1 <> 9
g-whip[3]  b4n9{r4c3 r456c1} - r3n9{c1 c5} - r8n9{c5 .} ==> r4c9 <> 9
g-whip[3]  b7n9{r7c3 r789c1} - r3n9{c1 c9} - b9n9{r9c9 .} ==> r7c5 <> 9
g-whip[3]  b4n9{r6c1 r4c123} - b6n9{r4c7 r456c9} - b9n9{r9c9 .} ==> r7c1 <> 9
g-whip[3]  b7n9{r7c3 r789c1} - r5n9{c1 c456} - r6n9{c6 .} ==> r7c9 <> 9
whip[4]  b5n7{r4c4 r4c5} - b5n2{r4c5 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c4 <> 5
whip[4]  b5n7{r4c4 r4c5} - b5n2{r4c5 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c4 <> 4
whip[4]  b5n7{r4c4 r4c5} - b5n2{r4c5 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c4 <> 1
whip[4]  b5n7{r4c4 r4c5} - b5n2{r4c5 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c4 <> 9
whip[4]  b5n7{r4c5 r4c4} - b5n2{r4c4 r4c6} - b5n3{r4c6 r6c6} - b5n8{r6c6 .} ==> r4c5 <> 4
interaction row r4 with block b6 ==> r5c9 <> 4
whip[4]  r6c4{n5 n9} - r5c6{n9 n1} - r5c4{n1 n4} - r5c5{n4 .} ==> r4c6 <> 5
whip[4]  r6c4{n9 n5} - r5c6{n5 n1} - r5c4{n1 n4} - r5c5{n4 .} ==> r4c6 <> 9
whip[4]  r6c4{n5 n9} - r5c6{n9 n1} - r5c4{n1 n4} - r5c5{n4 .} ==> r6c6 <> 5
whip[4]  r6c4{n9 n5} - r5c6{n5 n1} - r5c4{n1 n4} - r5c5{n4 .} ==> r6c6 <> 9
g-whip[3]  b9n9{r7c7 r789c9} - r6n9{c9 c1} - b7n9{r9c1 .} ==> r7c4 <> 9
g-whip[4]  b4n9{r5c1 r4c123} - b6n9{r4c7 r456c9} - r8n9{c9 c5} - r9n9{c6 .} ==> r3c1 <> 9
whip[3]  r3n9{c5 c9} - r8n9{c9 c1} - r6n9{c1 .} ==> r5c5 <> 9
whip[3]  r9c5{n9 n4} - r5c5{n4 n5} - r6c4{n5 .} ==> r9c4 <> 9
whip[4]  r9n7{c9 c1} - r3c1{n7 n8} - r3c9{n8 n9} - r2c8{n9 .} ==> r2c9 <> 7
whip[4]  r9n7{c9 c1} - r3c1{n7 n8} - r3c9{n8 n9} - r2c8{n9 .} ==> r1c9 <> 7
whip[4]  r2c8{n7 n9} - r3n9{c9 c5} - r3n7{c5 c9} - r9n7{c9 .} ==> r2c1 <> 7
whip[4]  r8c9{n5 n9} - r3n9{c9 c5} - r9c5{n9 n4} - r5c5{n4 .} ==> r8c5 <> 5
singles ==> r8c9 = 5, r4c8 = 5
interaction column c3 with block b1 ==> r1c1 <> 5, r2c1 <> 5
whip[3]  r8n9{c1 c5} - r9n9{c6 c9} - r3n9{c9 .} ==> r7c3 <> 9
whip[3]  r8n9{c1 c5} - r9n9{c6 c9} - r3n9{c9 .} ==> r7c2 <> 9
interaction block b7 with column c1 ==> r1c1 <> 9, r2c1 <> 9, r5c1 <> 9, r6c1 <> 9
interaction block b4 with row r4 ==> r4c7 <> 9
interaction block b6 with column c9 ==> r9c9 <> 9
interaction block b9 with row r7 ==> r7c6 <> 9
interaction block b6 with column c9 ==> r1c9 <> 9, r2c9 <> 9, r3c9 <> 9
singles
GRID 0 SOLVED. GW = 4, MOST COMPLEX RULE = G-Whip[4]
495786312
376512894
812394567
189273456
623451789
547968123
264135978
931827645
758649231
[edit 04/05/2011: corrected a bug in my implementation of g-whips]
Last edited by denis_berthier on Tue Apr 05, 2011 7:33 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: About subsumption

Postby ronk » Sun Mar 27, 2011 2:04 pm

denis_berthier wrote:1) "normal" solution with subsets, NRCZT=4
...
Code: Select all
*****  SudoRules version 13.7wter2  *****
.............1.....123.456...........23...78..47.6.12...........318.764..58...23.
nrc-chain[2]  c8n5{r4 r7} - r8n5{c9 c5} ==> r4c5 <> 5
xyz-chain[3]  r6c4{n9 n5} - r5c5{n5 n4} - r9c5{n4 n9} ==> r4c5 <> 9
naked-quads-in-a-block b5{r5c4 r5c5 r6c4 r5c6}{n1 n4 n9 n5} ==> r6c6 <> 9, r6c6 <> 5, r4c6 <> 9, r4c6 <> 5, r4c6 <> 1, r4c5 <> 4, r4c4 <> 9, r4c4 <> 5, r4c4 <> 4
interaction row r4 with block b6 ==> r5c9 <> 4
naked-quads-in-a-block b5{r5c4 r5c5 r6c4 r5c6}{n1 n4 n9 n5} ==> r4c4 <> 1
;;; A
hidden-single-in-row r4 ==> r4c1 = 1
even now, there is a full Jellyfish:
jellyfish-in-columns n9{c2 c8 c3 c7}{r7 r4 r2 r1} ==> r7c9 <> 9, r7c6 <> 9, r7c5 <> 9, r7c4 <> 9, r7c1 <> 9, r4c9 <> 9, r2c9 <> 9, r2c6 <> 9, r2c4 <> 9, r2c1 <> 9, r1c9 <> 9, r1c6 <> 9
nrc-chain[3]  c6n9{r5 r9} - r9c5{n9 n4} - b5n4{r5c5 r5c4} ==> r5c4 <> 9
jellyfish-in-columns n9{c2 c8 c3 c7}{r7 r4 r2 r1} ==> r1c5 <> 9, r1c4 <> 9
...

I realize the "normal" solution is not the focus of your post, but why does the same "naked-quads-in-a-block b5" appear a second time? The elimination(s) made upon the 2nd appearance were available at the 1st.

Ditto for the 2nd appearance of "jellyfish-in-columns n9."
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: About subsumption

Postby denis_berthier » Sun Mar 27, 2011 2:53 pm

ronk wrote:I realize the "normal" solution is not the focus of your post, but why does the same "naked-quads-in-a-block b5" appear a second time? The elimination(s) made upon the 2nd appearance were available at the 1st.
Ditto for the 2nd appearance of "jellyfish-in-columns n9."

There are 2 characteristics of SudoRules:
- eliminations are done one by one (when you see several on the same line, it means that I've edited the raw output manually) ;
- the strategy is "simplest first", i.e. the simplest elimination available at any time is applied (simplest in my classification of rules).

As a result, when a pattern such as NQ or SHQ is detected and allows a few eliminations, part of these eliminations may activate a simpler pattern (here basic interactions), which is then applied before the other eliminations allowed by the NQ or SHQ.
I know this is very unnatural for a human player, but it can't change the final result.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

About subsumption (continued)

Postby denis_berthier » Sat Apr 02, 2011 5:49 am



I've now coded g-braids in SudoRules. As for braids wrt whips, g-braids are much slower and more greedy for memory than g-whips.

For the same exceptional puzzle as above, I get GB = 4.
So, we finally have a whole range of ratings: NRCZT = 4, W > 18 , B = 10, GW = 4, GB = 4

[Edit 04/05/2011: modified the GW rating after the correction of a bug in my implementation of g-whips]
Last edited by denis_berthier on Tue Apr 05, 2011 7:35 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: About subsumption (continued)

Postby Mauricio » Sat Apr 02, 2011 4:15 pm

denis_berthier wrote:I've now coded g-braids in SudoRules. As for braids wrt whips, g-braids are much slower and more greedy for memory than g-whips.

For the same exceptional puzzle as above, I get GB = 4.
So, we finally have a whole range of ratings: NRCZT = 4, W > 18 , B = 10, GW = 6, GB = 4

Code: Select all
*****  SudoRules version 15b.1.11-GB  *****
.............1.....123.456...........23...78..47.6.12...........318.764..58...23.
same path as with g-whips, down to: hidden-single-in-a-block ==> r4c1 = 1
...


After following your solution up to hidden-single-in-a-block ==> r4c1 = 1, xsudo reports (formatted by me)

Code: Select all
g-whip[3]  9b7{r7c2 r789c1} - 9r6{c1 c9} - 9b9{r789c9 .}    ==> r7c4 <> 9
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Re: About subsumption (continued)

Postby denis_berthier » Sat Apr 02, 2011 4:51 pm

Mauricio wrote:After following your solution up to hidden-single-in-a-block ==> r4c1 = 1

I can't check your sayings, as xsudo works only on windows. But I seriously doubt that xsudo follows the same path as SudoRules. So, could you please publish the complete exact xsudo output without any interpretation or reformatting?

Mauricio wrote:xsudo reports (formatted by me)
Code: Select all
g-whip[3]  9b7{r7c2 r789c1} - 9r6{c1 c9} - 9b9{r789c9 .}    ==> r7c4 <> 9

It seems this is not only "formatted" but interpreted as a g-whip by you.
BTW, g-whips don't have segments as left linking candidates.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: About subsumption (continued)

Postby Mauricio » Sat Apr 02, 2011 5:10 pm

denis_berthier wrote:
Mauricio wrote:After following your solution up to hidden-single-in-a-block ==> r4c1 = 1

I can't check your sayings, as xsudo works only on windows. But I seriously doubt that xsudo follows the same path as SudoRules. So, could you please publish the complete exact xsudo output without any interpretation or reformatting?

I thought it was clear that I followed your solution path, and then I used xsudo to check what the next step was, not that xsudo followed your path right from step 1.

denis_berthier wrote:BTW, g-whips don't have segments as left linking candidates.
About not allowing segments as llc's, is there a reason not to allow them? I remember you said once that allowing them does not increase the resolution power, but to me that claim is not clear.

let reword the whip
Code: Select all
g-whip[3]  9b7{r7c2 r789c1} - 9r6{c1 c9} - 9b9{r9c9 .}   ==> r7c4 <> 9
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Re: About subsumption (continued)

Postby denis_berthier » Sat Apr 02, 2011 5:28 pm

Mauricio wrote:I thought it was clear that I followed your solution path, and then I used xsudo to check what the next step was, not that xsudo followed your path right from step 1.

Not clear for me. Anyway, I'd like to see the real xsudo output.

Mauricio wrote:
denis_berthier wrote:BTW, g-whips don't have segments as left linking candidates.
About not allowing segments as llc's, is there a reason not to allow them? I remember you said once that allowing them does not increase the resolution power, but to me that claim is not clear.

If a segment candidate could be used as a left-linking candidate, then any of its elements could be used instead. Accepting them therefore provides no additional power but it increases computational complexity.

Mauricio wrote:let reword the whip
Code: Select all
g-whip[3]  9b7{r7c2 r789c1} - 9r6{c1 c9} - 9b9{r9c9 .}   ==> r7c4 <> 9

ok, but once again, I'd like to see xsudo real output.

For a better understanding, at the point, you're mentioning, the PM is (I filled only the relevant cells and 9? is the target):

Code: Select all
+-------------------------+-------------------------+-------------------------+
|x       x       x        |x       x       x        |x       x       x        |
|x       x       x        |x       1       x        |x       x       x        |
|x       1       2        |3       x       4        |5       6       x        |
+-------------------------+-------------------------+-------------------------+
|x       x       x        |1       x       x        |x       x       x        |
|x       2       3        |x       x       x        |7       8       x        |
|589     4       7        |59      6       38       |1       2       359      |
+-------------------------+-------------------------+-------------------------+
|2467    679     469      |9?      x       x        |89      1579    1578     |
|29      3       1        |8       x       7        |6       4       59       |
|4679    5       8        |x       x       x        |2       3       179      |
+-------------------------+-------------------------+-------------------------+
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: About subsumption (continued)

Postby ronk » Sat Apr 02, 2011 5:35 pm

denis_berthier wrote:For a better understanding, at the point, you're mentioning, the PM is (I filled only the relevant cells and 9? is the target):

A complete pencilmark grid, which could be pasted into xsudo or another solver, would be much more useful. I believe the following matches the puzzle state being discussed.
Code: Select all
 3456789 6789    4569    | 25679   25789   25689   | 3489    179     1234789
 3456789 6789    4569    | 25679   1       25689   | 3489    79      234789
 789     1       2       | 3       789     4       | 5       6       789
-------------------------+-------------------------+------------------------
 1       689     569     | 27      2378    238     | 349     59      3456
 569     2       3       | 1459    459     159     | 7       8       569
 589     4       7       | 59      6       38      | 1       2       359
-------------------------+-------------------------+------------------------
 2467    679     469     | 124569  2345    123569  | 89      1579    1578
 29      3       1       | 8       259     7       | 6       4       59
 4679    5       8       | 1469    49      169     | 2       3       179
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: more on whips, braids, T&E...

Postby denis_berthier » Tue Apr 05, 2011 7:36 am

Thanks to Mauricio's remark, I could find a bug in my implementation of g-whips. It is now corrected in the previous posts. As it introduces a shorter g-whip earlier in the resolution path, the objection no longer applies.
(The bug made me miss a few whips in rare cases: about 1%).
[completed 04/15/11]
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

One more case of an anomalous SE rating

Postby denis_berthier » Fri Apr 15, 2011 7:54 am


.

"Anomalies" in the SE rating have been reported many times. Anomalies shouldn't be a surprise, for (at least) 2 reasons:
- the SE rating is based on a selection of techniques known at the time of its programming (Aug. 2006 for the last version) and we know that ratings that could be obtained with additional techniques may be very different (even if these ratings are defined in a way compatible with the ratings of the techniques already included in SE);
- the SE rating is not based on theoretical principles, but on a specific classification of the techniques it includes; different people may have different views, e.g. why should an x-wing or swordfish [3.4, resp. 4.0] be "harder" than a hidden pair or triplet [3.2, resp. 3.8], whereas a jellyfish [5.2] is simpler than a hidden quad [5.4] ? (for the SE rating of the various techniques, see Mike Barker's post near the middle of this page: http://forum.enjoysudoku.com/rating-rules-puzzles-ordering-the-rules-t5995.html

In this context, what's surprising should not be "anomalies", it should be that, globally, SER is not so bad - at least for puzzles that don't need "dynamic forcing chains", i.e. more or less a second level of T&E.

Anyway, here is one more "anomalous" case. It is taken from the examples given on the SE website:

Code: Select all
+-------+-------+-------+
| . . . | . . . | . . . |
| . 9 . | . 3 . | . 4 . |
| . . 2 | 6 . 1 | 5 . . |
+-------+-------+-------+
| . . 4 | . . . | 2 . . |
| . 3 . | . 5 . | . 1 . |
| . . 6 | . . . | 7 . . |
+-------+-------+-------+
| . . 5 | 8 . 2 | 6 . . |
| . 7 . | . 4 . | . 9 . |
| . . . | . . . | . . . |
+-------+-------+-------+


The SE rating is 8.3, which is far from the hardest known (as of today, or even as of SE last version, mentioning a puzzle with SER = 10.0). But SE 8.3 remains a very high rating for most human players.
Still according to Mike's post, in SE, 8.3 corresponds to "Multiple (9-12 nodes) Cell/Region Forcing Chains". I don't know exactly what this means. [ I've never seen any definition of the techniques included in SE, especially all the kinds of forcing chains: Forcing Chain, Forcing Chain+, multiple, dynamic, dynamic+CCRD), nor how "nodes" are counted - and I don't have time to reverse-engineer the Java code. Any clarification on these points would be welcome.] The only thing that seems clear to me is, the expression "forcing chain" in SE doesn't mean the same thing as in Sudopedia.
8.3 is after 7.5 "Forcing Chain (17-24 nodes)"

Nevertheless, this puzzle can be solved with whips of length <= 4 (if "node" in SE means anything similar to the number of 2D-cells involved in the chain, then these whips have <= 4 nodes; if it means anything close to the number of candidates involved, a whip[4] has 8 left- or right- linking candidates; I can't say exactly how many t- or z- candidates are involved in the the present whips[4], but my experience is that there are generally few 2D-cells with additional z- or t-candidates and there are few additional candidates in each of these cells - so that it is very unlikely that they reach the 17-24 zone).

Admittedly, this puzzle requires many short whips, but this can't be considered an objection, as SER is based only on the hardest step.

In the following resolution path, I consider only whips. Many steps could be replaced by hidden pairs or swordfish, but if the subset rules are activated, it doesn't change the W rating.


Hidden Text: Show
Code: Select all
*****  SudoRules version 15b.1.12-W  *****
..........9..3..4...26.15....4...2...3..5..1...6...7....58.26...7..4..9..........
21 givens and 250 candidates
interaction row r3 with block b1 ==> r1c1 <> 4, r1c2 <> 4
whip[3]  c2n6{r1 r9} - c5n6{r9 r4} - c8n6{r4 .} ==> r1c1 <> 6
whip[3]  c5n2{r1 r6} - c2n2{r6 r9} - c8n2{r9 .} ==> r1c4 <> 2
whip[3]  c7n9{r1 r5} - c3n9{r5 r9} - b8n9{r9c6 .} ==> r1c5 <> 9
whip[3]  b1n3{r1c3 r3c1} - r7n3{c1 c9} - c7n3{r9 .} ==> r1c8 <> 3
whip[3]  c8n2{r1 r9} - c2n2{r9 r6} - c5n2{r6 .} ==> r1c9 <> 2
whip[3]  b1n3{r1c3 r3c1} - r7n3{c1 c8} - c7n3{r9 .} ==> r1c9 <> 3
whip[3]  c8n6{r1 r4} - c5n6{r4 r9} - c2n6{r9 .} ==> r1c9 <> 6
whip[2]  b3n2{r1c8 r2c9} - b3n6{r2c9 .} ==> r1c8 <> 8, r1c8 <> 7
whip[2]  b3n2{r2c9 r1c8} - b3n6{r1c8 .} ==> r2c9 <> 8, r2c9 <> 7, r2c9 <> 1
whip[3]  r3n9{c5 c9} - r6n9{c9 c1} - r7n9{c1 .} ==> r4c5 <> 9
whip[3]  c5n6{r4 r9} - c2n6{r9 r1} - c8n6{r1 .} ==> r4c6 <> 6
whip[3]  b5n6{r4c5 r5c6} - r8n6{c6 c1} - r2n6{c1 .} ==> r4c9 <> 6
whip[3]  c3n9{r5 r9} - c6n9{r9 r1} - c7n9{r1 .} ==> r5c4 <> 9
whip[3]  c3n9{r5 r9} - c4n9{r9 r1} - c7n9{r1 .} ==> r5c6 <> 9
whip[3]  c7n9{r5 r1} - b2n9{r1c6 r3c5} - r7n9{c5 .} ==> r5c1 <> 9
whip[3]  c3n9{r5 r9} - r7n9{c1 c5} - r3n9{c5 .} ==> r5c9 <> 9
whip[3]  r5n2{c1 c4} - r2n2{c4 c9} - r8n2{c9 .} ==> r6c1 <> 2
whip[3]  b4n2{r5c1 r6c2} - c5n2{r6 r1} - c8n2{r1 .} ==> r9c1 <> 2
whip[3]  c2n2{r6 r9} - r8n2{c1 c9} - r2n2{c9 .} ==> r6c4 <> 2
whip[3]  r3n9{c5 c9} - r4n9{c9 c1} - r7n9{c1 .} ==> r6c5 <> 9
whip[3]  b1n3{r3c1 r1c3} - c7n3{r1 r9} - r7n3{c8 .} ==> r8c1 <> 3
whip[3]  c7n3{r8 r1} - c3n3{r1 r9} - b8n3{r9c6 .} ==> r8c9 <> 3
whip[3]  c3n3{r8 r1} - c7n3{r1 r8} - r7n3{c8 .} ==> r9c1 <> 3
whip[3]  r8n6{c1 c6} - r5n6{c6 c9} - r2n6{c9 .} ==> r9c1 <> 6
whip[2]  b7n2{r8c1 r9c2} - b7n6{r9c2 .} ==> r8c1 <> 8, r8c1 <> 1
whip[2]  b7n2{r9c2 r8c1} - b7n6{r8c1 .} ==> r9c2 <> 8, r9c2 <> 4, r9c2 <> 1
whip[3]  c8n2{r9 r1} - r1n6{c8 c2} - r9c2{n6 .} ==> r9c9 <> 2
whip[3]  c3n9{r9 r5} - c7n9{r5 r1} - r3n9{c9 .} ==> r9c5 <> 9
whip[3]  c5n6{r9 r4} - c8n6{r4 r1} - c2n6{r1 .} ==> r9c6 <> 6
whip[3]  c7n3{r9 r1} - c3n3{r1 r8} - b8n3{r8c6 .} ==> r9c8 <> 3, r9c9 <> 3
entering level W-4 with <Fact-33391>
whip[4]  c7n9{r1 r5} - c3n9{r5 r9} - r7n9{c1 c5} - b2n9{r3c5 .} ==> r1c9 <> 9
whip[4]  r7c8{n7 n3} - c7n3{r8 r1} - b3n9{r1c7 r3c9} - c5n9{r3 .} ==> r7c5 <> 7
interaction row r7 with block b9 ==> r9c8 <> 7, r9c9 <> 7
whip[4]  r3n9{c9 c5} - r7c5{n9 n1} - r7c2{n1 n4} - r3c2{n4 .} ==> r3c9 <> 8
whip[4]  r3n9{c9 c5} - r7n9{c5 c1} - r7n3{c1 c8} - c7n3{r9 .} ==> r3c9 <> 3
whip[3]  b3n3{r1c7 r3c8} - r7n3{c8 c9} - c7n3{r9 .} ==> r1c1 <> 3
whip[3]  r7c2{n1 n4} - c1n4{r7 r3} - c1n3{r3 .} ==> r7c1 <> 1
whip[3]  c3n9{r9 r5} - c7n9{r5 r1} - r1n3{c7 .} ==> r9c3 <> 3
whip[4]  r7c5{n9 n1} - r7c2{n1 n4} - c1n4{r9 r3} - c1n3{r3 .} ==> r7c1 <> 9
singles ==> r7c5 = 9, r3c9 = 9, r5c7 = 9, r9c3 = 9, r9c7 = 4
interaction row r9 with block b8 ==> r8c4 <> 3, r8c6 <> 3
whip[2]  c1n3{r3 r7} - c1n4{r7 .} ==> r3c1 <> 8, r3c1 <> 7
whip[2]  b2n4{r1c6 r1c4} - r1n9{c4 .} ==> r1c6 <> 8, r1c6 <> 7, r1c6 <> 5
whip[2]  b2n4{r1c4 r1c6} - r1n9{c6 .} ==> r1c4 <> 7, r1c4 <> 5
interaction row r1 with block b1 ==> r2c1 <> 5
whip[3]  r3c2{n8 n4} - r7c2{n4 n1} - r9c1{n1 .} ==> r2c1 <> 8, r1c1 <> 8
whip[4]  r5n6{c6 c9} - r2c9{n6 n2} - c4n2{r2 r5} - r5n4{c4 .} ==> r5c6 <> 8, r5c6 <> 7
whip[4]  r5c6{n4 n6} - r8c6{n6 n5} - c4n5{r9 r2} - c4n2{r2 .} ==> r5c4 <> 4
whip[2]  r5n6{c9 c6} - r5n4{c6 .} ==> r5c9 <> 8
interaction row r5 with block b4 ==> r6c2 <> 8, r6c1 <> 8, r4c1 <> 8, r4c2 <> 8
interaction column c2 with block b1 ==> r1c3 <> 8, r2c3 <> 8
whip[3]  b3n7{r1c9 r3c8} - r3c5{n7 n8} - b1n8{r3c2 .} ==> r1c9 <> 8
whip[3]  r9n2{c8 c2} - b4n2{r6c2 r5c1} - c1n8{r5 .} ==> r9c8 <> 8
whip[4]  c3n7{r1 r5} - r5c4{n7 n2} - r2n2{c4 c9} - r2n6{c9 .} ==> r2c1 <> 7
whip[4]  r8n6{c6 c1} - r2c1{n6 n1} - c3n1{r2 r8} - r8c4{n1 .} ==> r8c6 <> 5
singles ==> r8c6 = 6, r5c6 = 4, r1c6 = 9, r1c4 = 4, r5c9 = 6, r2c9 = 2, r1c8 = 6, r8c1 = 2, r9c2 = 6, r6c2 = 2, r5c4 = 2, r1c5 = 2, r9c8 = 2 r2c1 = 6, r4c5 = 6, r6c9 = 4
interaction column c8 with block b6 ==> r4c9 <> 5
interaction row r5 with block b4 ==> r4c1 <> 7
whip[3]  r1c9{n1 n7} - b1n7{r1c1 r2c3} - b1n1{r2c3 .} ==> r1c7 <> 1
whip[3]  r1c9{n1 n7} - r3n7{c8 c5} - r9c5{n7 .} ==> r9c9 <> 1
whip[3]  r9c9{n8 n5} - c6n5{r9 r2} - r2n8{c6 .} ==> r8c7 <> 8
interaction column c7 with block b3 ==> r3c8 <> 8
interaction column c8 with block b6 ==> r4c9 <> 8
naked-single ==> r4c9 = 3
whip[2]  r1c9{n1 n7} - r7c9{n7 .} ==> r8c9 <> 1
whip[3]  r4c6{n7 n8} - c5n8{r6 r3} - c5n7{r3 .} ==> r9c6 <> 7
whip[3]  b8n7{r9c5 r9c4} - r2c4{n7 n5} - r8c4{n5 .} ==> r9c5 <> 1
singles
GRID 0 SOLVED. W = 4, MOST COMPLEX RULE = Whip[4]
587429361
691735842
342681579
154967283
738254916
926318754
415892637
273546198
869173425

I was not present on the forum when a thread (http://forum.enjoysudoku.com/team-project-c-or-c-explainer-like-rating-program-t30083.html) was opened with the goal of making a faster version of SE (and I haven't read all the discussions there - and I don't know the needs of the patterns game which motivated that thread), but it seems to me that the accumulation of such "anomalies" should speak in favour of a really new rating system - or, rather, system of rating systems, because I don't believe in a unique rating.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: more on whips, braids, T&E...

Postby JasonLion » Fri Apr 15, 2011 12:56 pm

I don't think you are using the word "anomaly" in the same way that most of us are when talking about SE. In SE land an "anomaly" is a rating that is inconsistent from the point of view of SEs definition, almost invariably because of a coding error in the SE code. Meanwhile I believe you are using "anomaly" to talk about inconsistencies with things outside the world of SE, of which there are many which are routinely ignored by users of SE.

I find SE ratings interesting for two reasons that have nothing much to do with each other. First, SE ratings between about 1 and 7 correlate to the difficulty a human player might have solving the puzzle about as well as any single number rating system (ie they are all poor, and SE is no worse than any other). Second, SE ratings between about 9 and 12 seem to correlate fairly well with the computational complexity of producing puzzles. Producing puzzles with high SE ratings is far far more difficult than producing puzzles with lower ratings. While this correlation is also far from perfect, it seems to be far better than other available rating systems at rating the complexity of producing puzzles in this range.

The first aspect, human difficulty, is what originally sparked interest in SE. But it is the second aspect, computational complexity, that seems to have given SE it's current prominence in places like the puzzle game.
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: more on whips, braids, T&E...

Postby denis_berthier » Sat Apr 16, 2011 5:22 am

JasonLion wrote:I don't think you are using the word "anomaly" in the same way that most of us are when talking about SE. In SE land an "anomaly" is a rating that is inconsistent from the point of view of SEs definition, almost invariably because of a coding error in the SE code.

"almost invariably"? mmm. How could an inconsistency "from the point of view of SEs definition" be other than a "coding error" - which ordinary people call a bug. I can therefore hardly understand this overly restricted usage of the word "anomaly".
Moreover, as most of the hard techniques ("forcing chains") are not defined but by Java code (plus, occasionally, a few cryptic words), what is a bug in the code wrt to the code itself?
(Oh, well, after scanning the "SE rating clone" thread, I realise the simple techniques are not much better defined.)

JasonLion wrote:Meanwhile I believe you are using "anomaly" to talk about inconsistencies with things outside the world of SE, of which there are many which are routinely ignored by users of SE.

Yep. I was using "anomaly" with its standard English meaning. Anomalies can appear in relation to techniques not in SE but also between techniques in SE, such as the example I've given for subsets. But let's not restart here a discussion pertaining to the cloning thread and far from the topics of the present thread.

JasonLion wrote:I find SE ratings interesting for two reasons that have nothing much to do with each other. First, SE ratings between about 1 and 7 correlate to the difficulty a human player might have solving the puzzle about as well as any single number rating system (ie they are all poor, and SE is no worse than any other).

I can only agree on this and I've also shown long ago (in the "rating" thread) that all the known ratings are strongly correlated within this range. But, of course, correlation is meaningful only statistically, so that deviations from these stats can also be seen on many individual puzzles.
From a practical POV, I'm not sure having a numerical rating in this range is better than classifying puzzles according to the techniques they need to be solved, as done in all the commercial approaches.

JasonLion wrote:Second, SE ratings between about 9 and 12 seem to correlate fairly well with the computational complexity of producing puzzles. Producing puzzles with high SE ratings is far far more difficult than producing puzzles with lower ratings. While this correlation is also far from perfect, it seems to be far better than other available rating systems at rating the complexity of producing puzzles in this range.

On all of this, I clearly disagree.
- If there is any such correlation for the puzzles between SER 9 and 12, it can only be with exp(SER) or even exp(exp(SER)), not with SER itself. This is not very important, as it could easily be changed by a (highly nonlinear) rescaling, but SER drastically flattens everything in this range.
- Hard puzzles are rare, and the harder the rarer - by any known measure of hardness. I don't think this has much to do with SE in particular.


As many people here, I use SE as a blackbox and I've never tried to get more of it than a vague indication of the difficulty of a puzzle. I understand that some people may want a faster version of SE, but I'd be much more interested by a radical departure, e.g. along Paul's line of work.

As for the techniques SE uses in the puzzles rated above ~8 (which was the main question raised by my post), I'd like to believe I'm the only one that doesn't understand what all its types of "forcing chains" are (this is what is at stakes in the 8-12 range). But I fear I'm not. Even after scanning the whole SE cloning thread, I couldn't find any definition of them (nor any claim that they were clearly understood by anyone). At least, there was a positive result for me: I lost most of my initial interest in trying to understand them.

I've already stated long ago a few general criteria a rating system should satisfy:
- full compatibilty with the Sudoku symmetries;
- a set of well defined rules used as a backbone for a scale of complexity among which other rules would find their place in a way consistent with the possible views one can have on them (e.g. triplet vs whip[3]).
I think before any coding effort for a new rating system, the detailed principles of this new rating should be discussed (and maybe a specific thread opened for this: discussing code optimisations and discussing specifications is not the same thing).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: more on whips, braids, T&E...

Postby ronk » Sat Apr 16, 2011 6:00 am

denis_berthier wrote:As for the techniques SE uses in the puzzles rated above ~8 (which was the main question raised by my post), I'd like to believe I'm the only one that doesn't understand what all its types of "forcing chains" are (this is what is at stakes in the 8-12 range). But I fear I'm not. Even after scanning the whole SE cloning thread, I couldn't find any definition of them (nor any claim that they were clearly understood by anyone). At least, there was a positive result for me: I lost most of my initial interest in trying to understand them.

I don't think the "SE cloning thread", as a thread, ever got as far along as the "forcing chains", so how you can comment about what anyone there understands is beyond me.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques