# Search algorithm for vehicles moving through a square grid

I started to learn AI and I'm trying to solve the following problem like a search problem and I'm wondering which search algorithm would be the best in this case. Please give me at least some tips, I would be very thankful.

Problem statement:

$$n$$ vehicles occupy squares $$(1, 1)$$ through $$(n, 1)$$ (i.e., the bottom row) of an $$n \times 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 assume the goal is to find the fastest solution (smallest number of time steps)? – 6005 May 7 at 14:57
• What did you try? What approaches did you consider? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. May 8 at 4:50
• Please credit the original source of this problem. We require that you always attribute the source of all copied material. – D.W. May 8 at 4:51