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.

3 responses to “Sudoku Anyone?”

  1. Remy Becher

    There was an execellent article on the "science behind Sudoku" in July issue of Scientific American, with more strategies, worth reading.

  2. Tiffany Boisvert

    hey oh my gosh my last name is boisvert as well. most of my family lives in Quebec that i know of and my grandfather who past away when my father was 16 was put up for adoption then adopted by his biological parents..
    we have been trying to find history on the boisvert family for ages maybe you know?
    tiffany boisvert

  3. Barney

    Hey Tiffany,

    Sadly, I don't really know much of our family history. My dad's parents were born in Quebec and migrated to Maine early in life, where my father (and his siblings) was raised. Beyond my grandparent's I know almost nothing.

    Sorry I couldn't be of more help, but best of luck on your search!