Cuckoo For Sudoku

Sudoku is one of the latest crazes to hit the web (and newspapers, and airport bookstores…), and so far I’ve solved dozens of them.

Well, okay, I didn’t solve them myself…

Instead I’ve been more interested in writing code that solves them. There’s a detailed explanation of the theory behind it on Wikipedia, using math I’ve long since forgotten, but there’s always the brute force method of trying every possible value in every possible location until you get the solution. I wanted to try a slightly different approach though, and use algorithms that more closely approximated how I’d go about solving it myself as I’d sit there staring at the puzzle. After doing a few of them, I found that I’d generally follow two tactics:

1) Go row by row and column by column and see if each location only has one possible value it could be. E.g., if a row is already filled by everything but 3 and 8, see if putting those values in the empty cells conflicts with anything else in their columns.

2) Within each 3×3 subregion, look for spots that can be the only possible location of a value, based on conflicts within the rest of the row and column.

I quickly cobbled together a simple program that would try these methods against a board, alternating between each method until either no further values could be found these ways or the board was solved.

It was indeed able to solve some of the puzzles I fed into it, but others it could only partially solve. Sudoku puzzles are available in a variety of difficulty levels and my methods so far only worked against the easier ones. Some progress is still better than no progress though, and these partially solved boards could still be completed under the brute force method.

In some cases there is even a significant performance benefit to combining tactics like this. One board that was classified as ‘hard’ took 2.2 CPU seconds of time to solve by brute force alone, but when the above algorithms are applied to it first, the total CPU time needed dropped to 0.12 seconds.

There’s still room for improvement though, and as I sharpen my own skills I hope to come up with ‘human’ algorithms that will reliably provide solutions without having to resort to brute force.

(The crummy code I have so far. This is quick and dirty, so try not to judge too harshly… :-P)