'How to represent states for an 8 Puzzle in a graph

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*?

algorithmsearchgrapha-star


Solution 1:[1]

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

8 puzzle problem

Solution 2:[2]

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.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 Matt Timmermans

Related Questions