Discounting invalid puzzles that is -those that for the given clues are contradictory or have more than one possible solution. But for a sudoku with a single valid solution, is it guaranteed that the solution can be found logically? If so, is there a finite “tool kit” of methods guaranteed to be sufficient to solve any valid sudoku? Or are there sudoku that after all local clues are exhausted are “global”- the entirety of the puzzle simply has one valid solution but there’s no way to further reduce the problem at that point?
I believe that Sudoku (in general) is NP-Complete. Which means that as far as anyone knows, there is no general efficient solution. But nobody’s been able to prove it.
What I mean is, it’s possible that there are valid Sudoku puzzles out there where the only way to solve them includes trial and error. And there are definitely valid Sudoku puzzles where, as far as anyone knows, the only way to solve them is through a method that includes trial and error.
What do you mean trial and error? Guessing and going forward until you solve it or back tracking to where you guessed and trying another solution is a logical way to do the puzzles.
But then, trial and error is a perfectly logical method. For that matter, you could solve any sudoku by just checking every possible number in every possible square. Granted, it would take an extremely long time, but in the sense that there’s a methodical way to exhaustively check all of the possibilities, it’s “logical”.
I think the answer is “it depends”. I’ve solved puzzles where I had to resort to trial and error, but:
a) it could be I’m just stupid and didn’t see the obvious
or
b) you could solve it by seeing the bigger picture, by which I mean, what do you consider trial and error? If I can see that putting a 1 in one square means I have to have the 3 in that one, and that wouldn’t work, is it trial and error, or …
I used to do the sudoku in UK newpapers, and they were all marketed as having logical solutions - I have a few books of them were this is emphasised. This is a very important point, it would be a huge turn-off to puzzle-solvers if it all came down to a wild stab in the dark at some point. Admittedly, staring at some of the super-fiendish ones it certainly feels like it has to come down to trial and error, as there just doesn’t seem to be a logical solution - but it is out there.
Not to disagree with brazil84, as I am sure a Sudoku could be set that required a trial and error solution, but I think this would be seen by solvers as a significant failing.
The difference between trial and a “logical” solution as talked about in this thread is how many numbers you can put down on the paper in your head. If you can look at the puzzle and see that If I put 5 here the 7 goes there then 9 goes followed by 1 oh wait thats no good I should start with 8 instead of five and do that in your head is it trail and error. Because basically that is how every body solves the puzzles logically you might not be making quite so many steps but it is always trial and error.
What’s an example of an “illogical” method for solving a Sudoku?
I have yet to encounter a valid puzzle that requried trial and error. There are some fairly sophisticated logical patterns I’ve had to use, but I’ve never had to result to using trial and error on a valid puzzle. When I have, I’ve later plugged it in to a nifty Sudoku program, and it will give me a series of rules from the point where I was stuck.
FWIW, intuitively, it is probably an NP problem even in “Trial and Error” space, but I’m not sure it’s NP-Complete (I don’t really feel like doing the math right now); how would you go about reducing it to another NP-Complete problem? Either way, I think if we were to evaluate it in rule space, which is how we’re supposed to solve them anyway, wouldn’t that inherently reduce the problem to polynomial time (I’m gussing it to be about O(n^2 * R))? Of course, that assumes that all puzzles that are valid can be solved by one of about a dozen or so rules.
Logically speaking though, if it is a valid puzzle (having only a single solution) doesn’t that inherently imply that there must be SOME rule (possibly, as of yet, undiscovered), otherwise, what is it that is making only that single solution valid?
If there’s a unique solution, you can find it logically. But as some have emphasized above, there’s really no meaningful distinction between logic and trial-and-error.
Consider the following Sudoku “move”:
Suppose a row is missing only the 2 and the 4. One of the empty spaces in the row falls in a 3x3 square that already contains a 4. Thus, I can conclude that either that space gets the two or that space gets the four.
That seems like “logic”, but how is it any different than mentally trying the four in that space, discovering a contradiction (two fours in the same 3x3 square), and then concluding the other answer was correct? It’s not any different than trial and error, except I did the trial in my head.
In that case it was easy, because I only had to look one move ahead to see the contradiction. Sometimes you have to look two or three steps ahead, or more. My point is when people feel like they “have to guess” and see if it works out, what they really mean is that they can’t look far enough ahead to spot the contradiction. If you could perform infinitely many moves in your head, you’d never have to guess (except when there’s two solutions that work.)
I guess the underlying question is: What’s the most moves you’d ever need to be able to perform in your head to find the right move, assuming a unique solution exists?
On a related note: does anyone know of a way to determine that a puzzle has a unique solution without solving the whole puzzle? (I think they usually check the ones in the newspaper to make sure there’s a unique solution, but I have an electronic sudoku game that has definitely given me some that had multiple solutions.)
Latin squares. See here.
The only way is trial and error. 
Seriously though, if you get to a point where no rule applies, you have an invalid puzzle. It is also my understanding that they are rated by the “complexity” of the rule required.
Logical but not efficient. Here’s an example of a puzzle that can be solved only by trial and error:
I am thinking of a set of distinct whole numbers between 1 and 10. Try to guess what they are. You can make as many guesses as you like, and I will tell you only whether each guess is right or wrong.
What if, in the worst case, Sudoku was like this? In other words, the only way to be sure to solve the Sudoku puzzle is to fill in a few squares with guesses, then try to complete the puzzle and see if the guesses lead to a contradiction. If they do, then you put in different guesses and try again. And what if you sometimes had to complete nearly the whole puzzle to know if you’d made a bad guess?
That’s what I mean by trial and error.
Sudoku is equivalent to a graph vertex colouring problem. Now if I could only remember if that’s NP-complete or not.
To construct an equivalent graph of a particular sudoku puzzle, choose N colours labelled 1-N, construct a graph where there is an edge between vertex A and vertex B iff the rules of Sudoku say that the same number cannot be there (i.e. for a standard 9x9 grid and numbers 1-9 cell 1,1 is vertex A and has an edge to every vertex representing a cell in row 1, column 1 and every cell in the top left 3x3 grid not already mentioned)
I think that by “logical,” the original poster meant “efficient.”
For example any instance of SATISFIABILITY can be solved in a logical way. But nobody knows if there is an efficient way of solving it, for example by breaking up the problem into smaller pieces and solving each one individually.
Sudoku is simply a specific case of a Latin square with the additional restriction that any specific 3x3 subgrid can contain a number exactly once.
Latin squares were proven NP-Complete by Colbourn in 1984, so reduce from there.
(Yes, Sudoku is in NP because it can be easily verified that the structure is correct…etc, etc)
A thesis by Yato shows that problems such as Sudoku are NP-Complete: http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf
Thanks (and to the others), I’d never heard of Latin Squares. It’s been a while since I’ve done that stuff.
What is the minimum number of “clues” (already filled in squares) needed in order to create a sudoku puzzle (standard 9-by-9 made up of nine 3-by-3s) with one, unambiguous solution?
No one’s ever found one with less than 16 clues, although it hasn’t been proven that that’s the limit.
Subjectively, the difference between “logically” solvable and “trial and error” is if I can comprehend the chain of reasoning that shows that a square has to either be a value or not be a value. Versus simply having to make a 50/50 guess and then follow that until the puzzle is solved or a contradiction shows up. Some very advanced logical methods (“multiple chains”, etc.) verge on this.