## Solution to Ocean's #07/18

Advanced methods and approaches for solving Sudoku puzzles
Thanks Maria,

very interesting (though it was not what i meant with "educated guessing").

What i noticed for "middle hard" puzzles is that it is often better to try to eliminate candidates that would give you a number (e.g. one of two strongly linked candidates) than just trying to find a short chain (this is a reason that ER's solutions often have a lot of redundant eliminations).
ravel

Posts: 998
Joined: 21 February 2006

maria45 wrote: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? (...)

Very interesting comments on solving strategy, and rules of thumb.

(Wonder if it's possible to incorporate some of it into algorithms for finding new hard puzzles...)
Ocean

Posts: 442
Joined: 29 August 2005

RAVEL,
History repeats itself. Once again you are the man who replies to me. At length and in detail.

And I see that Maria has replied to your questions which apparently you addressed to me, before I could! At great length! So perhaps I should dispose of that interruption first. (Hey, I am joking!)

I fully agree with each and every suggestion of strategy put forward by Maria. Also I whole-heartedly support all her methods of solution. In particular:
(1) I endorse her statement "in solving the hardest puzzles you need some "educated guessing" ".
(2) I support her use of "forcing nets" as the most rational way to go - also something that is very far from being universally accepted.

To come now to one of your cruxes, Ravel : "It is not clear for me," you say, and I say : "Nothing can be more important for me than that it should be clear for you." So here goes :

(aa) I choose the candidate 1 in f6, because there are only two box-5 patterns with 1 at f6. So I have at most two patterns to test before I MUST discover whether or not 1 is true at f6 ! Which you must see must be a colossal step forward in solving the puzzle. I think this fully answers your last paragraph. Please correct me if you think I am wrong in this thought.

To come now to your sentence "...I never minded to show a contradiction for the wrong candidate afterwards." But I do mind! You ask me to find a needle in a haystack, and you guarantee there is only one needle. I find it, and now you expect me to go on searching the rest of the haystack! Am I being unfair with this analogy?

To come now to the sentence "...you could "feel" that r1c2=4, fill in the remaining singles in 5 minutes and then have proved that the 4 was correct." But what I want to know is HOW you could "feel" anything. If you can JUSTIFY that feeling, then I will accept your "proof".

But let's suppose you are not too happy to go along with my last two paragraphs. I will perhaps be able to accept that in the interests of practical compromise. Then to become more fully happy with my method in paragraph (aa), all you need to do is to check the other pattern as well, which will of course lead to a contadiction.

BTW, you say also, and I agree : BTW. Which means, one day I will get around to that somewhat digression, I hope. I have made this same point on the other forum : that solving techniques must be considered in relation to the resources being used : pencils, computers etc.
gurth

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

gurth wrote:To come now to your sentence "...I never minded to show a contradiction for the wrong candidate afterwards."

Sorry for my poor English, i wanted to say the opposite I never cared to prove the other candidate wrong on paper. When i find the solution directly when testing a candidate, i dont like the puzzle and i am happy to have done with it. But this happens very seldom. I suppose, it would be the case more often for very hard puzzles, but those i never try on paper.
But when someone asks for help for a puzzle and it would happen then, i always feel obliged to give a proof. I suppose the questioner would think, i am kidding, when i say "try this number and you will see, it solves". Its like posting the solution grid.

So we have 2 different situations. The one is to try to solve a puzzle "quick and dirty" (e.g. championships) and the other to solve it "clean and fit for publishing". I can follow your arguments, when you tried 2 numbers and it was solved, but my first thought then is "how lucky you were". With some bad luck you would have been stuck again with at least one of the 2 possibilities.
ravel

Posts: 998
Joined: 21 February 2006

well, I'd like to play the devil's advocate here concerning the "lucky" guess, or otherwise called backdoor. One could argue that a backdoor is by itself also a proof by contradiction, e.g. a proof by missing contradiction...

Regards, Maria
maria45

Posts: 54
Joined: 23 October 2005

Ravel,

somehow you don't seem to be quite getting my points.

"When i find the solution directly when testing a candidate, i dont like the puzzle and i am happy to have done with it." Are you now blaming the Puzzle if you get lucky? What is wrong with good luck? And can I help it if I was born under a lucky star?

And that person who is asking you for assistance with a puzzle : of course I wouldn't teach him by saying "try that guess and you will see it works." You don't seem to be getting my point about JUSTIFYING GUESSES at all. I am not saying use guesswork - I am saying use intelligent guesswork - a world of difference. I would teach by asking : what do you think is the most intelligent guess you could make in this situation?
gurth

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

gurth wrote:Are you now blaming the Puzzle if you get lucky?

Yes, i blame the puzzle, but not because i got lucky. A puzzle that requires running through 20 bivalue cell to solve it, what is neither hard nor elegant, but simply boring (looking for singles is more exciting), is just no good one.
You don't seem to be getting my point about JUSTIFYING GUESSES at all.

I think, i got this point and Maria's tips for intelligent guesses. Therefore i asked you, why you chose to try those candidates. From your answer i would say, your way is following point a) and b) in Maria's list: Since you immediately get many numbers you have good chances not to get stuck soon and because all numbers in the box fall into place, many different numbers are involved.
But i suppose Maria would not be satisfied with your solution.
We still have to distinguish "dirty" and "clean" solutions.
ravel

Posts: 998
Joined: 21 February 2006

Perhaps I am guilty of raising too many issues at once. But never mind. It is interesting to discuss the question of guessing, until we tire of that discussion.

Then eventually another question needs to be addressed: To what extent does my technique (pattern analysis) need guessing? And lastly, has that technique been of any value in this puzzle? Has it effected any worthwhile simplification or shortening of the solution?

If we get past such questions, then further questions become worthwhile, such as : what is the essential principle behind the success of this method? Once that principle is understood, can it not be applied to other methods, even SUGGEST other, new methods?

Today I will content myself with stressing a point which should already have been perceived. In choosing box 5 for my analysis, there was no guess involved : it was obviously the simplest box to tackle. The analysis I made of that box was quite elementary : it disclosed 7 possible patterns. No guess so far. It was also obvious that only two possible patterns involved digit 1 at f6. No guess. To then decide to examine both these two patterns is not a guess. And that is all that is involved in discovering the true digit for f6.

Conclusion: the technique of pattern analysis requires no guessing at all.

The foregoing I prepared before seeing your latest posting, Ravel. "Since you immediately get many numbers you have good chances not to get stuck soon.", you say. YES, THAT IS THE MOST ESSENTIAL POINT.

"But I suppose Maria would not be satisfied with your solution."
As we have now removed all guesswork from the technique, I would like to know what other objections there might be.
gurth

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

Gurth,
we are mixing 2 things here, the philosophy and the strategy of solving (hard) sudokus. Depending on my philosophy i either can repeat 1000 arguments against your solution - independantly of your strategy - or applause.

The deviding question is, if you accept uniqueness techniques or not.

If i dont, i only accept a placement of a number, when it is also proved that all other numbers cannot be placed there.

If i do, i also have to accept a lucky guess, that solves the puzzle, as proof for a valid solution. I dont like that, but it is a fact. To exclude that, we had to introduce an extra rule for a valid solution (would you call it an axiom ?), that says, that guessing+solving is not valid, as long as the other candidates are not proved wrong (where uniqueness is allowed for the proof). But this is, what most people think of being a valid solution.

So in the second case it is worth looking for solving strategies like yours - look for patterns, where you have good chances to either solve the puzzle directly or getting another number.
In the first case (and in the most common, classical POV) a solution you find this way would rather be looked at as an accident than a solution.
ravel

Posts: 998
Joined: 21 February 2006

Previous