I'm developing a 8 Puzzle game solver in python lately and I need a bit of help So far I finished coding the A* algorithm using Manhattan distance as a heuristic function.
The solver runs and find ~60% of the solutions in less than 2 seconds However, for the other ~40%, my solver can take up to 20-30 minutes, like it was running without heuristic.
I started troubleshooting, and it seems that the openset I use is causing some problems :
I have the feeling that O(n) is way too much to run a decent A* algorithm with such memory used so I wanted to know how should I manage to make the openset less "time eater"
Thank you for your help ! Have a good day
EDIT: FIXED
I solved my problem which was in fact a double problem.
I tried to use a dictionary instead of an array, in which I stored the nodes by their f(n) value and that allowed me to run the solver and the ~181000 possibilities of the game in a few seconds
The second problem (I didn't know about it because of the first), is that I didn't know about the solvability of a puzzle game and as I randomised the initial node, 50% of the puzzles couldn't be solved. That's why it took so long with the openset as the array.
The open set should be a priority queue. Typically these are implemented using a binary heap, though other implementations exist.
Neither an array-list nor a dictionary would be efficient.
The closed set should be an efficient set, so usually a hash table or binary search tree, depending on what your language's standard library defaults to.
A dictionary (aka "map") would technically work, but it's conceptually the wrong data-structure because you're not mapping to anything. An array-list would not be efficient.