The New Sudoku Players' Forum

[ravel]

Have updated the list now with the new hard puzzles from Oceans symmetrical list there.
(Line nr/steps)
13/5(9.0), 16/4(9.0), 18/6(9.0), 21/6(9.3), 22/4(9.1), 23/4(9.1), 29/4(9.7), 34/7(9.4), 40/5(9.2), 41/4(9.2), 42/6(9.0), 43/6(9.3), 49/9(9.6)
Already in the list were 2/4, 28/5, 33/15(9.8)
So we have 16 symmetrical puzzles with 20 clues in the list now.

PS: I noticed, that 7 of the puzzles are not minimal, but in all cases the number that can be dropped is a single (in the middle box).

[Ocean]

So we have 16 symmetrical puzzles with 20 clues in the list now.

Thanks for doing this time-consuming task.

Except observing that Explainer rating is 9 or above for those with many steps, I can not see a strong correlation between the two measures.

Hopefully there is now a bit more diversified material for those who want to analyze the puzzles or patterns in more detail. To what extent does the step count or rating tell something about the "real difficulty"? How can we find new hard ones? Is it possible to "learn" how to solve hard puzzles?

[beetjepeetje]

Hi,
I thought to find hard-to-do puzzles here.
But the first '7 steps' sudoku solves in 3 'hierarchy' levels and you have to go through 7 'hierachy' levels to check the solution is unique

How many steps do you give this one:

Code: Select all

...|1..|.3.
2..|6..|.9.
.1.|.32|6..
---+---+---
.47|...|.6.
1..|...|..7
.8.|..9|...
---+---+---
.9.|.18|.5.
3..|4..|.7.
4..|...|...

(I presented this one in a Dutch web site too, but no one responded until now..)

[RW]

How many steps do you give this one:

Solves with a x-wing. Isn't even close to the same league as the puzzles on the list. Even if ravel doesn't have the x-wing implemented then it would be max 1 step.

[daj95376]

This one caused my solver to generate an obscure solution. Anyone find it difficult? If so, then it has friends.

Code: Select all

6.9.5.7...2.9..........4..8..75.9..42.......99..3.68..3..4..........5.6...2.8.9.7


[ravel]

Daj, it solved with 3 steps, e.g.
r3c4<>6, r8c5<>3, r8c7<>4
r9c4<>1, r9c8<>3, r8c7<>4

[Karlson]

This one caused my solver to generate an obscure solution. Anyone find it difficult? If so, then it has friends.

Code: Select all

6.9.5.7...2.9..........4..8..75.9..42.......99..3.68..3..4..........5.6...2.8.9.7


Although ravel's solver only needs 3 steps to solve it, Into Sudoku needs 6x guessing to solve it - the highest guessing count I ever saw in that program.

[ravel]

I suppose, that the number of guessings will change, when you take an equivalent ("scrambled") version of the puzzle (e.g. by exchanging bands/stacks, rows/columns within a band/stack or mirroring). At least this is one problem i have with my program.

[daj95376]

Karlson, Thank You for the cross-check with Into Sudoku!!! It sounds like what my solver encountered.

Ravel, thanks for explaining how you obtain your results. It makes a lot of sense to me. Sometimes, I will re-compile my solver and have it scan cells in reverse order. I'm often amazed at how much the solution changes with that simple little action. With all the mappings you described, I understand why there was such a difference in our results. Thank You for running a cross-check and providing feedback!

[ravel]

Today i saw that Nicolas Juillerat had sent me an email 2 weeks ago, which i want to quote here:

I followed this thread with interest. There's a few things I can answer
about the Explainer.

One question was the reason why the Explainer does not always find the
shortest chain (the post of Viggo on 21 Apr). I have found a few reasons for
this.

The first reason is only due to the internal representation of chains in the
Explainer, which differs from the notation used in this forum. I think this
was correctly explained by Viggo on his next posts so I have nothing to add.

