50
$\begingroup$

I believe in a number of books I have read and solved myself, the introduction stated that guessing should never be necessary for any of the puzzles in the book. Instead, a handful of techniques could be used to solve the puzzle completely, including the hard puzzles.

Are there published puzzles out there that do require guessing? Perhaps designed to challenge those who have "mastered" the more basic Sudoku puzzles?

$\endgroup$
  • 7
    $\begingroup$ Close voters: please remember that since we are in private beta and defining scope, it's important to leave a comment explaining why you think the question is off-topic. $\endgroup$ – WendiKidd May 14 '14 at 22:10
  • 3
    $\begingroup$ "Any valid Sudoku can be solved without guessing, just by exhaustively trying all possibilities." What is the difference between guessing and exhaustively trying all possibilities? $\endgroup$ – user16012 Aug 27 '15 at 4:37
  • $\begingroup$ Anecdotally, I've twice come across sudoku's that left me with a cycle. That is, there was a choice to make, and either one would have been correct. Not the same as guessing. $\endgroup$ – Chris Cudmore Dec 19 '16 at 22:39
  • $\begingroup$ @Cudmore - I think this is the same as "guessing". Two choices, no (obvious?) logic determining which to use, so choosing one is (bu definition) guessing. If it leads to a solution, good guess. If not, backtrack, which is of course just the standard name for handling guessing. Choice made without logic = guess. $\endgroup$ – guthrie Dec 20 '16 at 2:47
  • $\begingroup$ I think “solvable without backtracking “ would be a better way of saying it. $\endgroup$ – John Meacham Mar 12 '17 at 5:13

11 Answers 11

32
$\begingroup$

The immediate answer is no. Any valid Sudoku can be solved without guessing, just by exhaustively trying all possibilities.

However, there are two interesting variant interpretations of the question:

Are there Sudoku puzzles that can't be solved logically?

This one depends on what you accept as a "logical solution." In the strictest sense, the answer is again no. However, if you define a "logical solution" as excluding brute-force solving, the answer is probably "yes." There is some imprecise agreement on what constitutes a logical solution under this definition in the puzzling community, but based on this, we will again find that yes, there are definitely Sudoku puzzles that have no logical solution.

Thomas Snyder has given an insightful definition of when a puzzle is solvable logically:

When I can solve a puzzle in ink, without erasures, with all deductions either positive or negative coming from visualization in my head and not making scratch-work on the paper, the puzzle is solvable by logic.

Are there Sudoku puzzles that are faster to solve by guessing?

Again, the answer is "yes." In a competitive setting, most solvers would not use the more obscure techniques. After having narrowed possibilities somewhat with realistic techniques, some puzzles "require" guessing so as to not put the solver at a competitive disadvantage.

$\endgroup$
  • 1
    $\begingroup$ Best answer so far — I think it is sensible to consider bruteforcing as guessing, even when done in memory. $\endgroup$ – lynxlynxlynx May 15 '14 at 21:02
  • 7
    $\begingroup$ I think that by definition "trying all possibilities" is guessing - whence the term "trying". $\endgroup$ – guthrie Mar 23 '15 at 5:56
  • $\begingroup$ @guthrie Sorry, no, no and no. There are people who can consider a chess game 8 moves forward or so. I'm quite sure that if these people concentrated on sudoku rather than on chess, they would not say they are "guessing". You could equally say that at one moment you try all numbers 1,2,3,...,9 into one cell to find out that only 7 fits in -- does this make all standard sudoku methods "guessing"? $\endgroup$ – yo' Dec 19 '16 at 20:19
  • 2
    $\begingroup$ @yo - no, no no - "trying a bunch of things" without an underlying logic to guide the choice, is guessing. Your example of "considering all possible values for a cell" is an interesting example, and although this starts to be just semantics, I would say if you commit to one of them without a logical basis and try to then make it a solution, yes, =guessing. Just looking at each possibility to see if there is some logic for it = not-guessing. $\endgroup$ – guthrie Dec 20 '16 at 2:52
