--- a/progs/sudoku.scala Thu Oct 31 12:01:56 2019 +0000
+++ b/progs/sudoku.scala Fri Nov 01 12:39:25 2019 +0000
@@ -1,6 +1,12 @@
// Sudoku
//========
+// call parallel version with
+//
+// scala -cp scala-parallel-collections_2.13-0.2.0.jar sudoku.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._
@@ -31,10 +37,6 @@
}
-//get_row(game0, 0)
-//get_row(game0, 1)
-//get_box(game0, (3,1))
-
def update(game: String, pos: Int, value: Char): String =
game.updated(pos, value)
@@ -44,11 +46,6 @@
def candidates(game: String, pos: Pos): List[Char] =
allValues.diff(toAvoid(game, pos))
-//candidates(game0, (0, 0))
-
-//def pretty(game: String): String =
-// "\n" ++ (game.sliding(maxValue, maxValue).mkString("\n"))
-
def search(game: String): List[String] = {
if (isDone(game)) List(game)
else
@@ -56,52 +53,21 @@
map(c => search(update(game, empty(game), c))).toList.flatten
}
-// two easy games
-val game0 = """.14.6.3..
- |62...4..9
- |.8..5.6..
- |.6.2....3
- |.7..1..5.
- |5....9.6.
- |..6.2..3.
- |1..5...92
- |..7.9.41.""".stripMargin.replaceAll("\\n", "")
-
-val game1 = """23.915...
- |...2..54.
- |6.7......
- |..1.....9
- |89.5.3.17
- |5.....6..
- |......9.5
- |.16..7...
- |...329..1""".stripMargin.replaceAll("\\n", "")
-
-
-// a game that is in the sligtly harder category
-val game2 = """8........
- |..36.....
- |.7..9.2..
- |.5...7...
- |....457..
- |...1...3.
- |..1....68
- |..85...1.
- |.9....4..""".stripMargin.replaceAll("\\n", "")
-
-// a game with multiple solutions
-val game3 = """.8...9743
- |.5...8.1.
- |.1.......
- |8....5...
- |...8.4...
- |...3....6
- |.......7.
- |.3.5...8.
- |9724...5.""".stripMargin.replaceAll("\\n", "")
+// a list of hard games according to Andrew Coles and Peter Norvig
val hard_games =
- List("85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
+ List("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......",
+ "52...6.........7.13...........4..8..6......5...........418.........3..2...87.....",
+ "6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....",
+ "48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....",
+ "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...",
+ "......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.",
+ "6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....",
+ ".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........",
+ "6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....",
+ ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....",
+
+ "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
"..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..",
"12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4",
"...57..3.1......2.7...234......8...4..7..4...49....6.5.42...3.....7..9....18.....",
@@ -209,28 +175,30 @@
"3...8.......7....51..............36...2..4....7...........6.13..452...........8..")
-
-//search(game0).map(pretty)
-//search(game1).map(pretty)
-
// 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) / i / 1.0e9} secs"
+ (end - start) / i / 1.0e9
}
-//search(game2).map(pretty)
-//search(game3).distinct.length
-println(time_needed(10, search(game0)))
-println(time_needed(10, search(game1)))
-println(time_needed(4, search(game2)))
-println(time_needed(8, search(game3)))
-for (i <- 0 until hard_games.length) {
- println(" " ++ hard_games(i))
- println(s"$i: ${time_needed(1, search(hard_games(i)))}")
+val total =
+ (for ((game, i) <- hard_games.zipWithIndex) yield {
+ val secs = time_needed(1, search(game))
+ println(f"${i}%2.0f: ${game} |${secs}%2.3f secs")
+ secs
+ }).sum
+
+println(f"\ntotal: ${total}%.3f secs")
+
}
-}
\ No newline at end of file
+
+
+// 1 single thread version 800 secs
+// 4 cores parallel version on moderate laptop 400 secs
+// 8 cores (4 physical + 4 hyperthread): 290 secs
+// 36 cores (18 physical + 18 hyperthread): 142 secs
+