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)

A simple Sudoku solver- Haskell to Scala

Context

I found this excellent blog post by Abhinav Sarkar that lays out, step-by-step, writing a simple Sudoku solver in Haskell, and … it seemed a good idea to translate it, step-by-corresponding-step, into Scala.

Finding equivalents

I tried to stick to the spirit of the code as much as possible.

Some translations were obvious, such as Option for Maybe, or grouped for Data.List.Split.chunksOf, but others (e.g. how unlines were replaced by their stdlib equivalents, in that case, scala.io.Source.getLines)

I thought it was okay to just use print...() for showing the Grid:

  def showGridWithPossibilities(grid: Grid) = {
    def printPossibilities(nums: List[Int]) = {
      print("[ ")
      Range(0,10).map { n =>
        nums.contains(n) match {
          case true => print(n)
          case false => print(" ")
        }
      }
      print(" ]")
    }


    def showRow(row: Row) = {
      for (cell <- row) {
        cell match {
          case Fixed(fv) => print(s"      $fv       ")
          case Possible(pv) => printPossibilities(pv)
        }
      }
      println()
    }
    for (row <- grid) showRow(row)
  }

For traverse and sequence, I could have used portions from cats, but decided to just “roll my own” to keep it simple:

  def traverser[A, B](list: List[A])(f: A => Option[B]): Option[List[B]] = {
    def inner[A](elem: Option[A], list: Option[List[A]]): Option[List[A]] = {
      for { l <- list; e <- elem } yield e :: l
    }

    list.foldRight[Option[List[B]]](Some(Nil))( (elem, list) => inner(f(elem), list) )
  }

  def sequencer[A](list: List[Option[A]]) = traverser(list)(identity)

The data ADT was replaced by sealed trait case class … extends ….

The solve method itself doesn’t look too different:


  def solve(grid: Grid): Option[Grid] = {
    for {
      pg <- fixPoint(grid)

      nextGrid <- solveHelper(pg)
    } yield nextGrid
  }

  def solveHelper(grid: Grid): Option[Grid] = {
    if (isGridInvalid(grid)) {
      None
    } else if (isGridFilled(grid)) {
      Some(grid)
    } else {
      val (g1, g2) = nextGrids(grid)
      val solvedG1 = solve(g1)
      solvedG1 match {
        case None => solve(g2)
        case _ => solvedG1
      }
    }
  }

Comments on the original

The way the original blog post lays out the solution to the problem is brilliant from a pedagogical point of view, and I wish there were more like it. Personally, I feel “seeing the work” teaches me way more than viewing some sort of final polished product.

Code cleanup

While developing, I basically had one long file, with the test code left in, mostly because I liked having this runTests() helper around while I was making additions.

Some of the helper functions could be consolidated into other methods, I might get to that later.

In general, I elected to leave it as a “work in progress” state.

Performance

Tested it on the first 100 entries from the same problem set,
Running it within SBT .

sbt:sudoku> run "/home/agam/tmp/sudoku17-top-100.txt"

… showed a similar result:

[success] Total time: 205 s (03:25)

… although this is (1) a cold JVM, running (2) on a small DO droplet, so I suppose it’s possible to do an amortized, longer test later on to get better timings.

tl;dr

The source code for all this is here

… and I see there’s a follow-on post, so … I’ll try that some time 🙂