Sudoku GameRulesStrategy

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.