8 puzzle solving using A*: a child node repeating its ancestor's state

Question

suppose that we have an 8 puzzle problem, and the empty tile is marked by ZERO. The goal state is :

• 1 2 3
• 4 5 6
• 7 8 0

the initial state is:

• 0 1 3
• 8 2 4
• 7 6 5

... my question is, is it possible for a child in an A* tree to "copy" or have the same state of its ancestor(s)? or will "f(n) = g(h) + h(n)" [where g(h) = # of moves made... h(n) = sum of manhattan distances of each tile] already make this impossible and therefore i don't need to worry about this?.. for example, from the initial state:

• 0 1 3
• 8 2 4
• 7 6 5

then the following states happen, thus making more child nodes in the A* tree

(action: up)

• 8 1 3
• 0 2 4
• 7 6 5

action: left

• 8 1 3
• 2 0 4
• 7 6 5

action: down

• 8 0 3
• 2 1 4
• 7 6 5

action: right

• 0 8 3
• 2 1 4
• 7 6 5

action: up

• 2 8 3
• 0 1 4
• 7 6 5

... then actions: left, down, right, up, left, down, right happens... thus leaving the state back to that of the initial state:

• 0 1 3
• 8 2 4
• 7 6 5

is this possible in an A* search of an 8 puzzle? or will f(n) take care of this problem? thanks to those who will answer, any help would be appreciated!

Answer 1

You do not have to worry about the situation you are describing in your question. The beginning state is expanded in the first iteration of A*, which leads the algorithm to include that node in the CLOSED list with an associated cost (which is zero, as it is the initial state). If you find that state again as successor of any other state, the algorithm will find that state in the CLOSED list with a lower cost and it will not be expanded again, discarding that branch in the search tree.

If you are going to implement this problem in Java, maybe you will find useful to use an heuristic search library like Hipster. This library is open-source (see at Github) and has some examples of search problems solved with it. Including the 8-puzzle problem solved with A*.

I hope my answer helps,