The New Sudoku Players' Forum

[ListentoRichter]

First time on this site. Perhaps my question has already been discussed.

Question. Has the following question been answered? No matter the level of difficulty of a SUDOKU PUZZLE is it always the case that the puzzle is solvable without ever making a guess between two possibilities in a particular square? I have at times found it necessary to guess between 2 possibilities. From that point one contiunues until the puzzle is actually solved or a contradiction is reached. If a contradiction is reached then all one does is to go back to the guessed square, used the 2nd possibility, and, usually this will lead to a solution.

[Moschopulus]

Your question has been asked many times before, and there have been heated debates on this topic. The fact that it keeps coming up is interesting in itself, perhaps more interesting than the question. Anyway, yes, there are sudokus that require guessing. You won't find any of them in newspapers, so if you get your puzzles in a newspaper then they can be solved without guessing.

Now watch the flurry of replies.....it depends what you mean by "guessing"....

[stuartn]

Hush guys....... let them think we haven't seen them...........

[emm]

Listentorichter, you might be the 2294th person to have asked this hoary old chestnut, but don’t worry, I was about the 1294th.

The answer is simple – some girls do, some girls don’t.

PS : Pappocom doesn’t.

[tso]

Don't worry, I'll be good. One of the many threads on the subject is here.

No one knows for sure if there are 9x9 Sudokus sufficiently hard enough to claim that they will never be solved by a clever enough human with the right tactics without having to resort to guessing. The line between those we know how to solve and the ones we don't is still moving.

There are 9x9 puzzles that are currently far enough beyond current by-hand solving methods that even trial and error may still not lead to a quick, easy, because the puzzle cannot be reduced much by other methods, for example:

Code: Select all

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


Puzzles like this are very economical -- for most people solving with pencil and paper, it will be comparable to solving a dozen or more of the hardest puzzles typically published in newspapers -- as they will be forced to take a guess, solve from their, backup, start again, several times.

[ListentoRichter]

I asked this question for a particular purpose. The creator of the Sudoku puzzle says that the puzzles can be solved using logic alone.
However, a major rule of logic, known as the "Law of the excluded Middle" is often used in logical proofs. As a matter of fact there are some mathematical theorems that can only be proved using this method.

It goes like this. You are at a point in which you know that only one of either A or B is true, and the other is false. You proceed as follows. Assume A is true(i.e. one of a pair of numbers belongs in this square). From there you continue to use the laws of logic. If you reach a contradiction then you know that your assumption (A is true) must be false. That procedure is known as the reductio ad absurdom. Having reached an absurdity based on the assumption that A is true then it is obvious that A must be false. Therefore B is true (since one of the two had to be true - i.e. the other numer belongs in the square). If however the choice of A does not lead to an absurdity then you will have solved the puzzle. This method is central to the rules of logic!!!! So, please do not consider a choice between two possible ways to fill in a square as "not using logic" - but using a guessing technique. If that were the case then there are several laws of mathematics that would still be logically unproved.

Thanks for your reply

[lunababy_moonchild]

We've been through all of this before.

Here : Solving techniques/Hard puzzle in Eppstein's paper etc (Just plug reductio ad absurdom into the search facility)

Luna

[Nick70]

It goes like this. You are at a point in which you know that only one of either A or B is true, and the other is false. You proceed as follows. Assume A is true(i.e. one of a pair of numbers belongs in this square).

To assume this you also need to rely on the solution of the puzzle being unique. Otherwise, BOTH possibilities in the cell could lead to a valid completion of the grid!

I don't like this, because in the end you will have found a solution but not necessarily proven that it is unique--you rely on someone else having proven it before you.

To prove that the solution is unique, you would have to always test all paths every time you make a guess. This is what double forcing chains do.

[stuartn]

Code: Select all

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


-- as they will be forced to take a guess, solve from their, backup, start again, several times.

only 2 guesses in this one!

stuartn

[tso]

I asked this question for a particular purpose. The creator of the Sudoku puzzle says that the puzzles can be solved using logic alone.

If you are refering to Wayne Gould, though he did is write a the software program available on this website and is probably the person most responsible for the recent popularity of Sudoku, he is *not* the creator of Sudoku or Number Place, though he seems to have taken it upon himself to rewrite the definition of Sudoku, puzzles in general -- and even what is and isn't logic -- making the claim that puzzles that are too difficult to be solved by his allowable subset of logic are invalid, leading to ongoing confusion and puzzle rating inflation in newspapers.

Of course, all Sudoku, regardless of how difficult, can be solved by logic. Wayne's idea of allowable logic is extremely limited.

However, a major rule of logic, known as the "Law of the excluded Middle" is often used in logical proofs.

I think we're well aware of this. The struggle is to find the easiest and/or best and/or most elegant method. We always have this type of proof by contradiction as a last resort once the puzzle has been reduced as far as possible by other methods.

