Sudoku Anyone?

For my birthday last month, Heather (my wife) got me a book of Sudoku puzzles.  If you like puzzles and haven't tried Sudoku, highly recommended.  Simple and fun.

However, being the good computer geek that I am, I quickly decided that it'd be a heck of a lot easier to let the computer solve them for me.  Note that this is not cheating.  Since the computer can't do anything I don't tell it to do, I'm still solving the puzzles; the computer must exhibit a subset of my Sudoku prowess.  However, it does have far better "bookkeeping" abilities, which is a marked advantage.

I built it as a simple JUnit-driven Java 5 application.  It's pretty basic: 20 types, plus a few nested types.  It leverages the Strategy pattern for implementing strategies, so adding a new strategy is as simple as implementing the Strategy interface (probably by extending AbstractStrategy) and registering the implementing class as a known strategy.

What was particularly interesting, however, was that the program was able to solve one- through four-star puzzles (five stars is the most difficult) with just two simple strategies:

1. Checking to see if any given unit (a row, column, or block) has only one cell that can contain a given number, which means that cell must contain the number in question.
2. Checking to see if all cells in a given unit that can contain a given number are also within a second unit, which means the rest of the second unit can't contain the number in question.

I've no idea how difficult the puzzles are in the overal universe of Sudoku, but it was surprising to me that those two simple strategies were so effective.

I should mention that the rule of the game (each number is present exactly once in each block) is enforced by the system itself, and was usually enough to solve the one-star puzzles.  So you might consider the rules themselves to be strategy zero as they are effective in their own right.