Anonymous user
15 puzzle solver: Difference between revisions
→{{header|Scala}}
Line 4,609:
<lang Scala>
import scala.collection.mutable
import Board._▼
case class Board(table: Array[Int], r: Int, c: Int, parent: List[String] = List()) {
def cloneSwap(r: Int, c: Int, rr: Int, cc: Int) = {
val cTable = table.clone
cTable(r
cTable(rr
cTable
}
Line 4,634:
// Manhattan distance
def heuristic() = {
val posF = Board.finalBoard.positionMap
val posT = positionMap
var res = 0;
for (i ← 0 to 15) {
Line 4,647 ⟶ 4,646:
def key = table.mkString(",")
def travelled() = parent.length
def aStar() = heuristic() * 5 + travelled() * 4▼
// Find children/neighbour that is not himself.
def children: List[Board] = List(this.up(), this.down(), this.right(), this.left()).flatten
Line 4,656 ⟶ 4,652:
val res = mutable.Map[Int, (Int, Int)]()
for (x ← 0 to 3; y ← 0 to 3) {
res(table(x
}
res.toMap
Line 4,666 ⟶ 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)
}
▲import Board._
object Solver extends App {
def solve(initBoard: Board, wTravel:Int, wHeuristic: Int ) {▼
implicit val ob = new Ordering[Board] { override def compare(x: Board, y: Board) = { y.aStar() - x.aStar() } }▼
// Setup weights for the heuristic, more weight to heuristic faster but longer solution.
▲ def solve(initBoard: Board) {
implicit val ob = new Ordering[Board] {
▲
aStar(y) - aStar(x)
}
}
val start = System.currentTimeMillis()
var found = false
Line 4,676 ⟶ 4,677:
val pq: mutable.PriorityQueue[Board] = new mutable.PriorityQueue()
pq.enqueue(head)
val visited = mutable.HashSet[String]()
var explore = 0
while (pq.nonEmpty && !found) {
head = pq.dequeue()
visited.add(head.key)
if (!head.key.equals(finalBoard.key)) {
val newChildren = head.children.filter(
visited ++= (newChildren.map(_.key))
pq.enqueue(newChildren: _*)
if (explore % 10000 == 0)▼
println(s"# $explore: A* ${head.aStar()} g:${head.travelled()} h:${head.heuristic()} q.size = ${pq.size}")▼
explore += 1
} else found = true
▲
}
if (found) {
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(head.parent.mkString.reverse)
Line 4,699:
println("Total time: " + (System.currentTimeMillis() - start) / 1000.0 + " seconds")
}
solve(startEasy, 4, 5)
solve(startHard, 1, 2 )
}
</lang>
Line 4,706 ⟶ 4,707:
<pre>
Exploring 698181 states, found solution with length 52 for board:
Weighted heuristic used 5 * heuristic + 4 * travel.
15 14 1 6
9 11 4 12
Line 4,711 ⟶ 4,713:
13 8 5 2
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd
Total time:
</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>
| |||