## Solution to Ocean's #07/18

Advanced methods and approaches for solving Sudoku puzzles

### Solution to Ocean's #07/18

Code: Select all
`174: Ocean #7/18 (9.9)   1 2 3   4 5 6   7 8 9 +-------+-------+-------+a| . . 1 | . . 2 | . . 3 |b| . 2 . | . 4 . | . 1 . |c| 5 . . | 6 . . | . . . | +-------+-------+-------+d| . . . | . . 7 | . . 1 |e| . 3 . | . 8 . | . 2 . |f| 4 . . | 5 . . | 6 . . | +-------+-------+-------+g| . . 5 | . . 9 | . . 2 |h| . 7 . | . . . | . 8 . |k| 3 . . | . . . | 9 . . | +-------+-------+-------+`
1. c7=2, d2=5 (trivial)

2. h1=1, g7=1, f2=1, h3=9, k3=2, c3=4, d1=2, f5=2, h4=2, f6=3, e1=9, b3=3, c5=3, c6=1, e4=1, k5=1, g4=3, h7=3, d8=3, cf8=79, k9=7, g5=7, k46=8, c8=7, f8=9, f9=8, c9=9, c2=8, a2=9, g1=8, b4=9, d4=4, d7=8, d3=6, e3=7, box6!=7 contradiction > h1!=1

3. e1=1, ghk4=1 or f2=1, g1=1, h7=1 > g5h56!=1

4. f5=2 or f3=2, h1=2 > h5!=2

5. k5=2, (d4=2, f3=2, h1=2, h3=9, e13=7, e46=4, e7=5, e9=9, df5=9, ab7c9=478, c8=9

5a. k3=4 or c3=4, a7=4, d8=4, c2=8, c9=7, f8=7, g7=7, k4=7, b7=8, a4=8, k6=8, k3=6, k8=5, k9=4 > k3!=8, k2468!=4

5b. b4=9, ghk4=3 or b1=9, f2=9, e1=1, e4=4, h6=4, h47=13 > h56!=3, h47=13

5c. h5=5 or a5=5, b9=5 > h9!=5, h56=5

5d. e4=4, h6=4 or e6=4, h56=56 , k6!=6, h6=6 > h6!=5 > h5=5, a5=7, a8=5, k9=5, b9=6, h9=4, a7=4, g4=4, k3=4, k4=7, h6=6, k6=8, d5=6, d3=8, c2=4, c9=8, box6!=8 >) k5!=2, hk4=2, d4!=2

6. f5=2 or d5=2, (f3=2, h1=2, h3=9, k4=2, e13=7, e6=6, de4=4, e3=7

6a. c3=4, (c56=13, c89=7, abe7=458, d7=3, f9=8, f8=7, c8=9, e9=9, e1=1, cf56=13 non-unique contradiction >) k3=4, h6=4, h9k89=567, h47=13, k89=7, ab7=7, c5=7, c6=1, f6=3, g4=7, k6=8, b6=5, a5=9) f5=1 > f5=12

7. k6=1, (f6=3, c6=8, b6=5, c5=1, e4=1, b4=3, c3=3, c89=7, b7=8, f9=8, a45=79, f5=2, bef3=679, h1=9, e13f3=679, c2=9, b9=9, c89=47, h34=24, a8=6, k8=5, h6=6, h9=nil contradiction >) k6!=1

8. d5=3, (f6=1, c5=1, f8=3, gh7=13, a5=9, b6=5, e6=6, e1=1, d48=49, d7=8, b7=7, a4=7, column1!=7 contradiction >) d5!=3

9. f6=3 or d4=3, f6=1, c5=1, bc6=3 > h6!=3

10. g4=3, (h7=3, f6=3, c5=3, d8=3, b3=3, g7=1, k2=1, h4=1, c6=1, f5=1, e1=1, d5=2, f3=2, h1=2, k4=2, h3=9, e3=7, e6=6, k6=8, b6=5, h6=4, a5=9, b19=69, a1=7, b4=7, column7!=7 contradiction >) g4!=3

