1 // Sudoku |
1 // Sudoku |
2 //======== |
2 //======== |
3 |
3 |
4 // call parallel version with |
4 // call parallel version with |
5 // |
5 // |
6 // scala -cp scala-parallel-collections_2.13-0.2.0.jar sudoku.scala |
6 // scala -cp scala-parallel-collections_3-1.0.4.jar sudoku.scala |
7 // |
7 // |
8 // java -cp .:scala-library-2.13.0.jar:scala-parallel-collections_2.13-0.2.0.jar Sudoku |
8 // java -cp .:scala3-library_3-3.2.2.jar:scala-parallel-collections_3-1.0.4.jar Sudoku |
9 |
9 |
10 object Sudoku extends App { |
10 |
11 |
11 |
12 import scala.collection.parallel.CollectionConverters._ |
12 import scala.collection.parallel.CollectionConverters._ |
13 |
13 |
14 type Pos = (Int, Int) |
14 type Pos = (Int, Int) |
15 val emptyValue = '.' |
15 val emptyValue = '.' |
50 (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos)) |
50 (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos)) |
51 |
51 |
52 def candidates(game: String, pos: Pos): List[Char] = |
52 def candidates(game: String, pos: Pos): List[Char] = |
53 allValues.diff(toAvoid(game, pos)) |
53 allValues.diff(toAvoid(game, pos)) |
54 |
54 |
55 |
55 // search for all solutions |
56 def search(game: String): List[String] = { |
56 def search(game: String): List[String] = { |
57 if (isDone(game)) List(game) |
57 if (isDone(game)) List(game) |
58 else |
58 else |
59 candidates(game, emptyPosition(game)).par. |
59 candidates(game, emptyPosition(game)). |
60 map(c => search(update(game, empty(game), c))).toList.flatten |
60 map(c => search(update(game, empty(game), c))).toList.flatten |
61 } |
61 } |
62 |
62 |
63 |
63 |
64 |
64 // search for single solution |
65 def search1T(games: List[String]): Option[String] = games match { |
65 def search1T(games: List[String]): Option[String] = games match { |
66 case Nil => None |
66 case Nil => None |
67 case game::rest => { |
67 case game::rest => { |
68 if (isDone(game)) Some(game) |
68 if (isDone(game)) Some(game) |
69 else { |
69 else { |
201 val end = System.nanoTime() |
201 val end = System.nanoTime() |
202 (end - start) / i / 1.0e9 |
202 (end - start) / i / 1.0e9 |
203 } |
203 } |
204 |
204 |
205 |
205 |
206 val total = |
206 @main |
207 (for ((game, i) <- hard_games.zipWithIndex) yield { |
207 def test() = { |
208 val secs = time_needed(1, search(game)) |
208 val total = |
209 println(f"${i}%2.0f: ${game} |${secs}%2.3f secs") |
209 (for ((game, i) <- hard_games.zipWithIndex) yield { |
210 secs |
210 val secs = time_needed(1, search(game)) |
211 }).sum |
211 println(f"${i}%2.0f: ${game} |${secs}%2.3f secs") |
212 |
212 secs |
213 println(f"\ntotal: ${total}%.3f secs") |
213 }).sum |
214 |
214 |
215 } |
215 println(f"\ntotal: ${total}%.3f secs") |
216 |
216 } |
217 |
217 |
218 |
218 |
219 // 1 single thread version 800 secs |
219 |
|
220 // some numbers: |
|
221 // |
|
222 // single thread version 800 secs |
220 // |
223 // |
221 // 4 cores parallel version on a moderate laptop 400 secs |
224 // 4 cores parallel version on a moderate laptop 400 secs |
222 // 8 cores: 290 secs |
225 // 8 cores: 290 secs |
223 // 10 cores: 156 secs |
226 // 10 cores: 156 secs |
224 // 18 cores: 142 secs |
227 // 18 cores: 142 secs |