I need to implement the following requirment, using a search algorithm(A STAR, BEST FIRST):

n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n×n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n−i+1, n). On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.

I determined hi formula |n – 1 + i – xi| + |n – yi|

For gi formula:

```
gi = g(i-1), for STAY
gi = g(i-1) + 1, for a simple move
gi = g(i-1) + 2, for a simple hop
```

But I don’t know how to implement an appropriate code for this problem, my attempts generating infinite cycles.

Can you help me with suggestions on whici search algorithm would be most suitable and how I could implement it ?

Source: Windows Questions C++