# Do all Sudoku puzzles have logical solutions? **URL:** \ **Category:** Factual Questions\ **Created:** [June 15, 2007, 3:46pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132 "2007-06-15T15:46:20Z")\ **Posts on this page:** 20\ **Page:** 6
**Author:** ![Voyager](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/voyager/32/133_2.png) [@Voyager](https://boards.straightdope.com/u/Voyager)\ **Post date:** [October 21, 2016, 11:15pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/102 "2016-10-21T23:15:08Z")
> [@LSLGuy](#): > > You’re using “search” in a more technical sense than I was. Which makes some sense because you’re far more sophisticated mathematically than I am. > > In a “meta” sense I’m “searching” about in logic-space for inference rules that might plausibly drive me closer to the goal state. Using your 3-empty-block example, first I have to notice those three blocks as a plausible region to explore. Then I have to “discover” the first-order implications of the three blocks’ possible values driven by the relevant filled-in squares. Then the second order implications driven by \*those \*implications. One of which is the statement “\*This \*empty box must be a 3” and thus we advance towards the goal state of a completely filled-in puzzle. That’s fair. When I start a new puzzle I search through the blank squares for the ones with obvious answers. For instance, in the 4x4 puzzle from **Indistinguishable** I quickly looked through the blanks and saw that the lower right square is a 2. But even algorithms running on computers which are very good brute force solves have to backtrack in order to solve the problem with a limited amount of processing resources. There are squares which cannot be decided given the candidates now written down. Trying every possible solution is backtracking also, of course. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [October 21, 2016, 11:15pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/103 "2016-10-21T23:15:57Z")
> [@Voyager](#): > > They are more or less equivalent. There have been efforts to parallelize ATPG by assigning branches of a decision tree to different processors. But the tree grows very quickly, in the worst case, so you’ll need a lot of friends, and a lot of them will be standing around while the friend with the branch which is working plugs onward. Sure, sure; I wasn’t making a practical suggestion, just trying to acknowledge that NP would indeed be polynomial time with unlimited (or at least exponential) parallelism available, in which model of computation there would be no “backtracking” necessary, but that “backtracking” was nonetheless the appropriate word for me to use in those posts in the context of a presumed single-threaded computation. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [October 22, 2016, 5:36pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/104 "2016-10-22T17:36:01Z")
I have no idea what **Indistinguishable** ’s problem is. But the resistance to understanding basic Algebra, let alone Boolean Algebra is beyond me. Since when is taking a product of sums and converting it into a sum of products via multiplication remotely anything ever like trial-and-error? That’s all it is. Period. _This cannot be sanely challenged in any way shape or form._ I repeat: it is exactly the same as coverting (X+3)(X-5)(X+1) to X[sup]3[/sup]-X[sup]2[/sup]-17X-15. No one how knows anything about Algebra would never for one second think that this is trial-and-error. _Never_. So why would the _even easier_ Boolean Algebra case be any different??? * * * BTW: I did oversimplify earlier. It’s not the case that if you end up with one product of literals that you have a unique solution. If some variables are left out, you have one or more solutions. Each open variables has to appear exactly once (as negated or not) and that informs the solution. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 22, 2016, 8:00pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/105 "2016-10-22T20:00:26Z")
Boolean algebra is easier than numerical algebra, yes. But in either, the product of 81 terms is going to be ugly. If you think it’s so easy, why don’t you work through a complete example for us? Even just one for a 4x4 puzzle would suffice. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [October 22, 2016, 8:16pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/106 "2016-10-22T20:16:47Z")
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Much of the discussion bypasses a key criterion: _Some puzzles are much more fun than others_ — that’s a key point, perhaps related to OP’s intent. Especially nice are _difficult-to-find_ deductions that _do not require backtracking_. (The precise threshold for for this, the optimal difficulty, might vary between individuals.) I prefer Battleship Solitaire and Nurikabe to Sudoko, and once did a study of Dominoes Solitaire. (Anyone know the puzzle I mean? An ordinary set of 28 dominoes is arranged into a 8x7 rectangle and the lines separating dominoes erased. Your mission is to restore those boundaries.) A _huge majority_ of domino configs had non-unique solutions, a _huge majority_ of those left had an easy single-siting first deduction. Among those which didn’t, a _huge majority_ … and so on and so on. (I created some great puzzles of this type, though much work rests on a defunction laptop ☹ I MIGHT e-mail the best dominoe-solitaire puzzle of-all, by special request!) I’m sure one can do something similar with Sudoku but so what? Several other games, e.g. Battleship Solitaire, are more fun. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [October 23, 2016, 5:37am UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/107 "2016-10-23T05:37:21Z")
> [@ftg](#): > > I have no idea what **Indistinguishable** ’s problem is. But the resistance to understanding basic Algebra, let alone Boolean Algebra is beyond me. > > Since when is taking a product of sums and converting it into a sum of products via multiplication remotely anything ever like trial-and-error? That’s all it is. Period. > > _This cannot be sanely challenged in any way shape or form._ > > I repeat: it is exactly the same as coverting (X+3)(X-5)(X+1) to X[sup]3[/sup]-X[sup]2[/sup]-17X-15. > > No one how knows anything about Algebra would never for one second think that this is trial-and-error. _Never_. So why would the _even easier_ Boolean Algebra case be any different??? Well, I think I know some things about algebra (more than nothing, anyway), and yet I illustrated in [post #100](http://boards.straightdope.com/sdmb/showpost.php?p=19719453&postcount=100) how I nonetheless consider this to be “trial and error” by another name. (Which is not to deny that it is also rote algebra… Algebra can formally describe the process of trial and error). ---
**Author:** ![Gatopescado](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/gatopescado/32/5711_2.png) [@Gatopescado](https://boards.straightdope.com/u/Gatopescado)\ **Post date:** [October 23, 2016, 6:13am UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/108 "2016-10-23T06:13:19Z")
There is no crying in baseball. There is no guessing in Sudoku. ---
**Author:** ![TimeWinder](https://avatars.discourse-cdn.com/v4/letter/t/bcef8e/32.png) [@TimeWinder](https://boards.straightdope.com/u/TimeWinder)\ **Post date:** [October 23, 2016, 4:46pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/109 "2016-10-23T16:46:34Z")
> [@Gatopescado](#): > > There is no guessing in Sudoku. What does “guess” mean, and how do you distinguish it from “logic?” That’s the sharp dividing line that many of us are claiming doesn’t exist. For a loose enough definition of “guess” here, no Soduku with more than a single unfilled square can be done without a “guess” (that you’ll make in your head based and immediately confirm or deny). If you don’t accept that as “guessing,” how about three unfilled squares? Four? Five? At what number of squares and at what configuration did we stop being “logical deduction” and start being “trial and error?” Or put using **Chronos** ’s “working memory” definition – how much is too much? ---
**Author:** ![Voyager](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/voyager/32/133_2.png) [@Voyager](https://boards.straightdope.com/u/Voyager)\ **Post date:** [October 23, 2016, 7:55pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/110 "2016-10-23T19:55:44Z")
> [@TimeWinder](#): > > What does “guess” mean, and how do you distinguish it from “logic?” > > That’s the sharp dividing line that many of us are claiming doesn’t exist. For a loose enough definition of “guess” here, no Soduku with more than a single unfilled square can be done without a “guess” (that you’ll make in your head based and immediately confirm or deny). If you don’t accept that as “guessing,” how about three unfilled squares? Four? Five? At what number of squares and at what configuration did we stop being “logical deduction” and start being “trial and error?” Or put using **Chronos** ’s “working memory” definition – how much is too much? Each empty square in a puzzle has a set of constraints on it which show what numbers the square can’t be filled in with. If the constraints include 8 numbers (no matter how many other unfilled squares there are) filling in the square is not guessing. Filling in the square imposes other constraints on other squares, and for the simpler puzzles you can solve the entire thing with no trial and error or guessing. When no empty squares are left with 8 constraints, then you use trial and error. I’ve taken guessing to mean you just throw down a number and go from there, while trial and error acknowledges you may be wrong and allows you to backtrack to change your choice if you are. It is a guess versus a hypothesis, in other words. ---
**Author:** ![si\_blakely](https://avatars.discourse-cdn.com/v4/letter/s/d9b06d/32.png) [@si\_blakely](https://boards.straightdope.com/u/si_blakely)\ **Post date:** [October 23, 2016, 8:58pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/111 "2016-10-23T20:58:06Z")
> [@TimeWinder](#): > > What does “guess” mean, and how do you distinguish it from “logic?” “guess” means that you select one possible candidate randomly for one cell, and then proceed with the rest of puzzle, until it is complete or inconsistent. That is a “guess”. Sudoku players do not do this. “logic” means that you use the available information about possible candidates to continue eliminating candidates from cells (via algorithms of ever-increasing complexity, none of which involve random information) until you are left with a clear indication of what a cell contains, and the puzzle can be solved. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 23, 2016, 9:57pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/112 "2016-10-23T21:57:20Z")
> [@](#): > > Quoth **Voyager** : > > Each empty square in a puzzle has a set of constraints on it which show what numbers the square can’t be filled in with. If the constraints include 8 numbers (no matter how many other unfilled squares there are) filling in the square is not guessing. For every valid Sudoku puzzle, every empty square has constraints against 8 numbers. It’s just that some of the constraints are more subtle and less obvious than others. ---
**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\ **Post date:** [October 23, 2016, 10:23pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/113 "2016-10-23T22:23:58Z")
So has anyone gotten even one step into the puzzle I linked to? [http://boards.straightdope.com/sdmb/showpost.php?p=19706123&postcount=55](http://boards.straightdope.com/sdmb/showpost.php?p=19706123&postcount=55) ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [October 24, 2016, 8:13am UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/114 "2016-10-24T08:13:57Z")
```auto --- --- --- --- --- --- --- --- --- | 8 | 1 | 2 || 7 | 5 | 3 || 6 | 4 | 9 | --- --- --- --- --- --- --- --- --- | 9 | 4 | 3 || 6 | 8 | 2 || 1 | 7 | 5 | --- --- --- --- --- --- --- --- --- | 6 | 7 | 5 || 4 | 9 | 1 || 2 | 8 | 3 | --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- | 1 | 5 | 4 || 2 | 3 | 7 || 8 | 9 | 6 | --- --- --- --- --- --- --- --- --- | 3 | 6 | 9 || 8 | 4 | 5 || 7 | 2 | 1 | --- --- --- --- --- --- --- --- --- | 2 | 8 | 7 || 1 | 6 | 9 || 5 | 3 | 4 | --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- | 5 | 2 | 1 || 9 | 7 | 4 || 3 | 6 | 8 | --- --- --- --- --- --- --- --- --- | 4 | 3 | 8 || 5 | 2 | 6 || 9 | 1 | 7 | --- --- --- --- --- --- --- --- --- | 7 | 9 | 6 || 3 | 1 | 8 || 4 | 5 | 2 | --- --- --- --- --- --- --- --- --- ``` ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [October 24, 2016, 1:02pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/115 "2016-10-24T13:02:19Z")
> [@si\_blakely](#): > > “guess” means that you select one possible candidate randomly for one cell, and then proceed with the rest of puzzle, until it is complete or inconsistent. > That is a “guess”. **Sudoku players do not do this.** > > “logic” means that you use the available information about possible candidates to continue eliminating candidates from cells (via algorithms of ever-increasing complexity, none of which involve random information) **until you are left with a clear indication of what a cell contains, and the puzzle can be solved.** Bolding mine. That is an overstatement. I agree with your taxonomy, but not with the bolded parts. It is \*not \*always possible for a \*human \*to uniquely determine the value of at least one currently blank square using the process you define as “logic”. It may be that the best that person can do is reduce a blank square, or perhaps a pair of blank squares, to one of two possible values. Yes, a solver armed with near-infinite working memory could continue the logic chain until the value(s) are conclusively known. A mere human cannot. At least not always. At which point the only way to move forward is to select one of those possible values _at random_ then proceed forward under that assumption until it’s either proven correct or wrong. Which game move can arguably be termed “guessing”, albeit from a logically restricted list of choices fewer than nine. And of course following that tentative decision there’s no guarantee that the “correct or wrong” determination will necessarily occur before you’re forced to make yet another random choice between a short list of candidate values for some other particular blank square(s). Lather, rinse, repeat as you recurse down the tree of possibilities your logic can illuminate. Many people refuse to play games that are difficult enough to require this type of play. Others find any game lacking this play to be trivial. As well, different players will have different skill levels and will hit the end of their logic abilities at different places. Even the same player playing the same game on different occasions may take different paths through the game and become totally stymied, forced to guess and backtrack, or not at all and solve it with only forward progress. All depending on the breaks. ---
**Author:** ![Voyager](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/voyager/32/133_2.png) [@Voyager](https://boards.straightdope.com/u/Voyager)\ **Post date:** [October 24, 2016, 5:46pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/116 "2016-10-24T17:46:31Z")
> [@Chronos](#): > > For every valid Sudoku puzzle, every empty square has constraints against 8 numbers. It’s just that some of the constraints are more subtle and less obvious than others. If you mean each puzzle has a solution, duh. But some of the constraints depend on choices made for other squares. If you have the situation where no square’s potential value does not depend on the choice of a value in another square also without a single value, you cannot proceed without lookahead - and since you might choose incorrectly, you have to backtrack or do a breadth first search which will also result in abandoning at least one path. ---
**Author:** ![Voyager](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/voyager/32/133_2.png) [@Voyager](https://boards.straightdope.com/u/Voyager)\ **Post date:** [October 24, 2016, 5:50pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/117 "2016-10-24T17:50:03Z")
> [@Lumpy](#): > > So has anyone gotten even one step into the puzzle I linked to? [http://boards.straightdope.com/sdmb/showpost.php?p=19706123&postcount=55](http://boards.straightdope.com/sdmb/showpost.php?p=19706123&postcount=55) The first commentary there has a pretty good description of the hypothesis method. ---
**Author:** ![Iggy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/iggy/32/3364_2.png) [@Iggy](https://boards.straightdope.com/u/Iggy)\ **Post date:** [October 24, 2016, 6:50pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/118 "2016-10-24T18:50:57Z")
> [@Lumpy](#): > > So has anyone gotten even one step into the puzzle I linked to? [http://boards.straightdope.com/sdmb/showpost.php?p=19706123&postcount=55](http://boards.straightdope.com/sdmb/showpost.php?p=19706123&postcount=55) An [online solver](http://www.sudoku-solutions.com/) confirmed a single solution exists. [Another such solver](http://www.sudoku9x9.com/howtosolve.php) gives a step-by-step approach which requires use of a hypothesis and testing over more than 70 steps to prove that one possibility cannot work so the other possibility must be correct. Technically that is a logical approach. ---
**Author:** ![si\_blakely](https://avatars.discourse-cdn.com/v4/letter/s/d9b06d/32.png) [@si\_blakely](https://boards.straightdope.com/u/si_blakely)\ **Post date:** [October 24, 2016, 8:14pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/119 "2016-10-24T20:14:33Z")
> [@Iggy](#): > > An [online solver](http://www.sudoku-solutions.com/) confirmed a single solution exists. [Another such solver](http://www.sudoku9x9.com/howtosolve.php) gives a step-by-step approach which requires use of a hypothesis and testing over more than 70 steps to prove that one possibility cannot work so the other possibility must be correct. Technically that is a logical approach. Having attacked that puzzle with an app on my phone, I agree with the “really, really, really hard assessment”. There is no easy start - a single cell with only 2 candidates, and no additional eliminations. The app provided no hints - it obviously does not do deep (70 step, sheesh) look-ahead. And I’ll admit to finally accepting that I needed to bookmark and track ahead to prove consistency. It may be possible to use a chain or pivot to make that proof logically (i.e without a test hypothesis), but I’m not good enough to do yet. But I’ll keep trying, once I have cracked more of the advanced techniques. The “Extreme” puzzles on my phone are hard enough and have fully logical solutions (that I have not completely learned to apply yet). I’ll stick with them for now. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 24, 2016, 8:15pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/120 "2016-10-24T20:15:42Z")
> [@](#): > > Quoth **Voyager** : > > If you mean each puzzle has a solution, duh. But some of the constraints depend on choices made for other squares. This happens quite often, and in situations that almost nobody calls guessing, and yet they still require some nonzero amount of look-ahead. For instance, here’s a partial puzzle: ```auto _ 1 _ 2 4 5 6 7 8 ? _ _ 8 9 1 4 _ _ _ _ _ 5 6 7 8 _ _ ``` What is the value of the question-mark square? Based on its column, I can eliminate 4, 5, 6, 7, and 8, based on its row I can eliminate 1 and 9, so all that’s left are 2 and 3. And I can’t pick which one of those it is without thinking about what might be in other squares but isn’t penned in yet. But what I can do is to note that one of those two blanks in the top row must be a 3, and both of them are in the same block as the ? square, and so the ? square can’t be a 3. I think that everyone would consider this technique to be “logical” and “legitimate”, but it requires one level of look-ahead: I have to consider what might be in blank squares to fill in a different square. Nor can I fill in those two squares first and then proceed from there: In the partial example given, I still don’t have enough information to say which of those two blanks is a 3 and which is a 9. This method is legitimate, and yet it differs only from “guess and check” in the amount of working memory it requires. In this case, it’s only a small amount of memory, but one can envision a situation which requires more memory, enough that some people can’t keep track of it all in their heads but others can. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [October 24, 2016, 8:26pm UTC](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132/121 "2016-10-24T20:26:32Z")
> [@Lance\_Turbo](#): > > I think the line some people are trying to draw in this thread is the difference between one-block elimination strategies and two-block elimination strategies described in [this paper](http://www.math.uci.edu/~brusso/provanAMM2009.pdf) by Prof. Provan of UNC. The paper has a pretty good example of a sudoku where one-block strategies only get you so far at which point a single two-block strategy is applied and the rest of the puzzle falls to one-block strategies. > > For some sudoku even two-block elimination strategies will not get the job done. At the time the paper was written the smallest n where n-block strategies will solve all sudoku was not known. I don’t know if that problem has since been solved. Lest you think this link went unappreciated, it did not; I very much enjoyed reading this paper, a concrete mathematical examination of a natural class of Sudoku inference rules and its limitations, and thank you for introducing it to the discussion. [Previous page](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132.md?page=5) [Next page](https://boards.straightdope.com/t/do-all-sudoku-puzzles-have-logical-solutions/408132.md?page=7)