Sudoku HiddenSingleStrategy

The next Sudoku solving strategy I want to dig into is called "hidden single".  Here's the implementation to start with:

class HiddenSingleStrategy implements Strategy {

  static getTests() {
    [
      new Test(
        '0' * 9 + '000200000' + '0' * 9 + '000060000' + '0' * 9 + '000080000' + '0' * 9 * 2 + '000002000',
        {
          def cell = it.getCell(5, 5)
          cell.isKnown() && cell.value == 2
        }
      )
    ]
  }

  boolean play(Board board) {
    for (h in board.houses) {
      for (n in 1..9) {
        def cells = h.findAll {
          ! it.isKnown() && it.hasMark(n)
        }
        if (cells.size() == 1) {
          // we found a hidden single
          cells[0].setValue(n, this)
          return true
        }
      }
    }
    false
  }

}

As you can see, the test is a little different than for GameRulesStrategy.  Before I just supplied a board and a successful test was when the board is solved.  In this case I'm just checking for if cell (5, 5) is known and it's value is 2 (no need to solve the whole board).

The strategy itself is pretty simple: for every house, for every number, see if any cell is the ONLY cell in the house that can contain the number, and if so, set that cell to that number.  Once we find a cell to set, the method exits (returning true) and does not continue the search.  This is the reason for the 'for' loops instead of the Groovy 'each' iterator.  This lets GameRulesStrategy "clean up" the board before continuing the search.  In this case it's probably not a big deal, but with the more complex strategies this is an essential optimization.

Comments are closed.