Another reason is simply a bug I recently found in my program :-p When an
implication chain consists of multiple sub-pathes, the Explainer counts all
links in all sub-pathes for the final rating (and the same link is counted
twice if it occurs in both views). But in the algorithm I use to search for
the shortest chains, the length is only based on the longest sub-chain...
In other words, the explainer searches shortest forcing chains according to
the longest sub-chain only but then classifies the results according to all
sub-chains. I don't know how much this can affect the ratings but this
*will* affect them in some cases. If I can find some time I'll try to fix
this incoherency for the next version.

I have not found bugs other than the above one yet but my code is quite
messy so I cannot exclude a few other bugs which can affect the results.

Another question was about the meaning of the solving techniques used by the
Explainer. Your answer was correct. Regarding "Dynamic Forcing Chain (+)",
these are chains in which at least a hidden pair, naked pair or intersection
is used within the chain. I don't know exactly how this relates to ALS. In
"Dynamic Forcing Chain (++)" (rated 9.5-10.5), I also include hidden/naked
pairs/triplets, swordfish and jellyfish. I'm not aware of any puzzle that
absolutely requires this.

Note that the explainer does not include these two last techniques with the
"get all hints" button (I took this choice because they are very rarely
necessary, and slow to find). You have to use the "get next hint" button
after "get all hints" to get them.

Also note that the explainer first searches all chains in a given category
before it starts with the next one. As a result it will for example find a
very long cell forcing chain rated 8.9 before a short dynamic forcing chain
rated 8.6. I agree this is not very smart for the rating, but my initial
interest was to test whether a given puzzle requires or not a specific kind
of chains.

The question about the stability of ratings under symmetries and rotations
was interesting but I don't have real answers. What I know is that at a
given step of the solving process, it is frequent that there are many
patterns with exactly the same difficulty. Choosing one or another can
completely change the solving path of the explainer. A rotation or symmetry
will change the choice of the explainer in these cases, and hence the whole
solving path. I don't know how much this can affect the overall rating of
the puzzle, but it seems to be stable most of the time. An obvious exception
is when unique loops and BUGs are involved because I didn't implement them
in a stable way; but the example posted by r.e.s. still has different
ratings (8.5/8.6) if I deactivate these techniques Maybe another bug in
my code, or simply a property of sudoku, I don't know yet.

Hope I've answered to most questions about the explainer...

Cheers,

Nicolas

[ravel]

Much has happened since i have started this thread with 123 toughies. In the meantime there are 199 and the 7 hardest in the list are new ones created by Ocean and tso.

It turned out that also the programs with most advanced pattern methods (including xy-chains, AIC and ALS) implemented can only solve a few ones in the list, where my rather simple error net method solves them all - with the disadvantage that the solution is hardly readable.
The best on the program side in the moment seems to be the Sudoku Explainer, the best on the human side maria45, who solved 4 of the toughies manually, including the hardest one.
The rating (now in combination with Explainers rating) turned out to be rather good. It was intended to reflect, how hard the puzzle is for humans and when i look at the manual solutions, they are shorter for the lower step puzzles.

The diagonal pattern seems to hold the most toughies.

Characteristic for the hard sudokus is that from beginning hardly a number can be placed without using multiple long chains. Since it is impossible for humans (and most programs) to foresee, what eliminations are possible and which of them will proceed the puzzle most, the T&E factor is much higher than for "normal difficult" puzzles: Try to make any elimination you can and look, where it leads to afterwards. When you need 10 hard steps to place the first number and you dont know, if the 10th is possible, you have to try.

Characteristic for a hard step is, that with any wrong number you either run into a situation where you are stuck again or there is an "almost" solution where you can set 50 numbers before you finally get a contradiction. In the moment no methods are available for a shortcut for these steps and i dont believe that there will come some, which provide short and easy readable steps (that at least eliminate one number): The problem is, that such a step needs to look at a lot of cells and candidates, which gives it a complexity, that hardly can be simplified.
But of course many optimizations are possible and also much better presentations of solutions.

Solving a toughie is a combination of solving a lot of hard sudukos. Each of up to 250 candidates leaves you with a hard one - either with or without a unique solution.

[maria45]

And we have a new leader !
No 7 is a very extreme puzzle. Though one guess (r1c2=4) could solve the puzzle with singles, it needed 12 steps.

The puzzle have 4 candidates in r1c2 and it can be solved by one guess (r1c2=4). Then this puzzle can be solved in 3 steps. The 3 steps are to eliminate the other three candidates in this cell.

