Scala Performance in Solving Sudoku

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