The Sudoku Challenge

I started doing sudoku in 2005. It was usually in the paper, and I was bored, so I decided to give it a try. I became hooked. As I became more obsessed, I began to wonder to myself, if I could find a way to look at a sudoku problem, and solve it instantly. I thought it was possible, because it has the following properties:

• A sudoku puzzle is an nxn matrix (square)
• All columns and rows add up to the same number: 45
• It is a latin square

So I started trying all sorts of things, to see if a method existed to solve it. I even wrote a guide on how to solve it by pen and paper. Exasperated, I went and talked to my math professor. He told me point-blank, “boy, its not possible, but if you can figure out a way to do it, you’ll be a millionaire!” You see, the problem of solving a sudoku problem is NP-Complete.

Let me explain a little bit about NP-complete problems. They are a type of problem who’s answer can be checked and verified very quickly, but actually coming up with that answer would take quite a long time (I know, I know, deterministic Turing machine, but that would require 2 more definitions and like 4 more paragraphs!) There’s another set of problems that are “Polynomial”, meaning they CAN be solved fairly quickly. All the NP-complete problems are linked to one another, so if you can figure out how to do one in Poly-time, then you can do them all in Poly-time.  However, if you do manage to figure out that algorithm, then you’ve essentially solved the “P vs NP” problem, a “Millennium Prize” problem, netting you $1 million.

So imagine my surprise today, upon reading the Toronto Star, and seeing that an “academic finally cracks the Sudoku code“! I didn’t really believe it, so I checked out the paper. Here’s the algorithm:

1. Find all forced numbers in the puzzle
2. Mark up the puzzle
3. Search iteratively for preemptive sets in all rows, columns, and boxes, taking appropriate crossout action as each new preemptive set is discovered -until
4. either
   a) a solution is found or
   b) a random choice must be made for continuation
5. If 4a), then end; if 4b), then go to step 3.

This is actually the same algorithm I use when I am doing it myself. So, let me reword it for you:

1. Find all the obvious ones (forced, meaning those numbers can go no where else)
2. Now in each square, list all the possible numbers that can go there and write it in that box (the mark ups)
3. Look at the entire puzzle, go through the mark ups, and see which ones cancel each other out. Do this until
4. You end up with squares with only one mark up left (thus it must be the solution) or squares where you have to guess (usually two choices).
5. If there’s only one mark up, that’s the solution. Else, go back to step 3.

If you ever played Nintendo’s Brain Age, their game allows you to use the same system of “markups”, so really, the algorithm is just what people would be doing anyways:

Ram Murty, a Queen’s University mathematics professor who has read the paper – “Pen-and-Paper Algorithm for Solving Sudoku puzzles” – said Crook has “codified what the average mind does when it looks at a Sudoku problem.”

The algorithm doesn’t even do anything to solve the “P vs NP” problem, since this is just a sudoku puzzle of size 9×9. Once you move to bigger ones, it takes longer and longer, which defeats the purpose!  As well, the article brags that the “Sudoku Code” has been cracked, despite the existence of other algorithms to solve sudoku.

I got bored of sudoku a while back, but maybe I’ll try to program a sudoku-solver. Sounds fun.