SudokuSolver.scala

import scala.io.StdIn

object SudokuSolver {
  def main(args: Array[String]): Unit = {
    val board = Vector.fill(9)(StdIn.readLine)
      .map(_.replace('*', '0').map(_.toString.toInt))
    
    val possibilities = {
      val transposed = board.transpose
      val divided = Seq.tabulate(3, 3) { (oy, ox) =>
        Seq.tabulate(3, 3)((iy, ix) => board(3*oy+iy)(3*ox+ix)).flatten
      }

      Seq.tabulate(9, 9) { (y, x) =>
        (1 to 9) diff (board(y) ++ transposed(x) ++ divided(y/3)(x/3))
      }
    }

    solve(Seq((board, possibilities))) match {
      case None => println("No solution")
      case Some(b) => println(b.map(_.mkString).mkString("\n"))
    }
  }

  def solve(n: Seq[(Seq[Seq[Int]], Seq[Seq[Seq[Int]]])]): Option[Seq[Seq[Int]]] =
    n.headOption match {
      case None => None
      case Some((board, _)) if !board.flatten.contains(0) => Some(board)
      case Some((board, possibilities)) =>
        val (candidates, (y, x)) =
          Seq.tabulate(9, 9)((a, b) => (possibilities(a)(b), (a, b)))
            .flatten
            .filter(_._1.nonEmpty)
            .minBy(_._1.size)
        
        val affected = ((0 until 9).map((y, _))
          ++ (0 until 9).map((_, x))
          ++ Seq.tabulate(3, 3)((dy, dx) => (y/3*3+dy, x/3*3+dx)).flatten)

        solve {
          candidates.map { c =>
            val b = board.updated(y, board(y).updated(x, c))
            val p = affected.foldLeft(possibilities) { case (ap, (ay, ax)) =>
              val ac = if (b(ay)(ax) != 0) Seq.empty else ap(ay)(ax).filter(_ != c)
              ap.updated(ay, ap(ay).updated(ax, ac))
            }
            (b, p)
          }.filterNot { s =>
            s._1.zip(s._2)
              .flatMap(t => t._1.zip(t._2))
              .exists(t => (t._1 == 0) && t._2.isEmpty)
          } ++ n.tail
        }
    }
}

Example

Input:

**2***1*5
*****5**2
8*5*4****
******7*4
**1****2*
*3***6***
4**9***6*
****8*3**
79*1*****

Output:

342679185
967815432
815243976
689321754
571498623
234756819
458937261
126584397
793162548