15 puzzle solver: Difference between revisions

Content added Content deleted

Inline

@@ Line 4,604: / Line 4,604: @@
 {{out}}
 <pre>Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd</pre>
+=={{header|Scala}}==
+<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 * 4 + c) = table(rr * 4 + cc)
+    cTable(rr * 4 + cc) = table(r * 4 + c)
+    cTable
+  }
+  def up() =
+    if (r > 0) { Some(Board(cloneSwap(r, c, r - 1, c), r - 1, c, "u" :: parent))
+    } else None
+  def down() =
+    if (r < 3) { Some(Board(cloneSwap(r, c, r + 1, c), r + 1, c, "d" :: parent))
+    } else None
+  def left() =
+    if (c > 0) { Some(Board(cloneSwap(r, c, r, c - 1), r, c - 1, "l" :: parent))
+    } else None
+  def right() =
+    if (c < 3) { Some(Board(cloneSwap(r, c, r, c + 1), r, c + 1, "r" :: parent))
+    } else None
+  def format: String = {
+    table.sliding(4, 4).toList.map(_.map(i ⇒ f"$i%4d").mkString).mkString("\n")
+  }
+  // Manhattan distance
+  def heuristic() = {
+    val posF = finalBoard.positionMap
+    val posT = positionMap
+    var res = 0;
+    for (i ← 0 to 15) {
+      val (x, y) = posF(i)
+      val (xx, yy) = posT(i)
+      res += (Math.abs(x - xx) + Math.abs(y - yy))
+    }
+    res
+  }
+  def key = table.mkString(",")
+  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.
+  def children: List[Board] = List(this.up(), this.down(), this.right(), this.left()).flatten
+  // Map number to positions
+  lazy val positionMap: Map[Int, (Int, Int)] = {
+    val res = mutable.Map[Int, (Int, Int)]()
+    for (x ← 0 to 3; y ← 0 to 3) {
+      res(table(x * 4 + y)) = (x, y)
+    }
+    res.toMap
+  }
+}
+object Board {
+  val finalBoard = Board(Array(Array(1, 2, 3, 4), Array(5, 6, 7, 8), Array(9, 10, 11, 12), Array(13, 14, 15, 0)).flatten, 3, 3)
+  val startEasy = Board(Array(Array(15, 14, 1, 6), Array(9, 11, 4, 12), Array(0, 10, 7, 3), Array(13, 8, 5, 2)).flatten, 2, 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 {
+  implicit val ob = new Ordering[Board] { override def compare(x: Board, y: Board) = { y.aStar() - x.aStar() } }
+  def solve(initBoard: Board) {
+    val start = System.currentTimeMillis()
+    var found = false
+    var head = initBoard
+    val pq: mutable.PriorityQueue[Board] = mutable.PriorityQueue.from(List(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(b ⇒ !visited.contains(b.key))
+        visited.addAll(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(initBoard.format)
+      println(head.parent.mkString.reverse)
+    }
+    println("Total time: " + (System.currentTimeMillis() - start) / 1000.0 + " seconds")
+  }
+  solve(startEasy)
+}
+</lang>
+{{out}}
+<pre>
+Exploring 698181 states, found solution with length 52 for board:
+14   1   6
+11   4  12
+10   7   3
+8   5   2
+rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd
+Total time: 44.648 seconds
+</pre>