Minimum Moves (Grid Path)

Question

How can i find the number of minimum moves for a given path with nxn grid to bring both players at each end together on any node?

Below example is for 6x6 grid and each player can move only within given direction. So for the first direction lets say if we move "left" only green can move left and then if we move "up" both red and green can move up and so on. Can we find the minimum number of moves required to move each circle to the same node? What could be the type of algorithm that I should be searching for (shortest path, longest path etc.)

Thanks

Answer 1

This seems like a job for dynamic programming. This means that we do the problem backwards in a sense. In any case where both players can move in the same direction, we obviously want to move in that direction. When we have a choice of two directions to move, we want to move in the direction that leaves the position requiring fewer steps.

Therefore, we start by computing the minimum number of steps required to move from positions where the players are close together, and keep track of the results. Then we increase the distance by $1$, and use the saved values to compute the new move requirements.

We can modify this to keep track of what the best move is in each case.

I wrote the following python script to do this.

green = 'XLULDLLLURRUURDRUULLLDDLUUURRRRRDDDDY'
table = green.maketrans('LRUD', 'RLDU')
red = green.translate(table)
N = len(green)
distance = { }
step = { }

for n in range(N):
    distance[n,n] = 0
for k in range(1, N):
    for n in range(N-k):
        if green[n+1] == red[n+k-1]:
            distance[n,n+k] = 1 + distance[n+1,n+k-1]
            step[n,n+k] = green[n+1]
        elif distance[n,n+k-1] <= distance[n+1,n+k]:
            distance[n,n+k] = 1 + distance[n,n+k-1]
            step[n,n+k] = red[n+k-1]
        else:
            distance[n,n+k] = 1 + distance[n+1,n+k]
            step[n,n+k] = green[n+1]

print(f'{distance[0,N-1]} steps required')
G = 0
R = N-1
steps = ''
while G < R:
    s = step[G,R]
    steps += s
    if s == green[G+1]:
        G += 1
    if s == red[R-1]:
        R  -= 1
print(steps)

In the green path, X and Y are just placeholders for the starting positions, and U,D,L,R are the moves needed to get to that cell. The red path is the same as the green, with the directions reversed.

The program produces the following output:

26 steps required
UUUULULDLLLDDDRUURRUURDDLU 

So, if I haven't made any mistakes, $26$ steps are required, the first $4$ of which are "up", and so on.

I haven't checked this script carefully at all. You should probably make some small cases that you can solve by hand, and test the script on them. Let me know of any problems, please.

Answer 2

One algorithm that works is breadth first search. The state space consists of ordered quadruplets $(x_1,y_1,x_2,y_2)$, where $(x_1,y_1)$ are the coordinates of the first piece and $(x_2,y_2)$ are the coordinates of the second piece. The program would maintain

• a queue of states, initially only containing the initial state,
• a set of visited states, initially containing the initial state,
• a dictionary which records the how each state was reached, initially with no entries.

It then repeatedly dequeues a state $s$ from the queue, adds $s$ to the set of visited states, and then enqueues the four states reachable from $s$ attained by pressing up, down, left and right which have not already been visited. This is where specifics of the maze have to be used; if there is a wall to the right of $(x_1,y_1)$, then $x_1$ is not increased by pressing right, but otherwise, pressing right increases $x_1$ by one. This continues until a state where $x_1=x_2$ and $y_1=y_2$ is dequeued.

Furthermore, for each state $t$ added to the queue, a dictionary entry with key $t$ and value $s$ is added to the dictionary. That way, when the algorithm stops, you can backtrack from the final state to find the path which led to it. That is, if the final state is $f_0$, use the dictionary to find the state $f_1$ which lead to it, then the state $f_2$ which led to $f_1$, and so on until you get back to the start state. By using a queue, it is ensured that the resulting path is indeed the shortest path.