11. f3=2, (d5=2, h1=2, k4=2, f5=1, k2=1, e1=1, c6=1, f6=3, e6=6, de4=49, h3=9, e3=7

11a. k3=4 or c3=4, c5=3, h4=3, g4=1, k6=8 > k3!=8, k6=8, h6=4, b6=5

11b. b4=3 or b3=3, b47=78, a1=7, a4=8, b4=7 > b4!=8, a4=8

11c. f8=7 or f8=9, f2=8, d7=8, b7=7 > ac8!=7

11d. g4=7 or b4=7, c9=7, f8=7, g7=7 > g58!=7

11e. b7=8, f9=8, f8=7 or b7=7, b4=3, c3=3, k3=4, g12=68, g5=3, g8=4, c8=9, f8=7 > f8=7

11f. b7=7 or b7=8, f9=8, f2=9, ab1=79, a15=79, g7=7, b4=7, c9=7 > a7!=7, b9!=7, ae7=45, h47=13, g47=17, x-wing bg47=7, b1!=7, a1=7, a5=9

11g. c3=4 or k3=4, g8=4 > c8!=4, c8=9, b1=9, f2=9, e9=9, f9=8, d7=3, d8=4, k9=4, a7=4, g2=4, c3=4, h7=1, k3=6, k8=5, box3!=5 contradiction >) f3!=2, f5=2 (the hardest step by far)

12. h7=4, abe7=578, d7=3, f6=3, g7=1, k2=1, row6!=1 > h7!=4

13. c5=3, (b3=3, h4=3, f6=3, h7=1, c6=1, h13=29, k4=2, e4=1, k5=1, f2=1, g1=1, d45=9, g45=7, ac2=9

13a. h5=5 or a5=5, k8=5 > k6!=5, h9!=5

13b. k3=4 or c3=4, c89=7, e7=7, f8=9, f9=8, c2=8, k3=8, g4=8, b6=8, h6=5, k6=4 > k289!=4, k3!=6

13c. h5=6 or h5=5, b6=5, k6=8 > k6!=6, k36=48, k2=6

13d. k3=4 or c3=4, c89=7, e7=7, e9=5, e6=4 > k6!=4, k6=8, k3=4, b6=5, h5=5, g2=8

13e. d4=9, b47=78, b1=6 or d4=4, g4=7, g5=6, h9=6, b1=6 > b1=6, a8=6, h9=6, h6=4, g4=7, d4=4, a5=7, c3=7, e1=7, b7=7, a7=5, e9=5, k8=5, a2=4, c2=9, f8=7, column8!=9 contradiction >) c5!=3, gh5=3, h4!=3

14. k5=1, (c6=1, e4=1, f2=1, g1=1, h7=1, f6=3, b4=3, c3=3, h5=3, a5=5, k8=5, h6=5, b6=8, d45=9, ac2=9, b13=67, b7=5, b9=9, f8=9, a8=6, e9=5, c9=8, f9=7, e7=4, e6=6, k6=4, h4=2, k3=2, d1=2, g5=6, k2=6, d4=4, a7=7, c8=4, h9=4, row8!=6 contradiction >) k5!=1, c5=1, ef6=1, e4!=1

15. e1=1 or e6=1, f2=1, g1=1, h7=1, k4=1, h4=2, k3=2, d1=2, f6=3, h5=3, b4=3, c3=3, c6=8, g4=8, k3=8, b6=5, k5=5, h9=5, a8=5, e7=5, d5=6, a4=7, g5=7, b7=7, box1!=7 contradiction > e1=1, f6=1, d4=3, f8=3ef3=7, c89=7, abd7=458, e7=7, f3=7, e9=5, gh7=13, k8=5

16. g1=6, a2=6, column8!=6 contradiction > g1=8 (very short and elegant),…
or with the same result: 16. g1=6 or g1=8, k6=8, c6=3, b6=5, a7=5, d7=4, d8=9, d5=6, e6=4, h6=6, k5=7, g8=7, g2=6 > g58!=6, a8=6, bf9=89, g12=6, g2=6, k2=1, hk3=4

17. f9=9, d8=4, g8=7 or f2=9, e3=6, d5=6, k5=7, g8=7 > g8=7, etc. trivial.

