8 Piece sliding puzzle
Attempt at solving 8 piece sliding puzzles. Commentary below. Make sure that you enter legal positions as an illegal start or end state will cause the script to fail to halt
Based on lesson 2.1 of Edinburgh AI planning course.
Commentary
Implements the A* algorithm.
All children of the current position are found and added to the array of fringe states.
The fringe states are then sorted by their Manhattan distance from the target plus their depth from the start and the closest is selected
f(n) = g(n) + h(n)
f(n) is the evaluation function.
g(n) is the exact distance (known) from the start position.
h(n) is the heuristic distance (estimated) to the goal.
If h(n) = 0 then A* is equivalent to Dijkstra's algorithm. The shortest path will be found but a lot of nodes are searched.
If h(n) < true distance - then the shortest path will be found and fewer nodes tested than with D's
If h(n) = true distance - then the shortest path will be the only path used and found.
If h(n) %gt; true distance - then the shortest path might not be found at all.
Repeat until either the target is found or the computer times out.
Distance Functions
The speed of A* depends on the accuracy of the heuristic function.
Hamming Distance.
For strings of identical length this is simply the number of letters that are in the wrong place.
Manhattan Distance
WIKI - Manhattan Distance. This is the number of moves on a grid needed to put each letter back in its right place.