what is an appropriate tree class in java that use to solve 8 puzzle.

Question

I'm doing an AI for 8 puzzle that develop on java. I have 1 class that keep the 2 dimension array of string that is a 8 puzzle board. This class also keep other necessary information. The question what is an appropriate tree that i will use to keep each object.

Answer 1

I can't see why you would want to use a tree.

If you're after solving an 8-puzzle in as few moves as possible, what you're after is actually finding the shortest path from the current configuration to the "solved" configuration in a graph where vertices are configurations and edges are moves.

The shortest path can be solved with for instance a breadth-first search.

I think this code explains it fairly well: http://www.dreamincode.net/code/snippet1914.htm

The (implicit) graph could mentally be pictured as a tree, but what is being depicted is more like the control flow of the algorithm.

Answer 2

You may want to consider using A* search for this. A good explanation of the algorithm can be found here.