CODEWITHSUNDEEP
calgorithmsearcha-star
Jemo
Jemo

Reputation: 309

Using A* search algorithm to solve 3x3 three-dimensional box puzzle?

I am working on a 3x3 three-dimensional box puzzle problem in my homework. I will code with C.

Image of the puzzle

There are 26 boxes and at first, first place is empty. By sliding boxes I must arrange them in correct order. Red numbers shows correct order and 27th place must be empty at last. I do not want you to give me code; I searched in forums and it seems that I must use the A* search algorithm, but how?

Can you give me tips about how I can use the A* algorithm on this problem? What type of data structure should I use?

Upvotes: 10

Views: 2276

Answers (2)

amit
amit

Reputation: 178481

Define your problem as a states-graph:
G=(V,E) where V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in} [each number is representing a single 'square' on the 3d board].
and define E={(v1,v2)| it is possible to move from state v1 to state v2 with a single step} an alternative definition [identical] for E is by using the function successors(v):
For each v in V: successors(v)={all possible boards you can get, with 1 step from v}

You will also need an admissible heuristic function, a pretty good one for this problem can be: h(state)=Sigma(manhattan_distance(x_i)) where i in range [1,54]) basically, it is the summation of manhattan distances for each number from its target.

Now, once we got this data, we can start running A* on the defined graph G, with the defined heuristic. And since our heuristic function is admissible [convince yourself why!], it is guaranteed that the solution A* finds will be optimal, due to admissibility and optimality of A*.
Finding the actual path: A* will end when you develop the target state. [x_i=i in the terms we used earlier]. You will find your path to it by stepping back from the target to the source, using the parent field in each node.

Upvotes: 5

hugomg
hugomg

Reputation: 69954

You know how graphs work and how A* finds shortest paths on them, right?

The basic idea is that each configuration of the puzzle can be considered a vertex in a graph and the edges represent the moves (by connecting the configurations before and after the move).

Finding a set of moves that leads from an original configuration to a desired one can be seen as a path finding problem.

Upvotes: 3

Related Questions