Computer Sciency stuff…

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.

This entry was posted in Uncategorized. Bookmark the permalink.

6 Responses to Computer Sciency stuff…

  1. Jeroen says:

    Why don’t I get to those kinds of things “in the line of duty”? :'(:P

  2. Vineet says:

    Neat looking view. How did you create the board? Are you using GEF/Draw2D or somehow using SWT? – I need to actually implement something similar looking.Thanks!Vineet

  3. Stephen Denne says:

    Knuth’s Dancing Links Algorithm is very fast at solving Sudoku. A java implementation is here: reports solutions to a partially filled in grid to a solution listener. It takes a little reading, and code investigation, to get your head around it.I was considering using it to create a Sudoku generating application (a GUI for manually creating puzzles) to quickly confirm the puzzle was unique (or to report the number of solutions), along with other algorithms to rate difficulty, solving techniques required, etc.

  4. Dave says:

    Vineet,I don’t know how Wayne did it, but you can easily do stuff like that in SWT using addPaintListener().Dave Orme

  5. Wayne says:

    I looked at GEF, but decided that I didn’t need most of what it provides. What I’m drawing is so simple that I just draw it myself using SWT.

  6. Vineet says:

    Wayne, Dave, Thank for the information. – Vineet

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s