This is a classical problem which has once appeared in some ACM/ICPC
regional contest. Obviously you should solve it by searching. Notice
two character of this problem: 1. The total state of this problem is 
not hugem, for each car has at most 5 possible positions and there
are not so many cars. 2. The result will not be very large and if you
consider the vertically cars that obstructs your car only you will 
get a considerable lower bound.

Since above we can design our searching algorithm by using IDA* 
(Iterative Deepening A*) and using a hash to eliminate the redundant
state. For randomized testdata which satisfies n=8, it will run in
1 second.