15 puzzle solver: Difference between revisions
Content added Content deleted
Line 4,609: | Line 4,609: | ||
<lang Scala> |
<lang Scala> |
||
import scala.collection.mutable |
import scala.collection.mutable |
||
⚫ | |||
case class Board(table: Array[Int], r: Int, c: Int, parent: List[String] = List()) { |
case class Board(table: Array[Int], r: Int, c: Int, parent: List[String] = List()) { |
||
def cloneSwap(r: Int, c: Int, rr: Int, cc: Int) = { |
def cloneSwap(r: Int, c: Int, rr: Int, cc: Int) = { |
||
val cTable = table.clone |
val cTable = table.clone |
||
cTable(r |
cTable(r << 2 | c) = table(rr << 2 | cc) |
||
cTable(rr |
cTable(rr << 2 | cc) = table(r << 2 | c) |
||
cTable |
cTable |
||
} |
} |
||
Line 4,634: | Line 4,634: | ||
// Manhattan distance |
// Manhattan distance |
||
def heuristic() = { |
def heuristic() = { |
||
val posF = finalBoard.positionMap |
val posF = Board.finalBoard.positionMap |
||
val posT = positionMap |
val posT = positionMap |
||
var res = 0; |
var res = 0; |
||
for (i ← 0 to 15) { |
for (i ← 0 to 15) { |
||
Line 4,647: | Line 4,646: | ||
def key = table.mkString(",") |
def key = table.mkString(",") |
||
def travelled() = parent.length |
def travelled() = parent.length |
||
// Playing with weight of heuristic vs travelled so far. Giving equal weight take too long. |
|||
// Heuristic only will converge too fast on a longer than 52 steps solution. |
|||
⚫ | |||
// Find children/neighbour that is not himself. |
// Find children/neighbour that is not himself. |
||
def children: List[Board] = List(this.up(), this.down(), this.right(), this.left()).flatten |
def children: List[Board] = List(this.up(), this.down(), this.right(), this.left()).flatten |
||
Line 4,656: | Line 4,652: | ||
val res = mutable.Map[Int, (Int, Int)]() |
val res = mutable.Map[Int, (Int, Int)]() |
||
for (x ← 0 to 3; y ← 0 to 3) { |
for (x ← 0 to 3; y ← 0 to 3) { |
||
res(table(x |
res(table(x << 2 | y)) = (x, y) |
||
} |
} |
||
res.toMap |
res.toMap |
||
Line 4,666: | Line 4,662: | ||
val startHard = Board(Array(Array(0, 12, 9, 13), Array(15, 11, 10, 14), Array(3, 7, 2, 5), Array(4, 8, 6, 1)).flatten, 0, 0) |
val startHard = Board(Array(Array(0, 12, 9, 13), Array(15, 11, 10, 14), Array(3, 7, 2, 5), Array(4, 8, 6, 1)).flatten, 0, 0) |
||
} |
} |
||
⚫ | |||
object Solver extends App { |
object Solver extends App { |
||
⚫ | |||
⚫ | |||
// Setup weights for the heuristic, more weight to heuristic faster but longer solution. |
|||
⚫ | |||
⚫ | |||
implicit val ob = new Ordering[Board] { |
|||
⚫ | |||
aStar(y) - aStar(x) |
|||
} |
|||
} |
|||
val start = System.currentTimeMillis() |
val start = System.currentTimeMillis() |
||
var found = false |
var found = false |
||
Line 4,676: | Line 4,677: | ||
val pq: mutable.PriorityQueue[Board] = new mutable.PriorityQueue() |
val pq: mutable.PriorityQueue[Board] = new mutable.PriorityQueue() |
||
pq.enqueue(head) |
pq.enqueue(head) |
||
val visited = mutable.HashSet[String]() |
val visited = mutable.HashSet[String]() |
||
var explore = 0 |
var explore = 0 |
||
while (pq.nonEmpty && !found) { |
while (pq.nonEmpty && !found) { |
||
head = pq.dequeue() |
head = pq.dequeue() |
||
visited.add(head.key) |
visited.add(head.key) |
||
if (!head.key.equals(finalBoard.key)) { |
if (!head.key.equals(finalBoard.key)) { |
||
val newChildren = head.children.filter( |
val newChildren = head.children.filter(child ⇒ !visited.contains(child.key)) |
||
visited ++= (newChildren.map(_.key)) |
visited ++= (newChildren.map(_.key)) |
||
pq.enqueue(newChildren: _*) |
pq.enqueue(newChildren: _*) |
||
⚫ | |||
⚫ | |||
explore += 1 |
explore += 1 |
||
} else found = true |
} else found = true |
||
⚫ | |||
⚫ | |||
} |
} |
||
if (found) { |
if (found) { |
||
println(s"Exploring $explore states, found solution with length ${head.parent.length} for board:") |
println(s"Exploring $explore states, found solution with length ${head.parent.length} for board:") |
||
println(s"Weighted heuristic used $wHeuristic * heuristic + $wTravel * travel.") |
|||
println(initBoard.format) |
println(initBoard.format) |
||
println(head.parent.mkString.reverse) |
println(head.parent.mkString.reverse) |
||
Line 4,699: | Line 4,699: | ||
println("Total time: " + (System.currentTimeMillis() - start) / 1000.0 + " seconds") |
println("Total time: " + (System.currentTimeMillis() - start) / 1000.0 + " seconds") |
||
} |
} |
||
solve(startEasy) |
solve(startEasy, 4, 5) |
||
solve(startHard, 1, 2 ) |
|||
} |
} |
||
</lang> |
</lang> |
||
Line 4,706: | Line 4,707: | ||
<pre> |
<pre> |
||
Exploring 698181 states, found solution with length 52 for board: |
Exploring 698181 states, found solution with length 52 for board: |
||
Weighted heuristic used 5 * heuristic + 4 * travel. |
|||
15 14 1 6 |
15 14 1 6 |
||
9 11 4 12 |
9 11 4 12 |
||
Line 4,711: | Line 4,713: | ||
13 8 5 2 |
13 8 5 2 |
||
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd |
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd |
||
Total time: |
Total time: 48.884 seconds |
||
</pre> |
|||
Extra credits, not optimum solution but fast, using heuristic twice as the travel weight. |
|||
<pre> |
|||
# 5000: A* 111 g:95 h:8 q.size = 4318 |
|||
Exploring 6117 states, found solution with length 106 for board: |
|||
Weighted heuristic used 2 * heuristic + 1 * travel. |
|||
0 12 9 13 |
|||
15 11 10 14 |
|||
3 7 2 5 |
|||
4 8 6 1 |
|||
ddrrurdlulddruldrruluuldlddrruulldrrdruuuldlldrdruruuldldrrululdlurdddluurdrdluldrruluurrddldruulddrulurdd |
|||
Total time: 0.328 seconds |
|||
</pre> |
</pre> |