--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/sudoku_test.scala	Mon Dec 07 01:25:41 2020 +0000
@@ -0,0 +1,88 @@
+// Sudoku
+//========
+
+// call parallel version with
+//
+// scala -cp scala-parallel-collections_2.13-0.2.0.jar sudoku_test.scala 
+//
+// or
+//
+// scalac -cp scala-parallel-collections_2.13-0.2.0.jar sudoku_test.scala
+// java -cp .:scala-library-2.13.0.jar:scala-parallel-collections_2.13-0.2.0.jar Sudoku
+
+object Sudoku extends App { 
+
+import scala.collection.parallel.CollectionConverters._
+
+type Pos = (Int, Int)
+val emptyValue = '.'
+val maxValue = 9
+
+val allValues = "123456789".toList
+val indexes = (0 to 8).toList
+
+
+def empty(game: String) = game.indexOf(emptyValue)
+def isDone(game: String) = empty(game) == -1 
+def emptyPosition(game: String) = {
+  val e = empty(game)
+  (e % maxValue, e / maxValue)
+}
+
+
+def get_row(game: String, y: Int) = indexes.map(col => game(y * maxValue + col))
+def get_col(game: String, x: Int) = indexes.map(row => game(x + row * maxValue))
+
+def get_box(game: String, pos: Pos): List[Char] = {
+    def base(p: Int): Int = (p / 3) * 3
+    val x0 = base(pos._1)
+    val y0 = base(pos._2)
+    for (x <- (x0 until x0 + 3).toList;
+         y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue)
+}         
+
+
+def update(game: String, pos: Int, value: Char): String = 
+  game.updated(pos, value)
+
+def toAvoid(game: String, pos: Pos): List[Char] = 
+  (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos))
+
+def candidates(game: String, pos: Pos): List[Char] = 
+  allValues.diff(toAvoid(game, pos))
+
+def search(game: String): List[String] = {
+  if (isDone(game)) List(game)
+  else {
+    val cs = candidates(game, emptyPosition(game))
+    cs.par.map(c => search(update(game, empty(game), c))).toList.flatten
+  }
+}
+
+
+def pretty(game: String): String = 
+  "\n" + (game.grouped(maxValue).mkString(",\n"))
+
+
+val game2 = """8........
+              |..36.....
+              |.7..9.2..
+              |.5...7...
+              |....457..
+              |...1...3.
+              |..1....68
+              |..85...1.
+              |.9....4..""".stripMargin.replaceAll("\\n", "")
+
+// for measuring time
+def time_needed[T](i: Int, code: => T) = {
+  val start = System.nanoTime()
+  for (j <- 1 to i) code
+  val end = System.nanoTime()
+  s"${(end - start) / 1.0e9} secs"
+}
+
+
+println(time_needed(10, search(game2)))
+
+}