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

⚫
import Board._
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 * 4 + c) = table(rr * 4 + cc)
cTable(r << 2 | c) = table(rr << 2 | cc)
cTable(rr * 4 + cc) = table(r * 4 + c)
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.
⚫
def aStar() = heuristic() * 5 + travelled() * 4
// 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 * 4 + y)) = (x, y)
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)
}
}
⚫
import Board._

object Solver extends App {
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 aStar(b: Board) = wHeuristic * b.heuristic() + wTravel * b.travelled()
⚫
def solve(initBoard: Board) {
implicit val ob = new Ordering[Board] {
⚫
override def compare(x: Board, y: 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(b ⇒ !visited.contains(b.key))
val newChildren = head.children.filter(child ⇒ !visited.contains(child.key))
visited ++= (newChildren.map(_.key))
visited ++= (newChildren.map(_.key))
pq.enqueue(newChildren: _*)
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
explore += 1
} else found = true
} else found = true
⚫
if (explore % 5000 == 0)
⚫
println(s"# $explore: A* ${aStar(head)} g:${head.travelled()} h:${head.heuristic()} q.size = ${pq.size}")
}
}
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: 44.648 seconds
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>
Retrieved from "https://rosettacode.org/wiki/15_puzzle_solver"