One could also use a sort of "back door" after step 5:
6. g5=3, (h7=3, g7=1, k2=1, e1=1, h4=1, k4=2, h13=29, ef3=7

6a. f3=2, e3=7 or f5=2, c5=1, c89=7, e7=7, f3=7 > f3=27, e9!=7

6b. k6=8, cf6=13, b6=5 or g4=8, g1=6, a2=6, b9=6, k8=6, a8=5, b6=5 > b6=5, eh6=46, k6=8 (2 numbers solved)

6c. e7=7, b7=8, a4=8 or e3=7, f3=2, f5=1, f6=3, c6=1, ac5=79, a4=8 > a4=8 (1 number solved)

6d. e7=7, b7=8, d7=4 or e3=7, f3=2, f5=1, f6=3, d8=3 > d8!=4

6e. e7=7, b7=8, d7=4, f9=8, f2=9 or e3=7, f3=2, h3=9 > de3!=9

6f. f6=1, f8=3, d8=9 or f5=1, ac5=79 > d5!=9, de4=9, b4!=9

6g. b4=7, g4=4, k3=4 or b4=3, c3=3, k3=4 > k3=4, g12=6, g8!=6, ak8=56 (2 numbers solved)

6h. e7=7, a7=5, a8=6 or a7=7, a5=9, a1=6 > a2!=6, g2=6, g1=8 (2 numbers solved)

6i. f2=9 or f2=8, d7=8, b7=7, a1=7, a5=9 > a2!=9, a2=4, de7=4, e9!=4 (1 number solved)

6j. a7=7, a5=9, a1=6 or e7=7, e3=6 > d1!=6, de3=6, b3!=6, dh1=29, a5=9 (2 numbers solved)

6k. f5=2, f6=1, f8=3 or f5=1, c5=7, g4=7, k9=7, f3=2, f8=7 > f8!=9, f29=89

6l. c2=9, b9=9 or f2=9 > f9!=9, f9=8, f2=9, c2=8, a7=8, d7=4, d1=2, h1=9, h3=2, f3=7, e3=6, d5=6, e6=4, e4=9, e9=5, e7=7, a7=5, a8=6, h6=6, h9=4, g8=7, k8=5, k9=6, h5=5, k5=7, g4=4, c5=1, c6=3, c3=9, b3=3, a1=7, b1=6, b4=7, b9=9, c9=7, c8=4, f8=3, d8=9, d3=8, d4=3, f5=2, f6=1 solution complete, no contradiction >) g5=3 (at last)

Well, I called it "back door" because the remaining steps are rather simple forcing chains. Perhaps there is another "break through"-step in 6a-6k, I didn't see it, so I had to painstakingly solve only one or two numbers at a time.

Thank you again for this wonderful puzzle, Ocean.

Kind regards, Maria
maria45

Posts: 54
Joined: 23 October 2005

### Re: Solution to Ocean's #07/18

Hi Maria!

Thanks for the solution! First manual solution of a puzzle (in this forum) with Explainer rating 9.9. Good work! I'm not able to check/verify your solution at the moment (will take some time), but am sure some of the experienced solvers around here can do it.
Ocean

Posts: 442
Joined: 29 August 2005

It lies in the nature of the hardest sudokus, that even reading the solutions is not easy - and you dont have the satisfaction of having solved it. I did it for two of Maria's solutions, but i need longer to find time and appetite for checking the next one, than she solves them. And - besides of typos and minor lapses (concerning the order or missing placements) or a minor improvement the two ones were very good. So probably i also cannot have the satisfaction of proving her wrong

Ocean, now when Maria eats all your toughies, cant you find new challenges for her ?
ravel

Posts: 998
Joined: 21 February 2006

Maria and Ocean, what a pleasure to suddenly discover work of this quality. It's indeed a wonderfully difficult puzzle, and I am studying this wonderful solution avidly.

So far I have got as far as the end of 5a. I thought 3 was quite ravishing. It's all beautifully clear; I'll ask for help if I get stuck.

Next morning : re 5b: help please! I see h56!=3, but I don't see how h47=13 follows in the case b4=9, ghk4=3. What happened to the 4s at h47? How did you get rid of them?
gurth

Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

### Re: Solution to Ocean's #07/18

