BarneyBlog

A couple days ago I posted about implementing a Sudoku solver in Groovy as a sort of cross-training exercise, and promised to delve into the strategies a bit more.  So here's GameRulesStrategy:

class GameRulesStrategy implements Strategy {

  static getTests() {
    [
      new Test(
        '900637100030001000107520300004810500019000820006059400002048705000200080001793006'
      )
    ]
  }

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

}

As with all strategies, it starts with test cases that exercise the strategy: in this case a single board that can be solved by application of the rules alone.  That board spec, just for reference, describes this board:

+-------+-------+-------+
| 9     | 6 3 7 | 1     |
|   3   |     1 |       |
| 1   7 | 5 2   | 3     |
+-------+-------+-------+
|     4 | 8 1   | 5     |
|   1 9 |       | 8 2   |
|     6 |   5 9 | 4     |
+-------+-------+-------+
|     2 |   4 8 | 7   5 |
|       | 2     |   8   |
|     1 | 7 9 3 |     6 |
+-------+-------+-------+

There are three things a strategy can do when asked to play: remove a mark from a cell, set a cell's value, or nothing.  It's up to the strategy to determine if doing several of them at once is appropriate or not.  And keep in mind that a cell with only one mark remaining is implicitly set to that value, so removing a mark can actually set a cell's value behind the scenes.

For GameRulesStrategy, we're only concerned with removing marks from cells, and we can do many of them in a single pass without stepping on our own toes.  We start by asking the board for all the cells, and then grabbing only the known ones.  Then we iterate over those cells, and for each one get the cell's houses (the row, column, and block the cell is in), flatten them into a single collection, and find all the other cells that aren't know.  Finally we iterate over those cells and remove the mark from each of them, keeping track of whether it actually did anything in the 'madePlay' variable.

If you're interested, this same algorithm can be implemented with for..in loops, instead of .each { } constructs, which is a technique I've used in later strategies where the closures get "in the way" of returning from the method early.  Here's the loop based implementation (minus the tests):

class GameRulesStrategy implements Strategy {

  boolean play(Board board) {
    def madePlay = false
    for (c in board.cells.findAll {
      it.isKnown()
    }) {
      for (it in c.houses.flatten().findAll {
        it != c && ! it.isKnown()
      }) {
        madePlay = it.removeMark(c.value, this) || madePlay
      }
    }
    madePlay
  }

}

If you're wondering, the loop performs marginally faster (<1%) than the iterator, but I find it to be a bit less readable, so I generally prefer the iterator approach.  If performance is paramount, Groovy is probably the wrong choice – it's forte is concise, readable code (and therefore development throughput) not CPU throughput.  People are more expensive than machines in most cases, and certainly this one.

This is a really simple strategy, but there are plenty more complicated ones to come, so stay tuned.

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.