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)