ravel wrote:It lies in the nature of the hardest sudokus, that even reading the solutions is not easy

Agree - even though there is a big difference from finding solutions. I had a look at a few of Maria's deductions, and those I checked seemed fine. For the long chains, especially those with subchains, I will prefer to have (find or make) an appropriate tool to help with the checking.
ravel wrote:Ocean, now when Maria eats all your toughies, cant you find new challenges for her ?

OK - have tried to find some more. But hope everybody can help finding new hard ones. Test your ideas on Explainer! Experimenting with patterns where one box deviates from the diagonal pattern, resulted in eighteen puzzles with Explainer rating between 9.4 and 10.0. These are posted in the "hardest sudokus" thread .

[Edit: Corrected the number of posted puzzles, since the search continued for a while. Hope it's not too time-consuming for you to check them all, Ravel. The Explainer Rating 10.0 is probably a new "record" - provided that puzzle has enough steps. Maybe a suitable challenge for you, Maria?]
Last edited by Ocean on Tue Aug 15, 2006 2:51 pm, edited 1 time in total.
Ocean

Posts: 442
Joined: 29 August 2005

Hello gurth,

step 5b: well, if h56!=3, then you are left with a hidden pair (1,3) in row 8 at h47. Alternatively, as this seems for most people somehow easier to spot, look at the inverse relation of the hidden pair, the naked triple in h569=456. That eliminates the 4 in h47.

Greetings, Maria
maria45

Posts: 54
Joined: 23 October 2005

### Re: Solution to Ocean's #07/18

Ocean wrote:For the long chains, especially those with subchains, I will prefer to have (find or make) an appropriate tool to help with the checking.

Thats exactly, what i was thinking about yesterday (but i personally hate GUI programming). The first step would be to find a common text format, that is able to represent Carcul's and Maria's chains. Then a GUI could be written, where the chains easily can be entered (and copied) and which allows to go through them step by step with a graphical, colored representation (e.g. different colors for the branches of an error net getting darker from step to step or whatever).
ravel

Posts: 998
Joined: 21 February 2006

Thanks, Maria, for your speedy help. Much appreciated. I'll have to go home now and see if I can now spot the hidden pair on my computer. Stupid of me to miss that.
gurth

Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Hello Ocean & Ravel,

I'd like that graphical thing. How about using the sudoku explainer? I just downloaded it yesterday and it seems to do exactly some type of nice graphical output (although the size of the output window *could* be a bit larger). If the source code is available, one could certainly without much coding get an input form from Carculs and my chains. For the sake of convenience I would even consider switching my notation to something like chess with the numbers vertically and a-i horizontally or r1-9c1-9...

However, a stupid automatic conversion tool from "a1=6" to "r1c1=6" should not prove too hard...

btw, I double checked a deduction by contradiction with the sudoku explainer, and my deduction was way shorter (16 steps) than the explanier (73 steps). Perhaps this could be improved.

oh, btw, I remember ronk asking a question: "what is a step in a forcing chain?"
Basically, any deduction followed by a colon, e.g. the following chain consists of 14 steps and one conclusion:
3. a1=6, (b9=6, cf9=78, e1=1, h1=8, d1=3, b1=7, g3=7, k1=4, h3=1, g4=8, f4=1, f6=3, row6!=4 contradiction >) a1!=6

Greetings, Maria
maria45

Posts: 54
Joined: 23 October 2005

maria45 wrote:oh, btw, I remember ronk asking a question: "what is a step in a forcing chain?"
Basically, any deduction followed by a colon, e.g. the following chain ...

It was a facetious question ... because chains have links. You can't find the word "step" in the opening post of Forcing chains: Terminology and Definition.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Hello ronk,

thank you for trying to assist me in the use of correct terminology. However, having read the definitions, neither "link" nor "node" feels appropriate for the "steps" I am counting. Perhaps closest are the terms inference, deduction or implication. Basically I see the "steps" as the same steps a program would consider "single-step-execution" like "set variable x to value a" respectively in this context "consider cell rxcy containing candidate a".

You know, it is still not entirely clear if I am human (the reverse Turing-test)...

Regards, Maria

P.S. and of course some of my "forcing chains" would rather be termed "forcing net", "multiple implication net", "error net" etc. I really apologize for my "blue coat approach" in sudoku terms.
maria45

Posts: 54
Joined: 23 October 2005

Hi Maria,

The Sudoku Explainer is free, but not open source, so we cannot use it.

There are different things that could be done. The easiest i suppose is to write a parser for your and/or Carcul's chains and then let the program validate it. No GUI needed.

But of course i would like to have a graphical representation, where i easily could follow the chains and sub-chains, but this would be a lot of work, also when a sudoku user interface already is available. Could be a topic for the programmer's forum.

Viggo already had pointed out here, that shorter chains than the Explainer's can be found. You can read Nicolas' explanation for that here.
ravel

Posts: 998
Joined: 21 February 2006

MY LATTER-PART SOLUTION OF #7/18

I was happy to follow Maria's solution as far as the end of step 10. Then I saw that the "hardest step by far" was coming up. I must still study that.

Meanwhile I felt inclined to complete the puzzle my own "rational" way.
This is where my philosophy of sudoku seems to part company with that of others. But I don't plan to give in to what I consider irrational pressures.

Some people seem to think that the aim of sudoku is to "prove" a solution. (some even say, a unique solution). But that is nonsense : the aim is to FIND a solution, which we then know is unique. It needs no proof : its proof is self-evident once it is found. WE DO NOT HAVE TO SHOW THAT EVERY NON-SOLUTION IS A NON-SOLUTION.

By which I mean that, when we follow a technique of testing candidates and then eliminating them if a contradiction occurs, we are just as justified to ACCEPT them if they do NOT lead to a contradiction!!

BECAUSE IF WE HAVE AGREED THAT IT IS LEGITIMATE TO TEST A CERTAIN CANDIDATE, HOW CAN WE THEN CHOOSE TO REJECT THE ANSWER IF IT IS "TOO GOOD"? That is sheer lunacy, which I will not condone.

We really need to consider more carefully why it is that we post a solution anyway. No reader is interested to know WHAT the solution is, or what its PROOF is : as said above, that is self-evident. What we ARE interested to know is HOW that solution was reached. And if that solution involved testing 19 random guesses in a non-significant order, then that smacks of brute force and is essentially uninteresting.

What we want to know is what STRATEGY the solver was following, and we want to know exactly why he chose to test any particular candidate in the order that he did. This is perhaps requiring MORE than what is customarily given to us. We are normally just presented with a series of steps with no explanation of how they were chosen.

Now I reject the testing of apparently random candidates, and request a reason for every candidate "tested", which is just another word for "guessed". People are just kidding themselves if they think they are not using "guesswork", and they are kidding themselves even more if they think there is anything UNSUITABLE about using such guesswork.

RATIONAL and therefore acceptable guesswork involves choosing the BEST POSSIBLE GUESS at every point, as part of an overall strategy aimed at FINDING A SOLUTION AS QUICKLY AND EASILY AS POSSIBLE.

Such is my philosophy of sudoku.

Now to how I did it : by using my head! As you will see. It's really quite amazing how lucky you can get by using your head. (Incidentally I made my fortune as a professional gambler).

SOLUTION FROM END OF STEP 10 :

(1) We want to test something. But what?

(2) First look at the simplest area : box 5. This is advice you should always take. In the words of Dostoevsky, "What is simplest is never understood till the last, when everything that is cleverer or stupider has been tried already".

(3) How many patterns are possible for this box, considered in isolation? (the SIMPLEST way to consider it). About 7. About 5 of these patterns involve a 3 at f6 ; only 2 patterns involve a 1 at f6. So that is the SIMPLEST way to go : look FIRST at these 2 patterns. (Checking patterns might be an unfamiliar idea to you. If so, it's time you started using this simple technique).

(4) These 2 patterns are : for box 5: (a) 367/984/521 and (b) 397/486/521.

(5) Test (a) first. IT LEADS STRAIGHT TO THE SOLUTION, using nothing but singles except for one naked [78] pair in row b.

(6) Goodnight! I hope to contribute a further article, on Winning Strategy in Sudoku, soon. If there is any intelligent response to this article. This is flattery, though sincerely meant. In the domain of my "home" turf, the Discussions Forum, I do not even entertain any such hopes. Why? Recently I posted an article on the Solution of the Riddle of Sho simultaneously on both forums. On this forum it elicited some intelligent response, on the other forum not a single word. Maybe I should consider emigrating.
gurth

Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Hi Gurth,

gurth wrote:Maybe I should consider emigrating.

Mmmhh, fresh blood, the Frankenfishes are awaiting you

Let me (again) formulate an extreme point of view:
When i know that a puzzle is unique, guessing a number right is a valid solution technique, when it solves the puzzle.
When you look at tso's ultrahard puzzle there, you could "feel", that r1c2=4, fill in the remaining singles in 5 minutes and then have proved that the 4 was correct.

So much is a matter of taste (but i dont know anyone, who likes proving by guessing).
BTW: When we talk about, what good puzzles and solution techniques are, i think, we also should distinguish between manual solving and solving with programs that automatically show the candidates for you. I would not like to solve ab's second puzzle on paper, which he posted today here, but with a program it is fun: So much candidates and one swordfish (easy to find, when you can filter candidates) cracks it.
And do you know those unpleasing puzzles, where at the end you are stuck with a lot of bivalue cells ? You try this one - no contradiction after 10,12 cells, you try that one - oh shit, the puzzle is already solved. On paper i never minded to show a contradiction for the wrong candidate afterwards.

I would like to have a good technique, which allows a kind of "educated guessing", but there is nothing around for manual solvers. I like the way, how Daj calculates the probability of candidates there, but you need a program to apply it (and programs dont need it to calculate a solution).

Now to your solution. It is not clear for me, why you choose to try the "less probable" candidates first. In the hope, it would lead to a contradiction? Or just, because all the numbers in the box immediately fall into place, when the second number is fixed, so that the chances to solve the puzzle quickly or to find a contradiction are better than for other numbers ?
ravel

Posts: 998
Joined: 21 February 2006

Hello Ravel,
ravel wrote:I would like to have a good technique, which allows a kind of "educated guessing", but there is nothing around for manual solvers.

in solving the hardest puzzles you need some "educated guessing", although I would prefer talking about strategy. What strategy to apply, which candidate to eliminate first and next and next by contradiction? You could sit there days and weeks staring at all the possible candidates and going through them one by one. Computer programs like the Explainer obviously do exactly this, resulting in a haphazard blind reduction of candidates. After I solved the ER10.0 puzzle from Ocean, I looked how the Explainer solves it and thats what it does. It also takes techniques I have never used myself even in the hardest puzzles, like region forcing chains. My bivalue forcing nets have somehow always sufficed, and even memorizing these for n steps in advance is really difficult, so multivalue forcing nets seem (until now, but who knows) more than I can tackle.

So, what is there for human thinking? Some good rules of thumb:

a) The longer a forcing net will run, the more probable it is to run into a contradiction. So don't look for short chains!
b) The more different numbers involved into a forcing net, the more probable it is to run into a contradiction. So look for a cell which "sprouts" different chains with different numbers in all directions. A bit of practice is needed. It took my just 5 minutes to look at the ER10.0 puzzle to find the most vulnerable point.
c) If you just eliminated a candidate, the next forcing net will probably need exactly the fact that it is eliminated. So look for forcing nets which involve the cell you just eliminated a candidate.
d) Bivalue cells are great candidates for simple forcing chains. So look for trivalue cells and try to reduce one of those candidates...
e) If you have a row/column/box with six possible cells for one number, it seems mostly pointless to reduce these possibilities to five cells. Looking for units with 3 or 4 possible cells for one number is better.

The next thing is strategy. Sometimes there seems to be no real strategy, you just have to look for the above rules and are lucky to eliminate a candidate at all. But often the hard puzzles have some bivalue forcing chains with one number, which is a good point to circle around. In the ER10.0 there is the candidates with 1, a nearly perfect x-chain. Strategy would like to link this to another x-chain with another candidate, so there was the idea to take the candidates 3 and mould them by elimination into another x-chain.

Just some observations on the last hardest puzzles.

Greetings, Maria
maria45

Posts: 54
Joined: 23 October 2005

Next