How Sudoku could win you a million dollars

An empty and full sudoku gridPuzzle 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.

a million dollars, pile of cashWould 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.

animation of sudoku solverSolving 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 of P vs NPVenn 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?


8 Responses to “How Sudoku could win you a million dollars”

  1. Matt Farrugia says:

    Thanks for reading, and let me know how that goes, Nelson!

  2. Nelsongc says:

    This was very well explained Matt. 1 million dollars, it’s almost worth devoting my swotvac period to instead of studying. XD Another great article. 🙂

  3. Matt Farrugia says:

    Hey Nam! Thanks so much for reading. I hope it’s bringing back good memories from last semester’s exam period. Good luck with your exams this semester!

  4. namn1 says:

    Hey Matt,

    I love reading about this after the discussion in your tutorial class and studying for it in exam last semester lol.
    The click bait absolutely works as well, honestly don’t think I’ve read on without the $$$. Nice work there Matt.

  5. Matt Farrugia says:

    Hey Mei! Thanks for reading through, despite the clickbait!

    I am sure you will hear about it if someone discovers such a strategy, and proves that P=NP. It’s probably the biggest open problem in computer science right now. And as evidenced by its inclusion on this list, it’s one of the most important maths problems today, too. The consequences of a strategy like this would result in a complete revolution of the world of problem solving. Being able to solve a problem as quickly as you can recognise a correct solution is a truly magical ability. I believe Scott Aaronson from MIT says it best:

    “If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss”

  6. Mei says:

    Love the title, love the hyperlinking of “the formal descriptions of most of”. It makes sense now. I love sudokus and I use the same strategy regardless of the difficulty level, which is I guess why harder sudokus take longer to solve? I would also love to know if someone discovers this magical strategy.

  7. Matt Farrugia says:

    Thanks again for reading, Felicity!

    I can only speak from my own experience solving Sudoku puzzles, but in my experience ‘the human strategy’ is at least trying most possibilities! One difference is that we don’t write down all of the possibilities as we are thinking about them, a lot of the processing goes on inside our heads — we can think two or three steps ahead without putting them onto the page.

    The other (more telling) difference is that humans don’t start with the top-leftmost empty square, but instead we look for any squares that only have one possible answer. These squares are a sure-thing, and they save us having to backtrack later (which the computer doesn’t mind doing, but sucks for humans using a pencil and eraser). The tradeoff is that we spend a lot more time looking for these ‘sure-thing’ squares — and when there aren’t any freebies left, we have to resort to making a guess in a cell that only has two or three possibilities. In the end, we’re following the same strategy, but in a different order.

    These differences are sensible and they do speed up computer programs, but they aren’t enough to bring Sudoku down from an NP problem into a P one.

  8. Felicity says:

    Oh, you tricked me into reading about maths using money! Just kidding! I like maths, even though I’m not that interested in doing it – even for $1 million.
    I find it very interesting though that computers don’t copy the human strategy for solving Sudoku. Trying every solution is such a computer thing to do. I wonder how hard it would be to code other problem solving strategies.