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