A Sudoku solver in Scala

Sudoku.scala

package sudoku

case class Location(row: Int, col: Int) {
  def areValuesMutuallyExclusive(other: Location, size: Int) =
    isInSameRow(other) ||
      isInSameColumn(other) ||
      isInSameSmallSquare(other, size)

  private def isInSameRow(other: Location): Boolean = row == other.row

  private def isInSameColumn(other: Location): Boolean = col == other.col

  private def isInSameSmallSquare(other: Location, size: Int) = {
    val smallSquareSize = Math.sqrt(size).intValue
    row / smallSquareSize == other.row / smallSquareSize &&
      col / smallSquareSize == other.col / smallSquareSize
  }
}

object Puzzle extends App {
  type Solution = Map[Location, Int]
  type Puzzle = Map[Location, Option[Int]]

  val problem = List(
    n(2) :: ____ :: ____ :: n(1) :: ____ :: n(6) :: ____ :: ____ :: n(5) :: Nil,
    ____ :: ____ :: ____ :: n(2) :: ____ :: ____ :: ____ :: n(7) :: ____ :: Nil,
    ____ :: n(5) :: ____ :: ____ :: ____ :: ____ :: n(1) :: n(2) :: n(4) :: Nil,
    ____ :: ____ :: ____ :: ____ :: ____ :: ____ :: n(6) :: ____ :: ____ :: Nil,
    ____ :: ____ :: ____ :: n(3) :: n(8) :: n(9) :: ____ :: ____ :: ____ :: Nil,
    ____ :: ____ :: n(4) :: ____ :: ____ :: ____ :: ____ :: ____ :: ____ :: Nil,
    n(7) :: n(2) :: n(6) :: ____ :: ____ :: ____ :: ____ :: n(3) :: ____ :: Nil,
    ____ :: n(8) :: ____ :: ____ :: ____ :: n(3) :: ____ :: ____ :: ____ :: Nil,
    n(1) :: ____ :: ____ :: n(6) :: ____ :: n(4) :: ____ :: ____ :: n(8) :: Nil)

  val start = System.currentTimeMillis
  val solution = solve(problem)
  val end = System.currentTimeMillis

  println(solution.size + " solution(s) found in " + (end - start) + " milliseconds")
  println
  solution.foreach(render(_))

  private def render(solution: Solution) {
    for ((_, row) <- solution.groupBy(_._1.row).toList.sortBy(_._1)) {
      for (col <- row.toList.sortBy(_._1.col))
        print(col._2 + " ")
      println
    }
    println
  }

  private def ____ = None
  private def n(v: Int) = Some(v)

  private def solve(puzzle: List[List[Option[Int]]]): Set[Solution] = {
    val valueByLocation = Map() ++ locations(puzzle.size).map(location => location -> puzzle(location.row)(location.col))
    solveIndexed(valueByLocation, puzzle.size)
  }

  private def solveIndexed(puzzle: Puzzle, size: Int, solutions: Set[Solution] = Set()): Set[Solution] = {
    val emptyCells = puzzle.filter(!_._2.isDefined)
    if (emptyCells.isEmpty)
      solutions + puzzle.map(lv => lv._1 -> lv._2.get)
    else {
      val numbersAvailableByEmptyCell = emptyCells.map(emptyCell => (emptyCell._1, numbersAvailable(size, puzzle, emptyCell._1)))
      val (emptyCell, availableNumbers) = numbersAvailableByEmptyCell.toList.sortBy(_._2.size).head
      if (availableNumbers.isEmpty)
        solutions
      else
        availableNumbers.flatMap(number => solveIndexed(puzzle + (emptyCell -> Some(number)), size, solutions))
    }
  }

  private def numbersAvailable(size: Int, puzzle: Puzzle, emptyCellLocation: Location) = {
    val allNumbers = (1 to size).foldLeft(Set[Int]()) { (acc, v) => acc + v }
    val fullCells = puzzle.filter(_._2.isDefined).map(t => t._1 -> t._2.get)
    val numbersExcluded = fullCells.filter(full => full._1.areValuesMutuallyExclusive(emptyCellLocation, size)).map(_._2).toSet
    allNumbers.filterNot(numbersExcluded.contains(_))
  }

  private def locations(size: Int) = {
    val indexes = (0 until size)
    for (row <- indexes; col <- indexes) yield Location(row, col)
  }
}