15 puzzle solver: Difference between revisions
Content added Content deleted
(Scala solution, quite slow using A* with some trial and error weighting.) |
(→{{header|Scala}}: Use 2.12 compatible, previously was 2.13.2) |
||
Line 4,649: | Line 4,649: | ||
// Playing with weight of heuristic vs travelled so far. Giving equal weight take too long. |
// 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. |
// Heuristic only will converge too fast on a longer than 52 steps solution. |
||
def aStar() = heuristic() * |
def aStar() = heuristic() * 3 + travelled() * 2 |
||
// 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,674: | Line 4,674: | ||
var found = false |
var found = false |
||
var head = initBoard |
var head = initBoard |
||
val pq: mutable.PriorityQueue[Board] = mutable.PriorityQueue |
val pq: mutable.PriorityQueue[Board] = new mutable.PriorityQueue() |
||
pq.enqueue(head) |
|||
val visited = mutable.HashSet[String]() |
val visited = mutable.HashSet[String]() |
||
var explore = 0 |
var explore = 0 |
||
Line 4,683: | Line 4,685: | ||
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(b ⇒ !visited.contains(b.key)) |
||
visited |
visited ++= (newChildren.map(_.key)) |
||
pq.enqueue(newChildren: _*) |
pq.enqueue(newChildren: _*) |
||
if (explore % 10000 == 0) |
if (explore % 10000 == 0) |