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.
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.
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.
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.
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
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.
Well, I think I know some things about algebra (more than nothing, anyway), and yet I illustrated in post #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).
There is no crying in baseball. 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?
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.
“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.
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.
So has anyone gotten even one step into the puzzle I linked to? http://boards.straightdope.com/sdmb/showpost.php?p=19706123&postcount=55
--- --- --- --- --- --- --- --- ---
| 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 |
--- --- --- --- --- --- --- --- ---
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.
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.
The first commentary there has a pretty good description of the hypothesis method.
An online solver confirmed a single solution exists. Another such solver 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.
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:
_ 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.
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.