How Sudoku could win you a million dollars
Puzzle by Tim Stellmach (public domain) and solution by Cburnett (CC BY-SA 3.0)
If you’ve never played Sudoku, head over the Sudoku.com and give it a try! The Japanese logic game involves filling a large grid of numbers 1 through 9 in a way that no row, column, or smaller 3-by-3 grid contains duplicates. Not only is the game addictive and fun; a clever sudoku strategy could be the key to winning a million dollar prize! That’s a bold statement, and I promise you it’s true. But; you’ll have to read this entire post to find out how.
The Millennium Problems
Let’s turn the clock back 17 years, to the end of 1999. The new millennium was about to begin. At the recently-founded Clay Mathematics Institute, a committee of leading mathematical scientists decided to mark the imminent temporal milestone by compiling a list of seven great unsolved problems of classical mathematics. These are the Millennium Prize Problems. The prize for the solution to any of the seven problems? One million US dollars.
Would you study math for this?
Picture by trontnort via flickr (CC BY-NC 2.0)
We’ve all been solving maths problems since primary school, what makes these ones worth a million bucks? Well, for one thing, reading the formal descriptions of most of these problems virtually requires a Major in Pure Mathematics. The very names of the problems are too intimidating to include in a blog post written for a general audience, such as this one. What’s more, to this day, only one of the problems has been solved. For some of the others, the solution has eluded the world’s mathematicians for over a century.
Okay, so how are we going to get our hands on that sweet million if we can’t even comprehend the questions the Millennium Problems are asking? Lucky for us, this difficulty applies to all of the problems except for one. Its name isn’t long or scary, and you can explain it to someone without their eyes glazing over. It’s actually a problem on the boundary of maths and computer science. And this is where Sudoku comes in!
The Sudoku Problem
If you’ve read my previous blog posts, you already know that computer science is all about problem-solving. But, despite how fun they are to solve, computer scientists aren’t writing papers about the specific Sudoku puzzles they complete on the train home. Instead, computer scientists are interested in methods of solving the puzzles, without knowing what the grid looks like in advance.
The problem of solving a Sudoku puzzle is special. It’s very easy to quickly check a solution (you can just count the numbers in each row, column, and section), but finding a solution from scratch might take a lot longer. To this day, the best methods we know for solving Sudoku puzzles essentially amount to systematically trying all possibilities.
Solving a Sudoku by trying all possibilities, starting from the top left.
Animation by Simpsons contributor via Wikimedia Commons (CC BY-SA 3.0)
The Sudoku Problem is in a group of problems called NP problems. At the risk of losing you after you’ve come this far, NP stands for ‘Nondeterministic Polynomial’, and it just means what we said before: you can quickly verify a correct solution, but finding one essentially requires trying lots of different options. Contrast this with P (Polynomial) problems, which can be solved quickly, too.
NP problems include many other important problems a bit more directly applicable to real life than Sudoku puzzles, including protein folding, the Travelling Salesman Problem, and countless other problems we can verify quickly, but don’t know how to solve quickly. P problems include easier problems with known, fast solutions, like sorting.
P versus NP (this is the part where I explain how solving a Sudoku could win you one million dollars like I promised)
That brings us back to the Millennium Problems. Give it up for the one with the shortest name and most accessible explanation: P versus NP! This problem simply asks the question: is there an efficient way to solve NP problems, just like P problems?
Venn Diagrams! If NP problems can be solved quickly like P problems, P and NP would actually be the same group of problems. This is the P versus NP question.
Author’s own image.
How can a faster Sudoku-solving strategy help answer this problem? This is the final piece of the puzzle. Sudoku is actually what’s called an NP-Complete problem. That is, computer scientists have discovered links between the Sudoku problem and every other NP problem. It turns out all the work you are doing trying different possibilities and selecting the choices that satisfy the rules of the grid is essentially the same core challenge making these other tough problems take so long. That means if you have a more efficient strategy for finding a Sudoku solution, the same strategy can be used to solve any other NP problem efficiently, as well.
So a fast Sudoku-solving method is literally a fast method for every other NP problem! Using this method, you could quickly find solutions for any NP problem. That means P and NP would be the same group of problems, and that would be the answer to the P versus NP Millennium Prize Problem. The prize would be yours! Just like I promised. So, if you think you have a faster-than-ever strategy for solving Sudoku puzzles, let me know, okay?