The New Sudoku Players' Forum

[1to9only]

I also looked at the ED=11.9/11.9/11.8 puzzle in champagne's list of hardest sudokus:

Code: Select all

98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2. ED=11.9/11.9/11.8 GP;champagne dry;1;22;


The first 6 SE solving steps are below (subsequent steps are 11.4/11.5 and lower):

Code: Select all

98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2. 11.8, Contradiction Forcing Chain: R9C5.4 on ==> R6C4.6 both on & off: -4r9c5
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2. 11.8, Contradiction Forcing Chain: R6C4.8 on ==> R4C5.6 both on & off: -8r6c4
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2. 11.9, Contradiction Forcing Chain: R5C5.6 on ==> R4C5.8 both on & off: -6r5c5
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2. 11.9, Contradiction Forcing Chain: R6C8.4 on ==> R8C7.8 both on & off: -4r6c8
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2. 11.9, Contradiction Forcing Chain: R2C5.4 on ==> R5C6.4 both on & off: -4r2c5
98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2. 11.9, Contradiction Forcing Chain: R6C7.8 on ==> R1C6.6 both on & off: -8r6c7


SE is running in NestedForcingChain code, at level=4, nestingLimit=0, thus the SER is at least 10.5:

Code: Select all

difficulty = 8.5 + 0.5 * level;


To the difficulty value a chain complexity (length!) value is added, as from this table:

Code: Select all

chain, value
192,   1.2
256,   1.3
384,   1.4
512,   1.5
768,   1.6
1024,  1.7


For the 6 solving steps above, the chain complexity value and SER value to be added are below:

Code: Select all

chain, value
l=364, add=1.3
l=378, add=1.3
l=398, add=1.4
l=434, add=1.4
l=467, add=1.4
l=446, add=1.4


For an SER=12.0 puzzle, the complexity value must be at least 514, as l is calculated as follows:

Code: Select all

length = getComplexity() - 2;


The l=512, add 1.5 is not very far off...

[mith]

For comparison, the 12.7 chain would be somewhere between 6144 and 8192 for length. 512 isn't really even that big, in that context. (And the 11.7 +MFC would be between 1024 and 1536. This may be the most complex chain actually used by SE?)

1to9, do you know how the complexity is calculated? One of these days I'll get around to reading the code...

[1to9only]

Code: Select all

public int getComplexity() {
    return getFlatComplexity() + getNestedComplexity();
}


I think dobrichev mentioned these in an earlier post, but no - I have not looked into the 2 components that make up the complexity value. Maybe on a rainy day, when I have nothing much to do!!

[Pupp]

My post was more directed at Pupp.

But yeah, in a 11.9 puzzle there could be eliminations rated harder than 11.9. (I have not actually stepped through any of the 11.9s to see if that's the case. I don't remember off the top of my head which puzzle I was looking at when I saw the 12.6 - one of mine, I assume. I do remember that SE froze on me when I tried to show it on the GUI.)

There seems to be techniques that humans can use that can make it "easier", or at least faster, that a solver would not use unless it was the only option. Solvers, I would think, are programmed to use the least difficult techniques first. "Easier" means using a more difficult technique to seriously shorten the puzzle as a whole. So it's "easier" in human terms, where "easier" means less steps to get to the finish line.

[denis_berthier]

I guess we can always make things more complicated than they need be. At least, it shows that SER has the capability of rating higher than 12.

But my original question was about the strict SER rating (for a real Sudoku puzzle), as it has been used here for decades (and I don't think either it's a good idea to change the techniques involved; that could only introduce confusion). SER is largely arbitrary, but any other set of techniques will be also. Millions of puzzles have been rated by SER and all this work would be lost if any changes were made.

As has been pointed out, there's no (known) intrinsic reason, neither because of SER nor because of Sudoku, why a SER 12.0 couldn't be found. We've observed that as SER increases above 11, the number of puzzles decreases drastically and there are only few 11.9 (after years of intensive search by proximity search). Chances of finding a 12.0 by the same technique seem to be very thin, but who knows?

The same applies to my BpB classification, as we know only 3 puzzles in B7B and nothing above.

[mith]

Pupp, you're not really understanding what we're talking about here.

The 11.9s are all the same "type" of technique (Dynamic Chains with Nested Dynamic Chains). So are the 12.0s. And 12.1s. etc. The only difference is in the complexity of the chains involved.

There are techniques not implemented by SE which, for some puzzles, can make the puzzle easier (in some cases much easier - see my "Potential Hardest" series for some examples, there are plenty more around). Humans can use those techniques. Solvers can too, if they are implemented, but since they are not implemented by SE they have no bearing on the rating of a puzzle by SE.

What an 11.9 rating means for a puzzle is that in order for SE to solve it, with the set of techniques it has available, it has to use Dynamic Chains with Nested Dynamic Chains, and that the most complex of these lies in a certain range (384-512, not sure which side is inclusive) as calculated by SE. A 12.0+ would mean exactly the same thing, except that the most complex chain was more complex than that. These don't really mean anything to a human solver - no one is going to solve a puzzle by going through 300+ pages worth of steps to arrive at an elimination! It's only a benchmark, and obviously not the only one.

FWIW, I found another 11.8 tonight. Maybe I keep running my scripts long enough, the magic will happen...

[1to9only]

