It’s only every once in a while that I really get to geek out and use some of that computer science stuff I learned in university. Frankly, I quite enjoy these little opportunities (disturbingly, most of these opportunities have something to do with combinatorics and recurrence equations).
Yesterday, I wrote a recursive backtracking algorithm for solving Sudoku puzzles. It’s a pretty simple thing (only about a dozen lines of code in addition to all the code that implements the actual puzzle board) but it works. And it works well. I use it to both solve an existing puzzle and to create new ones. Unfortunately, it’s not all that smart and, while it oftentimes takes less than a second to solve a puzzle, sometimes it takes several minutes. I have some thoughts on how to speed it up that I’ll explore over the next few days.
I built the solver because I need to generate puzzles for a Sudoku game that I’m building with Maria, my co-op summer student, using Eclipse Rich Client Platform. It’s taken about two days to get most of the game working and now, we’re working on finishing touches. Here’s what it looks like so far:
As you hover over a cell, it shows you the values that could possibly go in that cell; you simply type a digit to set the value in the cell under the cursor. At some point, we’re going make a preferences selection to turn on or off the hints. We’re also going to add a feature to optionally highlight invalid rows, columns, and boxes. There’s already a lot of cool features in the implementation that I’ll likely blog about later this week and next.
As of now, the Sudoku game is just a collection of plug-ins that I’m testing in the Eclipse workbench. I’ll turn it into a proper RCP application sometime later this week. That should end up being a pretty simple exercise since most of the heavy-lifting is already done.
