Actually, I don’t think that sudoku can properly be called NP-complete, since they’re constant size. I can write a very stupid brute-force algorithm guaranteed to eventually solve every sudoku, and I can then find an absolute upper bound on the running time of that algorithm. That’s not only polynomial time, it’s O(1) (albeit with a very large coefficient). Nor is there any obvious generalization of the concept of a sudoku to arbitrary n. At best, I suppose there’s an obvious generalization to arbitrary perfect squares.
Even when you have to guess, it’s not 50-50. Whenever I get to a point where I have to guess, I first try the possibility which seems to imply the most about other cells. A choice which implies a lot is more likely to quickly imply some contradiction, at which point of course you undo all that work and go with the other choice.
The logical way to do the puzzles is making a guess and seeing if contradictions show up. It is just that after working on the puzzles for a while you have some short cuts so it does not seem like you are making these hypothesis and eliminating them. When there is only one space left in a row you chose the missing number. How do you find the missing number you see which numbers are left. Those are guesses that are eliminated quickly.
I don’t think of it as trial and error; trial and error requires erasures when you discover a contradiction. For Sudoku, you might conclude that a space could hold either a 2 or a 4. You later find a 4 in the same row, and so know the first space must be a 2. That’s not trial and error, to me.
Example of Trial and error: the space could be a 2 or a 4. Let’s try 4 and see what happens. Ah, that makes this other space a 6, and this one a 9, and this one an 8… oops, there’s already an 8 in that box. So, I guess the original wasn’t a 4. Erase the 8, erase the 9, erase the 6, erase the 4, and put in a 2.
I never do that in solving Sudoku. If a space could be a 2 or a 4, I write both numbers in lightly and wait until I know I can eliminate one. But it’s never more than one square being treated that way.
Well, in that you are dealing with a specific problem size, you’re right that it is indeed constant in the time and space bounds of the problem.
However, if we look at the GROWTH of the problem, then I think we can safely consider it as NP-Complete. Consider Hexdoku, consisting of a 16x16 grid with 4x4 subgrids, filled in with the symbols 0-F. The space complexity growth would only be quadratic, but would the time required remain polynomial as well? I certainly would not say so…have to focus too much on quantum algorthms at the moment to do the math (need to write a quick paper on number sieves and Shor’s Algorithm and quantum and classical cryptography to remove an I from a class…long story…but I digress), but even with the restrictions I have a feeling it’s still exponential in nature. However, the cerfificate verification time certainly would only scale quadratically, so the problem would remain in NP. Further, there have been shown polytime reductions to the problem, so we can declare the general problem NP-Complete.
Well, a coworker of mine was watching me solve a puzzle and wanted to try it. He went to the next one in the magazine and just started randomly filling the blanks with numbers. He didn’t get very far.
Trial-and-error is an illogical method for solving sudoku. Guessing, then going back if (and when) one hits a road block is time-consuming and downright impossible for a mere human mind to do.
I’ve actually written a computer program that will usually solve sudoku puzzles that are rated from very easy to medium. This is only possible because there is a definitive logical way to go about solving sudokus.
(There’s a logical method that I employ when solving medium and hard puzzle that I have yet to articulate into a computer program. But once I do, watch out!)
The publishers of Sudokus must have some sort of computerized rating method that determines what level of logic is necessary to solve a given puzzle. I imagine that if they’re making a puzzle and blanking out squares to make it harder, there comes a point at which the puzzle is absolutely unsolvable using logic. They they backtrack and make that puzzle “very hard”.
I’ve given sudoku puzzles to my math students as time fillers after they finish a quiz. I cringe when they just start filling in numbers from the upper left corner, then pronounce, “I give up” when they ultimately come to a point where they can’t place any more numbers that way.
I’d love to develop a “Logic” class where the objective is to learn various methods of logically solving puzzles. (Many classes offered in high school anymore ultimately teach the students how to learn in certain ways, not necessarily to learn the subject matter.) But I doubt such a “pure” logic class would pass the approval process for new classes.
There’s only a minimal logic in writing a ‘1’ in a square because there’s no ‘1’ in the 3x3 square surrounding it. Logic is writing in the ‘1’ because of the above reason, plus the fact that there are '1’s in other rows and colums that preclude them having '1’s elsewhere in a given 3x3 square.
I spent 3 months working on this question for my final undergrad Math project. I found a complicated one for 4X4 Matrices but my answer for a full Sudoku set was, “I don’t know”. Isn’t that a bitch. I read later on the Internet the worlds finest minds aren’t even sure whats the least amount of stating numbers to create a unique solution (17 for right now). I would have saved myself some time if I’d read how truly complex it is, but it was an interesting math exercise anyway.
There are two schools of thought. Early on, trial-and-error had quite a few proponents, nowadays not so many. The SudoCue Solving Guide gives a good idea of the issues. Myself, I won’t touch a puzzle that can’t be solved logically. BTW, from what I’ve read, programming a T&E solution by computer apparently is almost trivial for folks who know how to do such things. It’s a pretty small matrix, after all.
if there is only one possible valid solution for a set of sudoku numbers, there must be a logical means to find the solution.
keep in mind that trial and error is just another logic strategy. someone with a sufficiently powerful memory would be able to test each number for a particular square to its eventual contradiction (or accuracy) without ever writing anything down. is that person just using “trial and error”?
i bet you’re already using trial and error in many numbers you write in the puzzle, but the trial and error all happens in your brain.
I think we may be witnessing the birth of a new ‘Monty Hall’ or ‘Plane on treadmill’ hot button issue. This time it’s: 'Is ‘trial and error’ distinct from ‘logical process?’.
In the context of this dicussion, about solving Sudoku puzzles, I think what people mean is this:
A puzzle is said to have a logical solution if, at any given stage in the solving process, the solver is able to deduce from the information available the precise value that must be entered into at least one blank square, without the need to explore the consequences of different possibiities. If this condition is not satisfied, then the puzzle is not said to have a logical solution.
It’s the difference between being able to work out what number must go in a cell based on what you already know, as opposed to working it out by entering a value and then seeing if this leads to a contravention of the rules.
I think a more precise way to define “logical” is in terms of how deep one needs to explore. In other words, if entering the wrong number will lead to a contradiction either immediately or 1 number away, then the deduction can be done in one’s head and a new number can be entered right away.
On the other hand, if you enter the wrong number and might you need to take 10, 20 or more steps to reach a contradiction, then you might feel you are using “trial and error.”
So another way to ask the initial question is whether there is an upper bound on the maximum ply level necessary to solve a Sudoku puzzle that guarantees you won’t have to just about complete the puzzle to eliminate a possibility. The answer is “probably not.”
I always thought Sudoku puzzles weren’t supposed to depend on guesswork at any point, that you should always be able logically to deduce the next move somehow.
I’ve found one puzzle so far that actually had two solutions, which I thought was odd. There were four numbers – two sets of two adjoining numbers – that could have been interposed and still work. I think that was a fluke.
Arthur C. Clarke: “Any sufficiently advanced technology is indistinguishable from magic.”
I have taught a lot of computer classes over the years, with Theory of Computation being the most relevant here. The overwhelming majority of students seem to think that solving basic computer problems is “magic”. They just can’t seem to understand that there are non-magical mental processes involved in solving easy problems (like the ones they are assigned).
So it is not surprising to see a lot of people who think solving Sudokus is a matter of guessing. You just apply basic rules and have a deep “mental stack”. That is, you keep track of possibilities and try them out mentally, backing up when you see something may not work.
Note that it is far from random. Consider it like a chess player. They hardly do trial and error and searching for moves. Certain patterns are noticed, the most optimistic moves are explored first, etc.
One key method in problem solving in general is “take a break.” If you’re stuck, put it down. When you come back later you will be surprised to find something you hadn’t noticed before. (Which is why the worst students put off starting their homework to the night before.)
Note: Finding if a (possibly incorrect) Sudoku grid has at least one solution is NP-complete. Determining the unique solution to a grid relates to the class “UP” which is (probably) not the same as NP. Ergo, the way most people refer to solving a Sudoku as “NP-complete” is incorrect.
BTW, just because a problem is NP-complete (or even ExpTime-complete) doesn’t mean that small versions of the problem are all that hard. But it appears that even 9x9 Sudokus can be surprisingly hard. (Esp. ones that are harder than newspapers dare to use.)
I’ve seen a few puzzles like that. They aren’t flukes, just very poorly designed puzzles. IMO - If a puzzle doesn’t have a unique solution then its not worth solving. I threw away a book of Sudoku puzzles once when I discovered that one had multiple solutions.
The rating for Sudoku puzzles is based on the length of the inductive chain required to solve the puzzle logically.
Broadly:
A puzzle where you just have to figure out what number can go where based on the visible numbers is “Easy”.
A puzzle where you have to go “If this is X then that would have to be Y… but that can’t be Y, so X would have to be Z instead” is medium.
Hard puzzles will just chain together “If X, then Y, then Z, but it can’t be Z, so Y could be A in which case Z would be K instead, if it Z is K then A…” etc.
The hardest sudoku I know of has an 8 step inductive chain.
There are other factors like the number of starting clues and the relationships (block relations are easier than column/row relations are easier than block-column/row relations, etc that can feed into finer graduations of difficulty, but the inductive chain length is the defining factor (with further ranking for single longest chain, average chain, and total length)).
At least that’s what the ranking looks like in my experience.
What ianzin said. What I (and everyone I can recall having read) mean by solving logically is that one can articulate a specific valid reason for entering or excluding a value from a particular cell. That’s what the SudoCue and other solving guides are all about. Yes, T&E is logical in a broad sense (executable on a computer, for example), but not in the sense used by the sudoku community.
But the tricks Sudoku players use are nothing more than observed patterns which allow them to bypass trial and error processes. To take the most basic example, if eight of the cells in a row or square contain digits, you can enter the remaining digit without further thought. A minimalist algorithm might instead try all digits in that cell until it found one which did not violate the rules of Sudoku. It would not know the shortcut and would use trial and error instead.
Who’s to say that there isn’t an equivalent shortcut for all stages of any Sudoku game with a unique solution? In some positions, the shortcut might not be known, or might itself be too complex to be useful, and players might complain that trial and error is necessary. But it depends on the player.