There are some pretty complex “shortcuts” out there. A while back I got a book of puzzles ranging in difficutly from hard to fuggitaboutit. The book included three pages of rather obscure logic schemes which would allow you to remove a particular number as a possibility from a cell somewhere; you still had to follow up with more common schemes to solve any cell.
(The only way I’ve been able to work the more difficult puzzles in that book is to cheat; interesting, I often find that just one well-placed number will turn a brainbuster into a piece of cake.)
That is exactly right. Several times I’ve come back to a Sudoku after a break – later in the day or even the next day – to see something right away that I had missed before. It can be very surprising.
Imagine going to a party where you’re not guaranteed to know anyone. It might take you a while to scan the crowd and find someone you know, but if the hostess points to someone on the other side of the room, you can decide pretty quickly that she’s correct.
The same sort of distinction shows up when you’re trying to solve problems on a computer. There are problems where we can find a solution quickly, and there are problems where we can verify a solution quickly if someone gives us one. The first class of problems is known as P, and the second as NP.
NP-complete problems are the hardest problems in NP in the sense that if you have a program that solves any NP-complete problem, you can use it to solve any problem in NP without needing too much extra time (in the same sense that any problem in P can be solved quickly). As it turns out, there are a lot of interesting problems in NP–simple things like adding numbers together or sorting lists, but also complicated problems like breaking the encryption used to transmit credit card numbers across the internet. So if you had a program that could solve arbitrarily large Sudokus, you could bring a large part of the modern economy to a grinding halt.
If a program like that exists, then every NP-complete problem can be solved quickly, and P = NP. We think that the two classes of problems are unequal, and that NP-complete problems take more time to solve than anything in P, but no one knows for sure. It’s still possible that P = NP (although I don’t think anyone seriously believes that), and if you can find a proof either way, there’s a $1000000 prize attached. I’m not holding my breath for anyone to win it any time soon.
In layman’s terms, if a puzzle is NP-Complete, it means that as far as anyone knows, there is no general, efficient way to solve it. As far as anyone knows, in the worst case scenario, all you can do is try different possible solutions until you get the right one.
Also, if a puzzle is NP-Complete, once you do get the right answer, you can easily verify that the answer is correct.
edit - those are all assuming a 9 x 9 grid; an n x n solver would probably be a little bit longer but not by much - it’s mostly the trouble of formatting the sequence.
That’s the way poorly made “hard” puzzles work. They really only have one multi-level relationship you have to figure out and the rest is fill-in-the-blanks easy.
This is the sort of quick non-technical description usually given of P and NP, but I don’t like it for various reasons; mainly, the problem you’ve described (presumably, something like: either find someone in the crowd you know, or conclude that there is none) doesn’t, in that form, really seem to be either P or NP, as P and NP apply only to strictly yes/no questions. And if we do look at the induced yes/no problem (is there someone in the crowd you know?), it is in some sense NP, but not because the answer, in itself, is quickly verifiable (if the hostess said “The answer is ‘yes’, there is someone in this crowd you know”, it wouldn’t be easy to tell if she was right or not). It’s because, if the answer is yes, then there exists some quickly verifiable witness to this fact (though the witness may be hard to find).
I mean, these sort of analogies aren’t entirely off; it’s just that they don’t usually describe P vs. NP so much as (something like) FP vs. FNP. Luckily, for one of the main reasons people discuss P and NP, it’s no big deal, as P = NP iff FP = FNP.
I thought I’d revive this thread since I just did my first Sudoku puzzle last week. How many possible solutions can there be for a 9x9 grid? There must be an upper limit. I understand that a fixed number of solutions does not necessarily demand a fixed number of puzzles, as I’m reasonably sure a single solution could be reached from many different starting points.
Reviving this old thread because I found something recently that answers my original post: This Sudoku puzzle World's hardest sudoku: can you crack it? is advertised as being (among) the world’s hardest, and I believe it. I see NO local clues at all to solving it; apparently it can only be solved by an elimination process of following multiple paths to dead ends until the sole valid path is uncovered.
And to answer a nearly decade-old question, there is definitely an upper limit to both the number of solutions and to the number of puzzles. In fact, I can confidently state that there are no more than 10^81 different possible puzzles, even without considering any of the many symmetries that apply, and I’m confident that the upper bound is much lower than that.
Indeed. The number of different solutions, when symmetries such as rotation, reflection, permutation, and relabeling are taken into account, is 5,472,730,538. (From the Wikipedia.)
No, a puzzle has ten possible states for each of the 81 cells: It can be filled in with any digit 1-9, or it can be blank. The actual number probably is less than 9^81, because of all of the constraints, but the only way to be sure of that would be to take some of the constraints into account and re-calculate, which process would yield an even lower bound.
