Last active
January 15, 2019 22:20
-
-
Save sshark/bc623797761f9bd2e1bc278aa699a184 to your computer and use it in GitHub Desktop.
Scala translation for http://www.norvig.com/sudoku.html Unfortunately, it has a longer execution time compare to the Python version.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Scala translation for http://www.norvig.com/sudoku.html | |
object Sudoku { | |
val debug = false | |
val digits = ('1' to '9').mkString | |
val alphas = ('A' to 'I').mkString | |
def cross(rows: String, cols: String) = (for { | |
row <- rows | |
col <- cols} yield {"" + row + col}).toSet | |
val verticals = digits.map(d => cross(alphas, d.toString)).toSet | |
val horizontals = alphas.map(a => cross(a.toString, digits)).toSet | |
val blocks = for { | |
colBlk <- alphas.grouped(3) | |
rowBlk <- digits.grouped(3) | |
} yield (cross(colBlk, rowBlk)) | |
val all = horizontals ++ verticals ++ blocks | |
val everyone = cross(alphas, digits) | |
.foldLeft(Map.empty[String, Set[String]])((m,a) => | |
m.updated(a, all.filter(_.contains(a)).flatten)) | |
val peers = everyone.map{case (k,v) => k -> v.filterNot(_ == k)} | |
def coord(ndx: Int) = "" + alphas(ndx / 9) + digits(ndx % 9) | |
def addNth(l: List[List[String]], extras: List[String], newList: List[List[String]] = Nil, ndx: Int = 0): List[List[String]] = | |
l match { | |
case Nil => newList.reverse | |
case xs +: xss if (ndx % 3 == 0 && ndx > 1) => addNth(xss, extras, xs +: extras +: newList, ndx + 1) | |
case xs +: xss => addNth(xss, extras, xs +: newList, ndx + 1) | |
} | |
def prettyFormat(s: String) = | |
List("+-----+-----+-----+") ++ | |
addNth(s.grouped(9).map(_.grouped(3).toList).toList, List("---", "---", "---")) | |
.map(x => if (x(0).startsWith("-")) "+-----+-----+-----+" else s"| ${x(0)} | ${x(1)} | ${x(2)} |") ++ | |
List("+-----+-----+-----+") | |
def init(puzzle: String): Map[String, String] = { | |
def fill(i: Char, cell: String, solution: Map[String, String]) = | |
peers(cell).foldLeft(solution)( | |
(m,c) => m.updated(c, m(c).filterNot(_ == i))) | |
def _init(cells: List[(Char, Int)], solution: Map[String, String]): Map[String, String] = cells match { | |
case Nil => solution | |
case (c, i) :: xs => _init(xs, fill(c, coord(i), solution)) | |
} | |
val prefilledSolution = puzzle.zipWithIndex | |
.foldLeft(Map.empty[String, String]) { | |
case (m, ('.', pos)) => m.updated(coord(pos), digits) | |
case (m, (c, pos)) => m.updated(coord(pos), c.toString) | |
} | |
_init(puzzle.zipWithIndex.filterNot(_._2 == '.').toList, prefilledSolution) | |
} | |
def prettyPrint(puzzle: Map[String, String]) = | |
puzzle.toList.sortBy(_._1).map(_._2).grouped(9).toList.foreach(line => { | |
line.foreach(x => {x.foreach(print); print(" " * (9 - x.size))}) | |
println | |
}) | |
def print2List(puzzle: Map[String, String]) = { | |
print("List(") | |
puzzle.toList.sortBy(_._1).map(_._2).grouped(9).toList.foreach(line => { | |
line.foreach(x => { | |
print("\"") | |
x.foreach(print) | |
print("\",") | |
}) | |
println | |
}) | |
print(")") | |
} | |
def isSolved(solution: Map[String, String]) = { | |
val result = all.map(y => y.foldLeft(Set.empty[Char])((s,z) => s ++ solution(z))) | |
result.size == 1 && result.headOption.map(_.size == 9).getOrElse(false) | |
} | |
def eliminate(solution: Map[String, String], cell: String, num: Char): | |
Option[Map[String, String]] = { | |
if (debug) { | |
println(s"Eliminate ($cell, $num)") | |
prettyPrint(solution) | |
println | |
} | |
val nums = solution(cell) | |
if (nums.contains(num)) { | |
val updatedSoln = solution.updated(cell, nums.filterNot(_ == num)) | |
val ys = updatedSoln(cell) | |
val emSoln = if (ys.isEmpty) None | |
else if (ys.size == 1) | |
peers(cell).foldLeft(Option(updatedSoln))((s, c) => | |
s.flatMap(s2 => eliminate(s2, c, ys.head))) | |
else Some(updatedSoln) | |
emSoln.flatMap(s => { | |
val finalSoln = everyone(cell).filter(c => s(c).contains(num)) | |
if (finalSoln.isEmpty) None | |
else if (finalSoln.size == 1) assign(s, finalSoln.head, num) | |
else emSoln | |
}) | |
} else Some(solution) | |
} | |
def assign(solution: Map[String, String], cell: String, num: Char): Option[Map[String, String]] = { | |
if (debug) println(s"Assign ($cell, $num)") | |
solution(cell).filterNot(_ == num).foldLeft(Option(solution))((s, c) => s.flatMap(m => eliminate(m, cell, c))) | |
} | |
def search(solution: Map[String, String]): Option[Map[String, String]] = { | |
def _search(solution: Map[String, String], cell: String, nums: String): Option[Map[String, String]] = | |
if (nums.isEmpty) None | |
else assign(solution, cell, nums.head) | |
.orElse(_search(solution, cell, nums.tail)) | |
solution.filter(_._2.size > 1).toList match { | |
case Nil => Some(solution) | |
case xs => | |
val (cell, nums) = xs.minBy(_._2.size) | |
} | |
} | |
/* | |
def search(solution: Map[String, String]): Option[Map[String, String]] = | |
solution.filter(_._2.size > 1).toList match { | |
case Nil => Some(solution) | |
case xs => | |
val (cell, nums) = xs.minBy(_._2.size) | |
nums.flatMap(d => assign(solution, cell, d) match { | |
case Some(x) => search(x) | |
case None => None | |
}).headOption | |
} | |
*/ | |
} | |
object SudokuApp extends App { | |
import Sudoku._ | |
/* unit tests */ | |
assert(peers("A1") == | |
Set("A9", "G1", "A4", "C1", "H1", | |
"A5", "D1", "I1", "E1", "B3", | |
"A2", "A6", "B2", "F1", "C3", | |
"A8", "A3", "B1", "A7", "C2")) | |
assert(everyone(coord(18)) == | |
Set("C6", "G1", "C1", "H1", "C8", | |
"C7", "D1", "I1", "E1", "C9", | |
"B3", "A2", "C4", "A1", "B2", | |
"F1", "C3", "C5", "A3", "B1", | |
"C2")) | |
/* unit tests end */ | |
val emptyPuzzle = "3..62..7....7...2...........5...81......4...8.........7.25......4....8........3.." | |
// val emptyPuzzle = "8.....4..72......9..4.........1.7..23.5...9...4...........8..7..17..............." | |
prettyFormat(emptyPuzzle) foreach println | |
val startMills = System.currentTimeMillis | |
// println(search(init(emptyPuzzle))) | |
search(init(emptyPuzzle)) match { | |
case Some(solved) => | |
if (isSolved(solved)) prettyFormat(solved.toList.sortBy(_._1).map(_._2.head).mkString).foreach(println) | |
else println("Sudoku solution is incorrect") | |
case None => println("Sudoku is not solvable") | |
} | |
println(s"\nTime taken: ${System.currentTimeMillis - startMills}ms") | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Scala implementation using the algorithm from http://www.norvig.com/sudoku.html with a slight twist | |
object Sudoku { | |
val debug = false | |
val digits = ('1' to '9').mkString | |
val alphas = ('A' to 'I').mkString | |
def cross(rows: String, cols: String) = (for { | |
row <- rows | |
col <- cols} yield {"" + row + col}).toSet | |
val horizontals = digits.map(d => cross(alphas, d.toString)).toSet | |
val verticals = alphas.map(a => cross(a.toString, digits)).toSet | |
val blocks = for { | |
colBlk <- alphas.grouped(3) | |
rowBlk <- digits.grouped(3) | |
} yield (cross(colBlk, rowBlk)) | |
val all = horizontals ++ verticals ++ blocks | |
val peers = cross(alphas, digits).foldLeft(Map.empty[String, Set[Set[String]]])((m,a) => | |
m + (a -> (all.filter(_.contains(a)).map(_ - a)))) | |
def coord(ndx: Int) = "" + alphas(ndx / 9) + digits(ndx % 9) | |
def addNth(l: List[List[String]], extras: List[String], newList: List[List[String]] = Nil, ndx: Int = 0): List[List[String]] = | |
l match { | |
case Nil => newList.reverse | |
case xs +: xss if (ndx % 3 == 0 && ndx > 1) => addNth(xss, extras, xs +: extras +: newList, ndx + 1) | |
case xs +: xss => addNth(xss, extras, xs +: newList, ndx + 1) | |
} | |
def prettyFormat(s: String) = | |
List("+-----+-----+-----+") ++ | |
addNth(s.grouped(9).map(_.grouped(3).toList).toList, List("---", "---", "---")) | |
.map(x => if (x(0).startsWith("-")) "+-----+-----+-----+" else s"| ${x(0)} | ${x(1)} | ${x(2)} |") ++ | |
List("+-----+-----+-----+") | |
def init(puzzle: String): Map[String, Set[Char]] = { | |
def fill(i: Char, cell: String, solution: Map[String, Set[Char]]) = | |
peers(cell).flatten.foldLeft(solution)( | |
(m,c) => m.updated(c, m(c).filterNot(_ == i))) | |
def _init(cells: List[(Char, Int)], solution: Map[String, Set[Char]]): Map[String, Set[Char]] = cells match { | |
case Nil => solution | |
case (c, i) :: xs => _init(xs, fill(c, coord(i), solution)) | |
} | |
val prefilledSolution = puzzle.zipWithIndex | |
.foldLeft(Map.empty[String, Set[Char]]) { | |
case (m, ('.', pos)) => m.updated(coord(pos), digits.toSet) | |
case (m, (c, pos)) => m.updated(coord(pos), Set(c)) | |
} | |
_init(puzzle.zipWithIndex.filterNot(_._2 == '.').toList, prefilledSolution) | |
} | |
def prettyPrint(puzzle: Map[String, Set[Char]]) = | |
puzzle.toList.sortBy(_._1).map(_._2).grouped(9).toList.foreach(line => { | |
line.foreach(x => {x.foreach(print); print(" " * (9 - x.size))}) | |
println | |
}) | |
def print2List(puzzle: Map[String, Set[Char]]) = { | |
print("List(") | |
puzzle.toList.sortBy(_._1).map(_._2).grouped(9).toList.foreach(line => { | |
line.foreach(x => { | |
print("\"") | |
x.foreach(print) | |
print("\",") | |
}) | |
println | |
}) | |
print(")") | |
} | |
def eliminate(i: Char, cell: String, solution: Map[String, Set[Char]]): Option[Map[String, Set[Char]]] = { | |
val neighbours = peers(cell).flatten | |
val affectedCells = neighbours.filter(cell => { | |
val guesses = solution(cell) | |
guesses.size == 2 && guesses.contains(i) | |
}) | |
val newSolution = neighbours.foldLeft(Option(solution))((s, c) => { | |
s.flatMap(m => m(c) match { | |
case xs if xs.contains(i) && xs.size == 1 => None | |
case xs if xs.contains(i) => Some(m.updated(c, m(c) - i)) | |
case xs => s | |
}) | |
}) | |
if (debug) { | |
println(s"Base cell: $cell, targeted cell: $affectedCells, neighbours: $neighbours") | |
newSolution.foreach(prettyPrint) | |
} | |
newSolution.flatMap(s => | |
affectedCells.foldLeft(Option(s))((s2, c) => s2.flatMap(m => | |
eliminate(m(c).head, c, m)))) | |
} | |
def filterOption[A, B](xs: Map[A, B]) = if (xs.isEmpty) None else Some(xs) | |
def solve(puzzle: Map[String, Set[Char]]): Option[Map[String, Set[Char]]] = { | |
def solve_(nextPuzzle: Map[String, Set[Char]], | |
cell: String, | |
balance: Set[Char]): Option[Map[String, Set[Char]]] = | |
if (balance.isEmpty) None | |
else eliminate(balance.head, cell, puzzle.updated(cell, Set(balance.head))).flatMap(solve(_)) | |
.orElse(solve_(nextPuzzle, cell, balance.tail)) | |
filterOption(puzzle.filter(_._2.size > 1)).map(_.toList.minBy(_._2.size)).headOption match { | |
case None => Some(puzzle) | |
case Some((cord, nums)) => { | |
if (debug) { | |
println(s"$cord => $nums") | |
prettyPrint(puzzle) | |
println | |
} | |
solve_(puzzle, cord, nums) | |
} | |
} | |
} | |
def isSolved(solution: Map[String, Set[Char]]) = { | |
val result = all.map(y => y.foldLeft(Set.empty[Char])((s,z) => s ++ solution(z))) | |
result.size == 1 && result.headOption.map(_.size == 9).getOrElse(false) | |
} | |
} | |
object SudokuApp extends App { | |
import Sudoku._ | |
/* unit tests */ | |
assert(peers("A1") == Set( | |
Set("C1", "B3", "A2", "B2", "C3", "A3", "B1", "C2"), | |
Set("A9", "A4", "A5", "A2", "A6", "A8", "A3", "A7"), | |
Set("G1", "C1", "H1", "D1", "I1", "E1", "F1", "B1"))) | |
/* unit tests end */ | |
val emptyPuzzle = "3..62..7....7...2...........5...81......4...8.........7.25......4....8........3.." | |
// val emptyPuzzle = "8.....4..72......9..4.........1.7..23.5...9...4...........8..7..17..............." | |
val startMills = System.currentTimeMillis | |
prettyFormat(emptyPuzzle) foreach println | |
solve(init(emptyPuzzle)) match { | |
case Some(solved) => | |
if (isSolved(solved)) prettyFormat(solved.toList.sortBy(_._1).map(_._2.head).mkString).foreach(println) | |
else println("Sudoku solution is incorrect") | |
case None => println("Sudoku is not solved") | |
} | |
println(s"\nTime taken: ${System.currentTimeMillis - startMills}ms") | |
} | |
object ManySudokuApp extends App { | |
import scala.util.Try | |
import scala.language.postfixOps | |
import scala.concurrent.duration._ | |
import scala.concurrent.{ExecutionContext, Future, Await} | |
import java.util.concurrent.ForkJoinPool | |
import Sudoku._ | |
implicit val ec = ExecutionContext.fromExecutorService(new ForkJoinPool) | |
val verbose = false | |
val defaultPuzzleFn = "hardest17.txt" | |
val resourcesTry = Try(scala.io.Source.fromResource(args.headOption.getOrElse(defaultPuzzleFn))) | |
val puzzlesFtr = Future.fromTry(resourcesTry).map(_.getLines) | |
val startMills = System.currentTimeMillis | |
val solvedPuzzles = puzzlesFtr.flatMap(puzzles => Future.sequence(puzzles.map {puzzle => | |
Future { | |
if (verbose) { | |
prettyFormat(puzzle) foreach println | |
solve(init(puzzle)) match { | |
case Some(solved) => | |
if (isSolved(solved)) prettyFormat(solved.toList.sortBy(_._1).map(_._2.head).mkString).foreach(println) | |
else println("Sudoku solution is incorrect") | |
case None => println("Sudoku is not solved") | |
} | |
} else { | |
solve(init(puzzle)) | |
} | |
} | |
})) | |
Await.ready(solvedPuzzles, 20 minute) | |
val output = solvedPuzzles | |
.map(x => s"\nTime taken: ${System.currentTimeMillis - startMills}ms") | |
.recover {case t => if (args.isEmpty) "Default puzzles not found" else s"${args.head} not found."} | |
println(Await.result(output, 10 second)) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment