Simple sudoku solvers based on scala streams

BoxMappedSudoku.scala

package sudoku

class BoxMappedSudoku {

  val EmptyValue = '0'
  val MaxValue = 9

  val allValues = "123456789".toList
  val indexes = (0 to 8).toList
  val boxCoordinates = (0 to 2).toList  
  
  def getX(pos: Int): Int = pos % MaxValue
  def getY(pos: Int): Int = pos / MaxValue

  def box(pos: Int): List[Int] = {
    def base(p: Int): Int = (p / 3) * 3

    val x0 = base(getX(pos))
    val y0 = base(getY(pos))
    val ys = (y0 until y0 + 3).toList
    (x0 until x0 + 3).toList.flatMap(x => ys.map(x + _ * 9))
  }

  val boxes = boxCoordinates flatMap (x => boxCoordinates map (x * 3 + _ * 3 * 9)) map box

  class Board(val game: String) {
    val empty = game indexOf EmptyValue
    val isDone = empty == -1

    def updated(pos: Int)(value: Char): Board = new Board(game updated (pos, value))

    def row(y: Int): List[Char] = indexes map (col => game(y * MaxValue + col))
    def col(x: Int): List[Char] = indexes map (row => game(x + row * MaxValue))
    def box(pos: Int): List[Char] = (boxes filter (_ contains pos)).head map game

    def toAvoid(pos: Int): List[Char] = (col(getX(pos)) ++ row(getY(pos)) ++ box(pos)).distinct
    def candidates(pos: Int): List[Char] = allValues diff toAvoid(pos)

    def next: Stream[Board] = candidates(empty).toStream map updated(empty)

    override def toString: String = "\n" + (game sliding (MaxValue, MaxValue) mkString "\n")
  }

  def build(game: String): Board = new Board(game)

  def from(path: Stream[Board]): Stream[Board] = path match {
    case h #:: t => h #:: from(t ++ h.next)
    case _ => Stream.empty
  }

  def steps(game: String): Stream[Board] = from(Stream(build(game)))

  def solve(game: String): Board = steps(game).filter(_.isDone).head

}

play.sc

package sudoku

object play {
  val sudoku = new Sudoku                         //> sudoku  : sudoku.Sudoku = sudoku.Sudoku@7e8bf0
  
  val sample = "651702090" + "030416257" + "742500006" +
  		"000040562" + "460125038" + "523860000" +
  		"285694371" + "004378625" + "376251849"
                                                  //> sample  : String = 651702090030416257742500006000040562460125038523860000285
                                                  //| 694371004378625376251849

  //sudoku.solve(sample)
  val game = "100459000" + "803070900" + "000008000" +
  		"508002600" + "900060007" + "007900105" +
  		"000200000" + "006080204" + "000594003"
                                                  //> game  : String = 10045900080307090000000800050800260090006000700790010500020
                                                  //| 0000006080204000594003
  
  //sudoku.solve(game)
  
  val hardGame = "014060300" + "620004009" + "080050600" +
  		"060200003" + "070010050" + "500009060" +
  		"006020030" + "100500092" + "007090410"
                                                  //> hardGame  : String = 0140603006200040090800506000602000030700100505000090600
                                                  //| 06020030100500092007090410
  sudoku.solve(hardGame)                          //> res0: sudoku.play.sudoku.Board = 
                                                  //| 714962385
                                                  //| 625834179
                                                  //| 389157624
                                                  //| 961285743
                                                  //| 472613958
                                                  //| 538749261
                                                  //| 896421537
                                                  //| 143576892
                                                  //| 257398416

  val optimizedSudoku = new BoxMappedSudoku       //> optimizedSudoku  : sudoku.BoxMappedSudoku = sudoku.BoxMappedSudoku@1d8add3
  optimizedSudoku.solve(hardGame)                 //> res1: sudoku.play.optimizedSudoku.Board = 
                                                  //| 714962385
                                                  //| 625834179
                                                  //| 389157624
                                                  //| 961285743
                                                  //| 472613958
                                                  //| 538749261
                                                  //| 896421537
                                                  //| 143576892
                                                  //| 257398416|
  
}

Sudoku.scala

package sudoku

class Sudoku {

  type Position = (Int, Int)
  val EmptyValue = '0'
  val MaxValue = 9

  val allValues = "123456789".toList
  val indexes = (0 to 8).toList

  class Board(val game: String) {
    val empty = game indexOf EmptyValue
    val emptyPosition = (empty % MaxValue, empty / MaxValue)
    val isDone = empty == -1

    def updated(pos: Int, value: Char): Board = new Board(game updated (pos, value))

    def row(y: Int): List[Char] = indexes map (col => game(y * MaxValue + col))
    def col(x: Int): List[Char] = indexes map (row => game(x + row * MaxValue))
    def box(pos: Position): List[Char] = {
      def base(p: Int): Int = (p / 3) * 3

      val x0 = base(pos._1)
      val y0 = base(pos._2)
      val ys = (y0 until y0 + 3).toList
      (x0 until x0 + 3).toList.flatMap(x => ys.map(y => game(x + y * MaxValue)))
    }

    def toAvoid(pos: Position): List[Char] = (col(pos._1) ++ row(pos._2) ++ box(pos)).distinct
    def candidates(pos: Position): List[Char] = allValues diff toAvoid(pos)

    def next: Stream[Board] = candidates(emptyPosition).toStream map (c => updated(empty, c))

    override def toString: String = "\n" + (game sliding (MaxValue, MaxValue) mkString "\n")
  }

  def build(game: String): Board = new Board(game)

  def from(path: Stream[Board]): Stream[Board] = path match {
    case h #:: t => h #:: from(t ++ h.next)
    case _ => Stream.empty
  }

  def steps(game: String): Stream[Board] = from(Stream(build(game)))

  def solve(game: String): Board = steps(game).filter(_.isDone).head
}