Have I missed some point here?

Hm, why can nothing ever be easy..., but here is a solution:

Code: Select all

143: tso #7/31 (9.4)
   1 2 3   4 5 6   7 8 9

 +-------+-------+-------+
a| . . . | 5 . . | 7 . . |
b| . 2 . | . 6 . | . 4 . |
c| . . 6 | . . 1 | . . 3 |
 +-------+-------+-------+
d| 9 . . | 2 . . | 4 . . |
e| . 3 . | . . . | . 1 . |
f| . . 7 | . . 3 | . . 8 |
 +-------+-------+-------+
g| 1 . . | 7 . . | 6 . . |
h| . 5 . | . 4 . | . 7 . |
k| . . 9 | . . 8 | . . . |
 +-------+-------+-------+


1. d8=3 (that's still easy)

2. k2=4, (g2=8, df2=16, a2=9, c2=7, gh3=23, k1=7, h1=6, k4=6, g9=4, h7=8, k7=3, b7=1, a3=1, b6=7, e3=4, f4=4, a6=4, c1=4, h4=1, k9=1, g5=3, b4=3, b13=58, b9=9, h9=2, k5=2, box2!=2 contradiction >) k2!=4

3. g9=4, (g2=8, k1=4, k2=7, h1=6, k4=6, gh3=23, h7=8, k4=6, k7=3, b7=1

3a. d6=6, f2=6 or e6=6, a6=4, c2=4 > f2!=4, f4=4, a6=4, c2=4, a2=9, e3=4, h4=1, k9=1, h3=3, g3=2, g5=3, b4=3, ac5=2, k5=5, k8=2, a3=1, g6=9, h9=9, row2!=9 contradiction >) g9!=4, k9=4

4. e6=7, (b6=9, c5=7, b1=7, k2=7, a6=4, a5=2, c4=8, b4=3, d9=7, cef7=259, hk1=6

4a. c2=4 or c2=9, c78=25, b9=1,b7=8, g8=8, g2=4 > f2!=4

4b. g2=8 or g2=4, c2=9, c1=4, b3=5, e3=4, f4=4, c78=25, b7=8, g8=8, ck8=25, f8=69, d56=5, f258=169, cf7=25, e7=9, f5=9, h4=9, e4=6, k4=1, h6=6, d2=6 > d2!=8, df2=16

4c. g6=5, k8=5, k1=2 or g6=2, h6=6, k1=6 > k1!=3

4d. k4=6 or k4=1, k7=3, k5=5, g6=2, h6=6 > h4!=6

4e. k4=1, k7=3 or k4=6, k1=2, e3=2, g3=4, g2=8, h3=3, k7=3 > k7=3, g5=3, h4=9

4f. h1=6 or k1=6, k8=2, h9=1, h7=8, b3=8, a3=3 > h1=26, h3=3, a1=3, e1=8, d3=5, e3=2, e4=4, e9=6, h7=8, a8=6, box3!=8 >) e6!=7

5. c2=4, (a6=4, g2=8, a2=9, k2=7, g3=4, h7=8, k7=3, b7=1, a3=1, h9=1, h46=9, g5=3, b4=3, a1=3, h3=3, hk1=26, e3=2, ac5=2, b13=8

5a. f1=5, d3=8 or f1=4, e4=4, c4=8, a8=8, f8=6, d2=6, d69=57, d3=8 > d3=8, b3=5, b9=9, b6=7, g8=9

5b. a8=6, a5=8, e4=8 or f8=6, d2=6, d5=1, e5=7, e4=8 > e4=8, c4=9, h4=6, f4=4, h6=9, f1=5, k4=1, k5=5, k8=2, g9=5, e7=5, c7=2, box6!=2 >) c2!=4

6. f2=4, (g2=8, g3=4, h7=8, k7=3, b7=1, h9=1, g5=3, b4=3, d23=1, fhk4=169, b13=8

6a. d3=8 or d5=8, c4=8, a6=4, a1=3, a3=1 > d3!=1, d2=1, a2=9, c2=7, k2=6, a3=1, b6=7, k4=1, f5=1, a1=3, c1=4, a6=4, c4=8, a5=2, c5=9, k5=5, k8=2, e9=2, f1=2, h3=2, col3!=3 >) f2!=4

7. g3=8, (g2=4, h7=8, k7=3, h9=1, b7=1, g5=3, b4=3, b3=5, d3=1, f2=6, d2=8, k2=7, c2=9, b9=9, g8=9, b6=7, b1=8, c1=7, c4=4, e6=4, e4=8, e3=2, a8=6, a9=2, k8=2, a6=9, k1=6, k4=1, f4=9, box8!=9 >) g3!=8

8. g2=4, g8=8 or a2=4, c4=4, e6=4, f1=4, g3=4, g2=8, h7=8, k7=3, b7=1, h9=1, df2=16, k2=7, c2=9, a3=1, g5=3, b4=3, a1=3, h3=3, e3=2, e4=8, e1=5, d3=8, b3=5, b9=9, g8=9 > g8=89

9. g2=4, g8=8 or a2=4, c4=4, e6=4, f1=4, g3=4, g2=8, h7=8, k7=3, b7=1, h9=1, df2=16, k2=7, c2=9, a3=1, g5=3, b4=3, a1=3, h3=3, e3=2, e4=8, e1=5, d3=8, b3=5, b9=9, g8=9, b6=7, b1=8, c1=7, e7=9, e5=7, e9=6, a9=2, g9=5, d9=7, a6=9, a5=8 > a8!=8

10. a2=1, (g2=4, f2=6, d2=8, k2=7, c2=9, d3=1, g8=8, ck8=25, f8=9, a8=6, ef7=25, c7=8, c4=4, e6=4, f4=1, f5=5, row4!=5 contradiction >) a2!=1, ab3=1

11. a3=4, (c4=4, e6=4, f1=4, g2=4, g8=8, b3=1, a9=1, hk7=13, de9=67, ab1=3, de3=5, f78=2, gh9=9, b9=5, k8=5, a8=6, c1=5, a56=2

11a. b1=7, b6=9, a2=9 or k1=7, ab1=38, a2=9 > a2=9, a6=2

11b. b6=7, c2=7, k1=7 or b6=9, h6=6, k1=6 > k1!=2, k5=2, k12=67

11c. b6=7, c2=7, k2=6, e1=6 or b6=9, d6=7, d9=6, b7=8, b4=3, k4=1, fh4=69, e4=8, e9=7, e1=6 > e1=6, d9=6, f4=6, e3=2, g3=3, g9=2, h9=9, hk47=13 nonunique contradiction or k1=7, b6=7, d6=5, box4!=5 contradiction >) a3!=4

12. c1=4 or c4=4, e6=4, f1=4, a2=4, g3=4, g2=8, h7=8, k7=3, b7=1, h9=1, df2=16, k2=7, c2=9, a3=1, g5=3, b4=3, a1=3, h3=3, e3=2, e4=8, e1=5, d3=8, b3=5, b9=9, g8=9, b6=7, b1=8, c1=7 > c1=47, b13=5

13. a6=4 or c4=4, e6=4, f1=4, a2=4, g3=4, c1=7, b6=7, g2=8, g8=9, g5=3, b4=3, k2=7, c2=9, h7=8, k7=3, b7=1, b9=9, e4=8, d3=8, b1=8, a5=8, a6=9 > a6!=2, ac5=2

14. e3=4 or g3=4, g2=8, h7=8, k7=3, b7=1, a3=1, g5=3, b4=3, a1=3, h3=3, e3=2 > e3=24

15. f4=4 or f1=4, a2=4, c4=4 > e4!=4

16. f1=4 or f4=4, a6=4, c1=4 > e1!=4

17. f4=4 or f1=4, a2=4, g2=8, h7=8, g8=9, c2=9, c1=7, k2=7, g3=4, e3=2, h3=3, g5=3, b4=3, a6=9, h4=9, c4=4, e4=8, d3=8, e1=5, e7=9, f5=9, e5=7, d9=7, b9=9, g9=5, k5=5, k4=1, f4=6 > f4=46, hk4=1

18. c1=4 or c4=4, f1=4 > a1!=4

19. b4=3 or a5=3, c5=2, b6=7, a1=8, a3=1, k5=5, g5=9, f5=1, f2=6, k2=7, c2=9, b4=9 > b4!=8

20. a5=3, (b4=9, a6=4, c5=2, b6=7, c4=8, a1=8, b3=3, d3=5, d6=6, e4=nil contradiction >) a5!=3, b4=3

21. b6=7 or b6=9, a6=4, c4=8, f4=4, e3=4, gh3=2, k78=2, a5=2, e9=2, d9=7 > d6!=7, b6=7, b79=9

22. b9=1 or b9=9, g9k8=25, h9=1 > a9!=1, a3=1, b13=58, a1=3, a5=8, c5=2, e4=8, bd3=58

23. g4=8, h7=8, k7=3, h9=1, k4=1 or g4=4, g8=8, c8=5, k8=2, k12=67, k4=1 > k4=1, k12=67

24. g8=9, h7=8, k7=3 or g8=8, f8=9, ef7=25, k7=3 > k7=3, k5=5, k8=2, a8=6, a9=2, g9=5, de9=67, g5=3, h3=3, ef5=9

25. c8=8, g2=8, d3=8 or c8=5, f8=9, f5=1, d2=1, d3=8 > d3=8, and then it becomes easy again.

Strategically, I tried to do something like that, eliminate the other values around a2=4, but the thing wouldn't bend. And when I was at last ready to have the alternative of a2=4 or g2=4, and I could prove that g2=4 leads to contradiction, I was too proud and looked for a way to circumvent further contradictions, since I still believe that the "hardness" of a sudoku consists of how many contradictions I am forced to use.

Perhaps the last contradiction step 20 wasn't really necessary, but then I wanted to get it done and it was such a beautiful short contradiction, with so many numbers still missing. So 8 contradictions, may be 9, needed, ranks this puzzle quite hard, compared with Ocean's BB with 7 contradictions.

Another idea of the "hardness" of the contradictions used is to count the number of substeps. Step 4 is clearly standing out with 6 substeps needed. Perhaps there are some easier ways to solution, but as I said, I tried this strategy.

Greetings, Maria

[ravel]

Out of 89 solutions with maximum 18 (single number elimination) steps that my program found for that puzzle, only one (with 14 steps) used the backdoor cell r1c2 to solve it (eliminated the 3 candidates there).
So i think you probably would have found a shorter solution without using that hint.

[maria45]

Hello Ravel,

I don't know how those solvers like yours or the Explainer work, but perhaps a more "objective" rating could be achieved, if each path to solution would be checked? The shortest path would then give the rating, and that should hold true even if puzzle are rotated or scrambled. To check a puzzle so thoroughly, you need not check each of myriad pathways. If you have already a solution, you can cut all paths with longer solutions. Do you check for double paths resulting in the same constellation, too? Like in chess programs, you could build a signature like a hash of the puzzle and simply check if the signature already exists in memory. That would be memory consuming, but not time consuming.

Greetings, Maria

[ravel]

Hi Maria,

i described here in this thread, how my program works and you can read some posts above, what Nicolas said about the Explainer.

I also thought, that the shortest (overall) path to a solution would give a good rating, but i am pretty far from being able to find it for a toughie, even with the very restrictive condition, that only single eliminations by error nets using basic methods are allowed.
The first big problem is to find all promising orders of eliminations that solve the puzzle. My program does it in a very sloppy way (and therefore gives different results for scrambled puzzles), but still needs an hour for one of the hardest sudokus. And i dont even have implemented to determine redundant eliminations (note that dropping one chain might be possible, if a longer chain is calculated for another elimination).
The second problem then is to find the shortest error net for a given elimination. This is all but trivial also if you dont allow "subchains". Also here a first step would be to determine unnecessary implications in a given net to a contradiction, which alone is not easy, because there can be different sub error nets, where an implication is necessary for the one, but redundant for the other.
But you know, that you can prove a given elimination using (sometimes very) different contradictions.

So finding optimal solutions is that complex, that i think it would need the interest people have in chess programs, that someone would take the effort to write a program, which could satisfy most of us.