I am trying to solve the 8 puzzle using A* Search for an assignment. I will be given an initial state and a goal state that I have to use to reach using the A* algorithm to reach the optimal path. My approach is to take the initial state as a list, then generate its successor states that can be generated based on the ways I can move the blank square(represented by 0). Then for each of the successor states I can calculate the heuristic, the Manhattan distance which I can use as the priority for a priority queue.
For example, if my initial state is [1,2,3,0,4,5,6,7,8]: 0 , the child states would be [0,2,3,1,4,5,6,7,8]: x, [1,2,3,4,0,6,7,8] : x and [1,2,3,6,4,5,0,7,8]: x. I don't know how to represent this as a graph, choose the lowest priority state and then expand that.
I am not sure where to go from here. How do I add the parent state and successor to a graph so I can do A*?
CodePudding user response：
Current position is start node of graph. Then you could use a standard for yourself. Two nodes in graph are adjacent if they are reachable from each others. The label of your graph is a string consist of current numbers in your list.
for example the initial state is
initial = [ [ 1, 2, 3 ],
[ 5, 6, 0 ],
[ 7, 8, 4 ] ]
and final state is
final = [ [ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 0 ] ]
Choose whom structure you are convince with.
Also, A* is a proper algorithm to solve n-puzzle.
Solving 8-Puzzle using A* Algorithm.
8 puzzle Problem using Branch And Bound
CodePudding user response：
In order to build a graph, you need a function that, given a state, will find all the states that are "one move away" from it.
When you implement that A* algorithm, though, the only thing you would use that graph for is finding all the states that are "one move away" from the state you're currently processing.
Don't bother building a graph. Just use the function.