12
$\begingroup$

Every "proper" sudoku puzzle which only has one solution can be solved without guessing.

The only time you would need to guess is when the sudoku puzzle is improper, and thus has multiple possible solutions, and your guesses would be irrelevant to whether the puzzle could be solved.

And, just so people are aware, improper sudoku puzzles are actually not uncommon. I have a booklet of them on my shelf, so these puzzles are actually used.

In these cases, the puzzles aren't more challenging necessarily (though they're typically written to be). While improper puzzles can be harder to solve, they are not usually more difficult to solve because they are improper, but rather because the design of the puzzle is more difficult.

$\endgroup$
8
$\begingroup$

TL;DR - short of a definitive mathematical proof, there is no way of knowing.

If you do a web search for Sudoku solving techniques, you will find that there are a great many. Some of them are difficult and obscure, but handle cases that can't be solved any other way.

My own experience, using the Sudoku app on my tablet, has been that every puzzle, no matter how difficult, can be solved by some technique, no matter how obscure. So, if you don't know a technique for a given situation, you may be reduced to guessing, but when asked for a hint, my tablet has always had a technique up it's sleeve for every possible situation.

$\endgroup$
  • 1
    $\begingroup$ It depends on whether or not the puzzle has a unique answer. If there is only 1 answer, you should not need to guess. If there is more than one, you will definitely be required to at some point. $\endgroup$ – WendiKidd May 14 '14 at 22:09
  • 2
    $\begingroup$ @WendiKidd Perhaps my explanation is at fault. By definition, all Sudoku puzzles are supposed to have exactly 1 answer. However, some of the techniques needed to solve the very hardest puzzles are very obscure and hard to understand, so rather than learn them, some Sudoku fans resort to guessing. So while guessing is not, strictly necessary, it works better for some people than the alternatives. $\endgroup$ – Donald.McLean May 15 '14 at 4:27
3
$\begingroup$

If by 'guessing' you mean writing down numbers that you are not sure about, then no, every proper puzzle is solvable (in theory) by looking at all the possibilities remaining. This is the brute force algorithm.

However, some puzzles are complicated enough that you won't be able to remember all the possible values. This is simply a case of humans having poor short-term memory, and you will require additional resources (like writing down numbers and trying them).

As you get better and better at solving Sudoku puzzles, your brain recognizes more and more patterns, and when the puzzle you're solving matches one of those patterns, your brain can remember the solution. The more experience you have, the less difficult your reasoning becomes, and the less likely you are to find a puzzle that requires brute forcing.

$\endgroup$
  • $\begingroup$ Every puzzle with a unique solution is solvable without guessing. If there's more than one solution, that's not necessarily true. $\endgroup$ – WendiKidd May 14 '14 at 22:10
  • 1
    $\begingroup$ @WendiKidd Can you show me a proof that if there is an unique solution then no backtracking is required? I don't find that intuitively obvious. $\endgroup$ – user66554 Apr 11 '15 at 21:20
  • 1
    $\begingroup$ It's more a definitional question; what is considered a valid rule of logic, and what is considered guessing? $\endgroup$ – Richard Rast Nov 14 '15 at 9:37
2
$\begingroup$

I do a lot of sudokus. In at least 3 cases over the last few years, I found a puzzle that had more than one solution. It was an either/or type of thing. I had to choose which one of a pair of numbers was going to be the "solution" number. From there, I could solve the puzzle. I actually saved one puzzle and ran it both ways. It checked out each way. Very,very rare, but it happens.

$\endgroup$
  • $\begingroup$ Additionally, I speculate that publishing a puzzle with more than one solution was probably unintentional. $\endgroup$ – James Webster Jan 14 '17 at 14:39
2
$\begingroup$

I came across this result that claims that 16-clue sudokus are not solvable without guessing as they have multiple solutions possible. While they have used brute-force to go over all the solutions, there is no mathematical proof yet. I think.

