Sudoku solver in scala. Doesn't quite work; it repeatedly finds the same solutions instead of only finding each unique solution once.

Sudoku.scala

object Sudoku extends App {

  val ints = (1 to 9).toSet

  val start = List(
    0, 0, 0, 0, 0, 0, 0, 6, 0,
    0, 0, 0, 0, 5, 3, 0, 0, 9,
    5, 2, 0, 0, 0, 8, 0, 1, 0,
    0, 0, 1, 0, 6, 0, 0, 2, 4,
    2, 0, 0, 0, 0, 0, 0, 0, 8,
    3, 9, 0, 0, 1, 0, 6, 0, 0,
    0, 7, 0, 3, 0, 0, 0, 8, 1,
    9, 0, 0, 2, 8, 0, 0, 0, 0,
    0, 3, 0, 0, 0, 0, 0, 0, 0).map(n => if (n > 0) Some(n) else None)

  println(iterate(start).take(1))

  def iterate(board: List[Option[Int]]): List[List[Option[Int]]] = {
    val unsolved = board.contains(None)
    if (!unsolved) {
      fanfare(board);
      List(board)
    }

    val (solvedCells, possibilities) = board.zipWithIndex.filter(_._1.isEmpty).map(x => (getPossibilities(x._2, board), x._2)).partition(_._1.size == 1)

    if (!(possibilities ++ solvedCells).exists(_._1.isEmpty)) { // make sure we have some options to try

      // swap in all the cells that we now have a definite answer for
      val updatedBoard = solvedCells.foldLeft(board)((b, t) => b.updated(t._2, Some(t._1.head)))

      // now recursively try all of the possible replacements.
      for {
        p<-possibilities;
        i<-p._1
      } yield {
        iterate(updatedBoard.updated(p._2,Some(i)))
      }.flatten
    }
    else{// else this branch is insoluble; stop and continue with other options
      List()
    }
  }

  def getPossibilities(pos: Int, board: List[Option[Int]]): Set[Int] = {
    rowPossibilities(pos, board).intersect(colPossibilities(pos, board)).intersect(boxPossibilities(pos, board))
  }

  def rowPossibilities(pos: Int, board: List[Option[Int]]): Set[Int] = {
    ints -- board.slice((pos / 9) * 9, ((pos / 9) * 9) + 9).flatMap(x => x).toSet
  }

  def colPossibilities(pos: Int, board: List[Option[Int]]): Set[Int] = {
    ints -- board.zipWithIndex.filter(_._2 % 9 == pos % 9).flatMap(x => x._1).toSet
  }

  def boxPossibilities(pos: Int, board: List[Option[Int]]): Set[Int] = {
    val top = ((pos / 9) / 3) * 3
    val left = ((pos % 9) / 3) * 3

    ints -- board.zipWithIndex.filter(x => {
      val i: Int = x._2
      val row = (i / 9)
      val col = (i % 9)
      (row >= top && row <= top+2) && (col >= left && col <= left +2)
      }).flatMap(x => x._1).toSet
  }

  def printBoard(board: List[Option[Int]]): Unit = {
    val grid = board.map(_.getOrElse((0))).zipWithIndex.groupBy(_._2 / 9).mapValues(l => l.map(_._1))
    (0 to 8).foreach(r => println(grid(r).mkString(",")));
  }

  def fanfare(board: List[Option[Int]]): Unit = {
    println("Ta-Da!!")
    printBoard(board)
  }
}