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 🙂