# 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 🙂