My team got this as A* algorithm assignment in Artificial Intelligence class few years ago taught by Mrs. Afiahayati, Ph.D. We should create an implementation of A* algorithm (read: “A” Star) to solve 8 puzzle problem. This puzzle problem is the small version of 15 sliding puzzle game.
In my opinion A* Algorithm (read more about it here) is looks like combination of Breadth First Search (BFS) and Depth First Search (DFS) algorithm (or maybe Dijkstra’s too(?)). It’s using Heuristic scoring to estimate the step from vertex to goal so make the system may running faster, and like Dijkstra’s, it’s a complete search which always finding a best solution. Read this to get better explanation.
My team agreed to use Manhattan distance to estimate distance between the current state and the goal state (h) and count the number of step as exact cost (g).
I wrote the code using Python. And after several hours coding I found python have a “magical” function that make easy to write 🙂 My first implementation was not using any class at all and it made the code hard to read. After I saw this implementation, I realize that code is much prettier than mine, so I rewrite my code using Node class with similar class concept from that code.
See the complete source code on Github