If you plug the ED=119.119.118 puzzle into the SudokuExplainer-HoDoku hybrid I mentioned here, the first solving step it displays is a 12.2 nested dynamic chain.

[denis_berthier]

If you plug the ED=119.119.118 puzzle into the SudokuExplainer-HoDoku hybrid I mentioned here, the first solving step it displays is a 12.2 nested dynamic chain.

Changing the thermometer doesn't change the temperature. This puzzle has SER 11.9.
I don't know what this mixed software does precisely. It could be worth checking the SERs of all this puzzle isomorphs, but that's too long computations.

[mith]

Now I'm curious. I'll run it for 100 isomorphs and see what happens.

A quick check with skfr shows some variance - minlex is 11.8/11.8/11.7, but I also have EDs of 11.8, 11.5, and 11.2(??); one with ER/EP at 11.9 (also with ED 11.2). Really curious why it would have this kind of variation, based on what (little) I know about the code. Really strange.

It'll take a while to run serate on these.

[denis_berthier]

Now I'm curious. I'll run it for 100 isomorphs and see what happens.
A quick check with skfr shows some variance - minlex is 11.8/11.8/11.7, but I also have EDs of 11.8, 11.5, and 11.2(??); one with ER/EP at 11.9 (also with ED 11.2). Really curious why it would have this kind of variation, based on what (little) I know about the code. Really strange.
It'll take a while to run serate on these.

It is well known that SER is not stable under isomorphisms. And there's no reason why it should be: the set of "rules" that define each level do not have the confluence property. The same is true of skfr.
The only approach I know of that can guarantee invariance is mine, with the braid, g-braid, S-braid or Bp-braid resolution theories.

[Added] Don't forget the permutations of digits. They can also lead to different results.

[coloin]

..... one with ER/EP at 11.9

maybe plug that one in to SE 1.2 and maybe you will get a 12.0 !!!

Seriously though, I think the best person to comment on skfr - which essentially was a speeded up pseudo clone by Papa champagne - and he never ever defined it as a replacement.

Its not at all surprizing that our other rating programs are inconsistent over isomorphs, as they dont define the way they are solving - and hence the rating is different for isomorphs.
In the patterns game a different isomorhic ED rating is quite rightly disallowed by the referee

A human solver usually doesnt have a rigid method / order of solving [above simple methods] ....

suexratt - takes a good number of isomorphic variations of a puzzle and averages [actually a high centile] the number of nodes/guesses
-q2 - not sure how the number is generated !!! it does suffer some ... but not that much variation eg

Code: Select all

..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5.. # 98434 FNBP C22.m/M2.1.85293   SKFR  ED=10.8/10.8/2.6  ED=11.0
.74.6..3....9.......5..2...........4.46.8.3..1.......8.68.7...3......6..5..6..7.. # 98426 FNBP C22.m/M2.1.85293   SKFR  ED=10.8/10.8/2.6  ED=   
......9...74.3...6..5....2......4....463....81....8......6......68..3..75..7..6.. # 98433 FNBP C22.m/M2.1.85293   SKFR  ED=10.8/10.8/2.6  ED=   
.74..3..6......9....5....2....6......68.3...75..7..6......4.....463....81...8.... # 98433 FNBP C22.m/M2.1.85293   SKFR  ED=10.8/10.8/2.6  ED=   
...9......47.6...3.5...2.........6...86.7..3.5..6..7.........4.1......8..64.8.3.. # 98426 FNBP C22.m/M2.1.85293   SKFR  ED=10.8/10.8/2.6  ED=   


Its good that Denis's resolution theory is consistent with isomorphic puzzles ....

[denis_berthier]

Its good that Denis's resolution theory is consistent with isomorphic puzzles ....

But it has a high computational cost.
Braid resolution theories are much more computationally costly than the corresponding whip resolution theories. (Fortunately, the approximation of braids by whips is very good.)

[mith]

I ran that one and a set of 15 others, all 11.9/11.9/11.8. Not surprising, but

q2 does an average as well, I think. But even using isomorphs generated by the same program, q2 can vary quite a bit - for champagne dry, it landed on three different values for the 100 I tested (95249, 95247, 95239), but for my 11.8 pearl it hit a large range of values from 98001 to 98047.

I understand why q2 would have variance like that; I'm not sure I understand yet why SE does, though. The same complexity chains should be available regardless of the morph. I have a couple puzzles I know have different SE ratings, so I'll have to step through them and see what it's doing differently.

[denis_berthier]

I understand why q2 would have variance like that; I'm not sure I understand yet why SE does, though. The same complexity chains should be available regardless of the morph. I have a couple puzzles I know have different SE ratings, so I'll have to step through them and see what it's doing differently.

The reason is quite simple. IN two different morphs, rules are applied in different orders. That's where non confluence can make a rule that was applicable in the original puzzle impossible to apply in the morph.

[Edit:] The rules I use are different from those of SER, but in PBCS, there is a detailed example of non-confluence and how it can happen.

[denis_berthier]

SE finally unfroze after I clicked on the last hint, heh. 12.7, with a ridiculous 313 "views" (chains and nested chains). I pasted the explainer text into office, it's 331 pages.

I'm not too surprised. It's basically T&E at depth 2. I've never counted the number of pages at depth 2, but it's around 20 at depth one and it increases as the power of depth.