Sudoku polynomial algorithm?
algorithm, complexity-theory, np-complete
Solution
Because the generalized Sudoku problem (with n2 × n2 grids) is NP-hard, if there were a known polynomial-time algorithm for solving Sudoku puzzles, it would prove P = NP. That would be a huge deal.
Something to keep in mind is that Sudoku puzzles as we know them are all 9 × 9 grids. As a result, when trying to measure the time complexity of solving a Sudoku puzzle, it actually isn't a good idea to use big-O notation because big-O notation talks about how an algorithm scales in the long term and all we care about is solving Sudoku puzzles of a fixed size. Restated differently, if you wanted to talk about a polynomial-time for solving Sudoku puzzles, you'd have to answer the question "polynomial in what variable?" If you're always solving a 9 × 9 Sudoku grid, the answer to that question isn't really clear.
Problem
I have a project to do for a complexity and problem solving course, and I've decided to base the project on Sudoku. From the research I've done, Sudoku is an NP-Complete problem (which is required for the project), and I've found a few ways of creating algorithms for it. I'm planning on doing a brute force solving method, and I need to do two other methods. I've found some ways, such as solving it as an Exact Cover problem, and I've found a paper that describes Sudoku as a SAT problem. But my question is this: Is there a proven polynomial solution for Sudoku? My teacher seems to think there was a "clever" solution by a "senior" gentleman about 5 years ago, but that's all he can remember. Does anybody know what this solution is, or what any other polynomial solution is? I'd appreciate any information or tips. Thanks!