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)