I translated Peter Norvig Python Sudoku solver to Scala and my Scala implementation was slower in the order of few magnitudes e.g. instantaneous, in Python, vs 4 to 5 seconds. I suspected I didn't implement the algorithm to the dot or the way I use the Scala classes less than ideal. These are the crucial functions I translated from the Python functions using the same names. Thanks.

def eliminate(solution: Map[String, String], cell: String, num: Char):
Option[Map[String, String]] = {

val nums = solution(cell)

if (nums.contains(num)) {
  val updatedSoln = solution.updated(cell, nums.replace(num.toString, ""))
  val ys = updatedSoln(cell)

  val emSoln = if (ys.isEmpty) None
  else if (ys.size == 1)
    peers(cell).foldLeft(Option(updatedSoln))((s, c) =>
      s.flatMap(s2 => eliminate(s2, c, ys.head)))
  else Some(updatedSoln)

  emSoln.flatMap(s => {
    val finalSoln = peersAndSelf(cell).filter(c => s(c).contains(num))
    if (finalSoln.isEmpty) None
    else if (finalSoln.size == 1) assign(s, finalSoln.head, num)
    else emSoln
 } else Some(solution)
def assign(solution: Map[String, String], cell: String, num: Char): Option[Map[String, String]] = {
if (debug) println(s"Assign ($cell, $num)")
solution(cell).replace(num.toString, "").foldLeft(Option(solution))((s, c) => s.flatMap(m => eliminate(m, cell, c)))

def search(solution: Map[String, String]): Option[Map[String, String]] =
solution.filter(_._2.size > 1).toList match {
  case Nil => Some(solution)
  case xs =>
    val (cell, nums) = xs.minBy(_._2.size)
    nums.flatMap(d => assign(solution, cell, d) match {
      case Some(x) => search(x)
      case None => None

I am not comparing which language is faster. I happy if Python takes 300ms and the refactor Scala code takes 800ms.

Click here for the full implementation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.