29 for (x <- (x0 until x0 + 3).toList; |
35 for (x <- (x0 until x0 + 3).toList; |
30 y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue) |
36 y <- (y0 until y0 + 3).toList) yield game(x + y * maxValue) |
31 } |
37 } |
32 |
38 |
33 |
39 |
34 //get_row(game0, 0) |
|
35 //get_row(game0, 1) |
|
36 //get_box(game0, (3,1)) |
|
37 |
|
38 def update(game: String, pos: Int, value: Char): String = |
40 def update(game: String, pos: Int, value: Char): String = |
39 game.updated(pos, value) |
41 game.updated(pos, value) |
40 |
42 |
41 def toAvoid(game: String, pos: Pos): List[Char] = |
43 def toAvoid(game: String, pos: Pos): List[Char] = |
42 (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos)) |
44 (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos)) |
43 |
45 |
44 def candidates(game: String, pos: Pos): List[Char] = |
46 def candidates(game: String, pos: Pos): List[Char] = |
45 allValues.diff(toAvoid(game, pos)) |
47 allValues.diff(toAvoid(game, pos)) |
46 |
|
47 //candidates(game0, (0, 0)) |
|
48 |
|
49 //def pretty(game: String): String = |
|
50 // "\n" ++ (game.sliding(maxValue, maxValue).mkString("\n")) |
|
51 |
48 |
52 def search(game: String): List[String] = { |
49 def search(game: String): List[String] = { |
53 if (isDone(game)) List(game) |
50 if (isDone(game)) List(game) |
54 else |
51 else |
55 candidates(game, emptyPosition(game)).par. |
52 candidates(game, emptyPosition(game)).par. |
56 map(c => search(update(game, empty(game), c))).toList.flatten |
53 map(c => search(update(game, empty(game), c))).toList.flatten |
57 } |
54 } |
58 |
55 |
59 // two easy games |
56 // a list of hard games according to Andrew Coles and Peter Norvig |
60 val game0 = """.14.6.3.. |
|
61 |62...4..9 |
|
62 |.8..5.6.. |
|
63 |.6.2....3 |
|
64 |.7..1..5. |
|
65 |5....9.6. |
|
66 |..6.2..3. |
|
67 |1..5...92 |
|
68 |..7.9.41.""".stripMargin.replaceAll("\\n", "") |
|
69 |
|
70 val game1 = """23.915... |
|
71 |...2..54. |
|
72 |6.7...... |
|
73 |..1.....9 |
|
74 |89.5.3.17 |
|
75 |5.....6.. |
|
76 |......9.5 |
|
77 |.16..7... |
|
78 |...329..1""".stripMargin.replaceAll("\\n", "") |
|
79 |
|
80 |
|
81 // a game that is in the sligtly harder category |
|
82 val game2 = """8........ |
|
83 |..36..... |
|
84 |.7..9.2.. |
|
85 |.5...7... |
|
86 |....457.. |
|
87 |...1...3. |
|
88 |..1....68 |
|
89 |..85...1. |
|
90 |.9....4..""".stripMargin.replaceAll("\\n", "") |
|
91 |
|
92 // a game with multiple solutions |
|
93 val game3 = """.8...9743 |
|
94 |.5...8.1. |
|
95 |.1....... |
|
96 |8....5... |
|
97 |...8.4... |
|
98 |...3....6 |
|
99 |.......7. |
|
100 |.3.5...8. |
|
101 |9724...5.""".stripMargin.replaceAll("\\n", "") |
|
102 |
57 |
103 val hard_games = |
58 val hard_games = |
104 List("85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.", |
59 List("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......", |
|
60 "52...6.........7.13...........4..8..6......5...........418.........3..2...87.....", |
|
61 "6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....", |
|
62 "48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....", |
|
63 "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...", |
|
64 "......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.", |
|
65 "6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....", |
|
66 ".524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........", |
|
67 "6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....", |
|
68 ".923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....", |
|
69 |
|
70 "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.", |
105 "..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..", |
71 "..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..", |
106 "12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4", |
72 "12..4......5.69.1...9...5.........7.7...52.9..3......2.9.6...5.4..9..8.1..3...9.4", |
107 "...57..3.1......2.7...234......8...4..7..4...49....6.5.42...3.....7..9....18.....", |
73 "...57..3.1......2.7...234......8...4..7..4...49....6.5.42...3.....7..9....18.....", |
108 "7..1523........92....3.....1....47.8.......6............9...5.6.4.9.7...8....6.1.", |
74 "7..1523........92....3.....1....47.8.......6............9...5.6.4.9.7...8....6.1.", |
109 "1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..", |
75 "1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..", |
207 ".5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.", |
173 ".5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.", |
208 ".....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........", |
174 ".....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........", |
209 "3...8.......7....51..............36...2..4....7...........6.13..452...........8..") |
175 "3...8.......7....51..............36...2..4....7...........6.13..452...........8..") |
210 |
176 |
211 |
177 |
212 |
|
213 //search(game0).map(pretty) |
|
214 //search(game1).map(pretty) |
|
215 |
|
216 // for measuring time |
178 // for measuring time |
217 def time_needed[T](i: Int, code: => T) = { |
179 def time_needed[T](i: Int, code: => T) = { |
218 val start = System.nanoTime() |
180 val start = System.nanoTime() |
219 for (j <- 1 to i) code |
181 for (j <- 1 to i) code |
220 val end = System.nanoTime() |
182 val end = System.nanoTime() |
221 s"${(end - start) / i / 1.0e9} secs" |
183 (end - start) / i / 1.0e9 |
222 } |
184 } |
223 |
185 |
224 //search(game2).map(pretty) |
186 |
225 //search(game3).distinct.length |
187 val total = |
226 println(time_needed(10, search(game0))) |
188 (for ((game, i) <- hard_games.zipWithIndex) yield { |
227 println(time_needed(10, search(game1))) |
189 val secs = time_needed(1, search(game)) |
228 println(time_needed(4, search(game2))) |
190 println(f"${i}%2.0f: ${game} |${secs}%2.3f secs") |
229 println(time_needed(8, search(game3))) |
191 secs |
230 |
192 }).sum |
231 for (i <- 0 until hard_games.length) { |
193 |
232 println(" " ++ hard_games(i)) |
194 println(f"\ntotal: ${total}%.3f secs") |
233 println(s"$i: ${time_needed(1, search(hard_games(i)))}") |
195 |
234 } |
196 } |
235 |
197 |
236 } |
198 |
|
199 |
|
200 // 1 single thread version 800 secs |
|
201 // 4 cores parallel version on moderate laptop 400 secs |
|
202 // 8 cores (4 physical + 4 hyperthread): 290 secs |
|
203 // 36 cores (18 physical + 18 hyperthread): 142 secs |
|
204 |