[ListentoRichter]

The puzzle was presented to me as always having a unique solution. I.E. you already know that there is only one solution!

[Doyle]

The puzzle was presented to me as always having a unique solution. I.E. you already know that there is only one solution!

Ah yes, but (restating some of the things said above - and much previously, and often), the T/E approach is something which I see only as a last resort, even though canonically logical. And I never actually resort to it, if I can't (yet) solve by more direct (and enjoyable, and satisfying) methods, then I drop that particular puzzle, knowing it can be solved by T/E, but not bothering to.

A funny thing about solved grids: they all look the same, and are a bit of a letdown when completed and staring at you (as opposed for example to an elegant mating position in chess). It's the getting there that's fun, and some routes are more so.

[emm]

Isn't this one of those protracted (but very interesting) discussions that goes back to a simple definition of terms - one man's logic is another man's guess is another man’s logical guess - and to the fact that values have been attached to the terms i.e. Logic = good, Guess = bad. Isn't it a question of what floats your boat?

[quote="Wayne's idea of allowable logic is extremely limited.
[/quote]

As far as 'allowable' goes - it seems to me that if Wayne writes the program then he can determine its parameters. If we don't like it, then we can do someone else's puzzles. Mais non?

I'm going to leave the elegant mating rituals of chess players to the experts!

[lunababy_moonchild]

Isn't this one of those protracted (but very interesting) discussions that goes back to a simple definition of terms - one man's logic is another man's guess is another man’s logical guess - and to the fact that values have been attached to the terms i.e. Logic = good, Guess = bad. Isn't it a question of what floats your boat?

Wayne's idea of allowable logic is extremely limited

As far as 'allowable' goes - it seems to me that if Wayne writes the program then he can determine its parameters. If we don't like it, then we can do someone else's puzzles. Mais non?

I'm going to leave the elegant mating rituals of chess players to the experts!

Mais non. Here, here and well said

Luna

[tso]

As far as 'allowable' goes - it seems to me that if Wayne writes the program then he can determine its parameters. If we don't like it, then we can do someone else's puzzles. Mais non?

Sure -- but the problem is that he claims that puzzles beyond a certain level are "invalid" -- not actually Sudoku at all. He condescends that puzzles in newpapers he doesn't serve are merely "sudoku-lookalikes" (here, and here -- is it ethical to make a chess program that refers to competitors as"chess-lookalikes"?). He didn't invent Sudoku, didn't come up with the name or make any change to the existing genre. He can call them "hard" or "to hard for me" or say "I don't like them hard ones.". It isn't "logical" for him to call them "invalid". If he did in a vaccuum, it wouldn't matter. But he is "sudoku.com". He sells what I would guess is the most popular Sudoku program. Newbies get the software, try to dub in a hard puzzle from elsewhere and are told it is "invalid". It's confusing and annoying.

From the help file in his software (bolds are mine):

Not-verified puzzles
If a puzzle is Not verified, it could be because —

If you are dubbing, there is a mistake in the dubbed clues.
Check the message area of the Dubbing toolbar for tips and advice.

If you are working with a library book, there is an error in the file.
If you know how to create your own books, you know how to check the data for errors.

The puzzle cannot be solved using logic.
The solution – if it has a unique solution at all – can only be found by guessing or using trial-and-error. Note that the program can solve unfair puzzles, nevertheless.

There is an error in the source puzzle.
At Pappocom we have a database of 25,000 Sudoku puzzles published world-wide over a 5 year period. Of the puzzles published in books and magazines, about 1 in 700 is just plain wrong. Sometimes the error is obvious on the face of the puzzle. Sometimes a clue has been omitted. Sometimes the error goes deeper.

The error rate for Sudoku puzzles published on the Web is much higher. Nearly 1 in 200 is impossible.

I entered this puzzle into a Pappocom library file:

Code: Select all

...6....1
.9.1...7.
6...2..98
..49....7
5...7...6
8....32..
78..9...3
.5...4.6.
9....1...


When I tried to load it, I got this message:

Sorry, cannot show puzzle 1 from test.

The data in <question> does not form a valid puzzle.

To be valid, a puzzle must be solvable using logic alone. If you must use guess-work or trial and error to get the answer, the puzzle is not valid.

This puzzle is perfectly valid, perfectly solvable. It may be a challenge, but it requires only one advanced tactic -- a Swordfish.

I'm not debating free speech. If he wants to call his dog an banana plant, he's certainly free to do so. It doesn't mean we'll have any bananas. I've harped on this before -- I don't understand why I seem to be alone on this. He's also free to write a chess program that claims castling is "invalid". It would be *exactly* as absurd, confusing and annoying. Yes, we could simply avoid the program, but we would still have to deal with all the people it will teach that this move is "invalid".