$\endgroup$
1
$\begingroup$

NOTE: I have read all the answers and tried to answer the main problems mentioned there.

  1. Brute-force solving a Sudoku is not considered "guessing".
    • If it was then filling in any square (single number) would be a guess (to do this you "brute-force" (choose from) all the numbers available (subset of 1-9) into the square and check if it is the right one using logic).
  2. What does it mean to "solve" a Sudoku puzzle?
    • "Find the puzzle creator's intended solution"
    • "Fill whole grid without violating the rules". I believe this one is correct.
  3. Every Sudoku puzzle that has at least one solution (we don't consider puzzles with no solution) can be solved (definition from #2) using brute-force (which by #1 is not considered guessing).

Considering the above I claim that:

Sudoku puzzles never require guessing.

Guessing would be necessary only if solving the Sudoku puzzle means to get the puzzle creator's intended solution and there are multiple valid solutions available.

$\endgroup$
0
$\begingroup$

Yes for example, the puzzle below cannot be solved by logic only guesswork and it only has one solution too.

enter image description here

$\endgroup$
  • $\begingroup$ Isn't the arrangement in the middle third grid a "nice loop," or x-cycle ( a coloring problem ) with an overloaded 5 in D9 ( the discontinuity )? The 5 in D1 then becomes the only valid five in the middle first grid - no guess necessary, just deduction. $\endgroup$ – Avarkx Nov 27 '16 at 19:09
0
$\begingroup$

Ok, this thread has no clear answer. However, this example may prove that the answer is that some Sudoku puzzles require a guess as part of the technique. See the three puzzles below.

PUZZLE 1 OF 3:

____642_3  
_4___89_6
__6_5_4_7
6_38__745
45_6_3821
___54_639
2_143_5_8
7_41_5362

PUZZLE 2 OF 3

14_9__73_
763_148__
__2_3_461
_37__16__
_5____14_
__1___25_
81__4_9__
3291__5_4
_74__931_

PUZZLE 3 OF 3:

__25___98
49__2___5
3_59__2__
864312759
153798_2_
927654831
2_1__59_3
____3_582
53_2__1__

Plug the puzzles into a Sudoku solver website such as this and you will see that the solver reports back that it is stuck. There is no more logic to use to deduce the solution, therefore you must guess at one of the pairs.

Can someone please chime in and agree or disagree with assessment?

$\endgroup$
0
$\begingroup$

The simple answer is yes, but not in most cases. A prime example is Arto Inkala's Worlds Hardest Sudoku it has been published with the point that it has a high number of required guesses. Another good example is SudokuWiki's Weekly Unsolvable Sudoku all of them have the property that they require guesses, although occasionally one of those turns out to be solvable by logical means.

The important thing to note here is these are published specifically as not solvable by standard logic. Most puzzle makers go through some effort to make sure their published puzzles are all solvable by logic, either by having a human solve it using only logic or having software solve it using logic based techniques humans would use. This is usually incorporated in the grading of the puzzle as easy or extreme if it is found not to be solvable without guessing it won't usually be published.

$\endgroup$
  • $\begingroup$ How would you define "standard" logic? $\endgroup$ – Brandon_J Jan 18 at 18:15
  • $\begingroup$ In this case very loosely. Mainly I mean the group of logical methods implemented by human style solvers that don't use trial and error. $\endgroup$ – Rocus Halbasch Jan 18 at 19:55
-1
$\begingroup$

There are definitely a lot of Sudoku puzzles that require guessing. By guessing I include selecting a box for which you have two potential numbers and using one of those numbers to see how far it will take you to solution. If you solve the puzzle you "guessed" correctly. If you get a conflict, you go back and use the other number to solve the puzzle. I have also seen puzzles where it did not matter. You could chose either number and solve the puzzle. It is still guessing and I consider it a crappy puzzle.

$\endgroup$

protected by Community Aug 22 '16 at 4:29

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.