Optimized Sudoku solver- Haskell to Scala

Context

As hinted at in the first post, I found Abhinav’s posts to be a great source material for learning and (over this weekend) recreation 🙂

I picked the second post, where the pruning process is tweaked to be faster.

Pruning changes

I pretty much stuck to the original code, just Scala-ized it, most of the action happens here:

  def exclusivePossibilities(row: Row): List[List[Int]] = {
    def foldHelper1(m: Map[Int, List[Int]], entry: (Cell, Int)): Map[Int, List[Int]] =  entry match {
      case (Possible(nums), idx) =>
    nums.foldLeft(m) {  (m,n) =>
          m.updatedWith(n)( (optList) => optList match {
            case None => Some(List(idx))
            case Some(list) => Some(list.appended(idx))
          })
        }
    }

    def foldHelper2(m: Map[List[Int], List[Int]], entry: (Int, List[Int])): Map[List[Int], List[Int]] = entry match {
      case (idx, nums) =>
        m.updatedWith(nums)( (optList) => optList match {
          case None => Some(List(idx))
          case Some(list) => Some(list.appended(idx))
        })
    }

    // Get map of indices to values.
    val interim = row.
      zip(Range(1,10).toList).
      filter {
        case (c, _) => isPossible(c)
      }.
      foldLeft(Map(): Map[Int, List[Int]])(foldHelper1(_, _)).
      filter(_._2.length < 4)

    // Flip map and extract list of indices.
    interim.
      foldLeft(Map(): Map[List[Int], List[Int]])(foldHelper2(_, _)).
      filter { case (k, v) => k.length == v.length }.
      values.
      toList
  }

  def makeCell(nums: List[Int]): Option[Cell] = nums match {
    case List() => None
    case List(x) => Some(Fixed(x))
    case xs => Some(Possible(xs))
  }

… which is then used by the pruning functions (the first largely kept from before, the second one something new) …

  def pruneCellsByFixed(cells: List[Cell]): Option[List[Cell]] = {
    val fixeds = cells.collect { case Fixed(x) => x }

    def pruneCell(c: Cell): Option[Cell] = c match {
      case f @ Fixed(_) => Some(f)
      case Possible(nums) => makeCell(nums.filterNot(fixeds.toSet))
    }

    traverser(cells)(pruneCell)
  }


  def pruneCellsByExclusives(cells: List[Cell]): Option[List[Cell]] = {
    val exclusives = exclusivePossibilities(cells)
    val allExclusives = exclusives.flatten

    def pruneCell(c: Cell): Option[Cell] = c match {
      case f @ Fixed(_) => Some(f)
      case p @ Possible(nums) => {
        val intersection = nums.intersect(allExclusives)

        if (exclusives.contains(intersection)) {
          makeCell(intersection)
        } else {
          Some(p)
        }
      }
    }

    exclusives match {
      case List() => Some(cells)
      case _ => traverser(cells)(pruneCell)
    }
  }

… and the replacement for the old pruneCells is:

 def pruneCells(cells: List[Cell]): Option[List[Cell]] = {
    for {
      step1 <- fixM[List[Cell]](pruneCellsByFixed, cells)
      step2 <- fixM[List[Cell]](pruneCellsByExclusives, step1)
    } yield step2
  }

View source here.

(Note: I had a bug where I had forgotten to filter out keys/values of identical length within exclusivePossibilities, which led to a few rounds of debugging … once again, I elected to leave that commit history instead of cleaning it up)

Results

sbt:sudoku> run "/home/agam/tmp/sudoku17-top-100.txt"
…
Total time: 2 s,

I found a massive speedup too (100x! … two seconds to solve the sample set of a hundred problems, instead of two hundred seconds earlier)