58
$\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?

Improve this question
$\endgroup$
9
  • 10
    $\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
    Commented May 14, 2014 at 22:10
  • 7
    $\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
    Commented Aug 27, 2015 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
    Commented Dec 19, 2016 at 22:39
  • 1
    $\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
    Commented Dec 20, 2016 at 2:47
  • $\begingroup$ I think “solvable without backtracking “ would be a better way of saying it. $\endgroup$
    – John Meacham
    Commented Mar 12, 2017 at 5:13

11 Answers 11

Reset to default
40
$\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.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Best answer so far — I think it is sensible to consider bruteforcing as guessing, even when done in memory. $\endgroup$
    – lynxlynxlynx
    Commented May 15, 2014 at 21:02
  • 13
    $\begingroup$ I think that by definition "trying all possibilities" is guessing - whence the term "trying". $\endgroup$
    – guthrie
    Commented Mar 23, 2015 at 5:56
  • 1
    $\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'
    Commented Dec 19, 2016 at 20:19
  • 3
    $\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
    Commented Dec 20, 2016 at 2:52
13
$\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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ If one is not an expert, they may be faced with a puzzle that requires a strategy they are not familiar with, and will need to guess (as in backtracking). This does not mean it lacks a unique solution. $\endgroup$
    – bryc
    Commented Sep 17, 2020 at 16:49
10
$\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.

Improve this answer
$\endgroup$
2
  • 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
    Commented May 14, 2014 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
    Commented May 15, 2014 at 4:27
4
$\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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented May 14, 2014 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
    Commented Apr 11, 2015 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
    Commented Nov 14, 2015 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Additionally, I speculate that publishing a puzzle with more than one solution was probably unintentional. $\endgroup$
    – James Webster
    Commented Jan 14, 2017 at 14:39
2
$\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.

Improve this answer
$\endgroup$
1
$\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.

Improve this answer
$\endgroup$
0
$\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.

Improve this answer
$\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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 27, 2016 at 19:09
  • $\begingroup$ This board can be solved with the "medusa" technique. See sudokuwiki.org/… $\endgroup$
    – User12345
    Commented May 13, 2021 at 15:48
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?

Improve this answer
$\endgroup$
5
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How would you define "standard" logic? $\endgroup$
    – Brandon_J
    Commented Jan 18, 2019 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
    Commented Jan 18, 2019 at 19:55

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