Sudoku is Groovy

Last week I spent a bunch of time implementing Sudoku solving strategies in Groovy.  Actually a pretty interesting exercise, I thought.  Even the simple solving techniques/strategies require a bit of thought to generalize into code.  This might seems like a pointless exercise, but think of it a cross training.  Football players can't hope to compete without lifting weights, and developers can't hope to be at their peak without doing some heavy lifting as well.

I picked Groovy because it let me avoid so much of the boilderplate code you might have with Java, and gives you some really powerful syntactic constructs that are missing from CFML.  Data structure searching/manipulation is the task at hand, and the code reflects that without much extra cruft.  I did run into some issues with aboring .each { } "loops", so had to convert a number of those to for..in loops instead.  I prefer the 'each' syntax, but it's problematic with aborting iteration several levels deep since you don't have the equivalent of a method-return or a labeled-break construct.

I'm going to walk through some of these strategies, but first I'm going to present the general Sudoku framework I built.  It's founded on two main types (Board and Cell) with a number of anciliary types (BoardSpec, House, Row, Column, Block, Chute, Stack and Band), and the actual solving types (Strategy, Solver, TestRunner and Test).  Starting at the top, the "runner" script looks like this:

new TestRunner(new Solver([new GameRulesStrategy()])).test()

That'll create a new Solver with just the GameRulesStrategy, and then supply that to a TestRunner to run the test (using the Strategy's internal test case(s)).  Here's GameRulesStrategy:

class GameRulesStrategy implements Strategy {
  static getTests() {
    [new Test('900637100030001000107520300004810500019000820006059400002048705000200080001793006')]
  }

  boolean play(Board board) {
    def madePlay = false
    board.cells.each { c ->
      if (c.isKnown()) {
        c.houses.each { h ->
          h.findAll {
            ! it.isKnown()
          }.each {
            if (it != c) {
              madePlay = it.removeMark(c.value, this) || madePlay
            }
          }
        }
      }
    }
    madePlay
  }
}

The getTests() method returns a List of Test objects, which contain a BoardSpec and an optional 'check' Closure for when the test has passed (the default is when the board is solved).  The BoardSpec uses a board literal – an 81 character string representing the board's cells starting in the upper left, and moving to the lower right, exactly like reading an English-language page.  1-9 represent themselves, any other character (zeros in this case) represent blank cells.

The solving loop simply iterates over each strategy invoking play(Board) on each one in turn, where a play is either removing a mark from a cell, or setting a cell's value.  Cells with a single mark are automatically promoted to a "known" cell.  Any time a strategy makes a play, the loop starts back at the first strategy.  Itereration continues until every strategy fails to make a play (the test fails), or the board passes the check (usually being solved).

Raw code is available at https://ssl.barneyb.com/svn/barneyb/sudoku/groovy/trunk/ and requires Groovy 1.7 to run.  You should be able to export the code and run 'groovy driver.groovy' and have it.