Introduction

If "simultaneously" means you must apply the same move sequence to every 4x4 maze at once, then the problem is not just running BFS on each maze separately. It becomes a single shortest-path search over a combined state space where one action, such as U or R, updates every maze position at the same time.

Model the Problem as a Product State

For one maze, a state is just the current cell. For k mazes solved together, a state is a tuple of k positions:

(p1, p2, ..., pk)

From that combined state, one move is chosen from:

• up
• down
• left
• right

The same chosen move is applied to every maze. If a move is blocked by a wall in one maze, that maze simply stays in place while the others move if they can.

The goal state is reached when every maze position is at its own exit cell.

Why Breadth-First Search Is the Right Tool

Each move has the same cost, so ordinary BFS gives the shortest sequence of simultaneous moves. The algorithm is:

1. start from the tuple of starting positions
2. try the four possible global moves
3. enqueue unseen combined states
4. stop when all mazes are solved

That gives the least number of moves by construction.

A Runnable Python Example

The code below uses simple adjacency maps rather than drawing maze walls directly. Each maze is a dictionary from a cell to the cells reachable by U, D, L, or R.

1from collections import deque
2
3MOVES = ("U", "D", "L", "R")
4
5
6def step(maze, position, move):
7    return maze[position].get(move, position)
8
9
10def solve_simultaneously(mazes, starts, goals):
11    start_state = tuple(starts)
12    goal_state = tuple(goals)
13
14    queue = deque([(start_state, "")])
15    seen = {start_state}
16
17    while queue:
18        state, path = queue.popleft()
19        if state == goal_state:
20            return path
21
22        for move in MOVES:
23            next_state = tuple(
24                step(maze, pos, move)
25                for maze, pos in zip(mazes, state)
26            )
27            if next_state not in seen:
28                seen.add(next_state)
29                queue.append((next_state, path + move))
30
31    return None
32
33
34maze_a = {
35    0: {"R": 1, "D": 4}, 1: {"L": 0, "R": 2}, 2: {"L": 1, "D": 6}, 3: {},
36    4: {"U": 0, "D": 8}, 5: {}, 6: {"U": 2, "D": 10}, 7: {},
37    8: {"U": 4, "R": 9}, 9: {"L": 8, "R": 10}, 10: {"L": 9, "U": 6, "D": 14}, 11: {},
38    12: {}, 13: {}, 14: {"U": 10, "R": 15}, 15: {"L": 14}
39}
40
41maze_b = {
42    0: {"D": 4}, 1: {"R": 2}, 2: {"L": 1, "D": 6}, 3: {},
43    4: {"U": 0, "R": 5}, 5: {"L": 4, "D": 9}, 6: {"U": 2, "D": 10}, 7: {},
44    8: {}, 9: {"U": 5, "R": 10}, 10: {"L": 9, "U": 6, "D": 14}, 11: {},
45    12: {}, 13: {}, 14: {"U": 10, "R": 15}, 15: {"L": 14}
46}
47
48path = solve_simultaneously(
49    [maze_a, maze_b],
50    starts=[0, 0],
51    goals=[15, 15],
52)
53
54print(path)
55print(len(path) if path is not None else "unsolved")

This BFS returns the shortest shared move sequence if one exists.

Why Solving Each Maze Separately Is Not Enough

If you solve each maze independently and then try to combine the answers, you usually lose optimality or feasibility. One maze may want U at a step where another needs R. The simultaneous version is constrained by one shared control stream, so the coupled search is the real problem.

That is why the product-state BFS is the correct model.

Complexity on 4x4 Mazes

Each individual maze has at most 16 positions. For k mazes, the worst-case combined state space is 16^k. That grows quickly, but 4x4 mazes are small enough that BFS can still be practical for a modest number of mazes, especially with pruning and symmetry reduction.

If you truly mean "all possible 4x4 mazes," the search space becomes enormous and you will need stronger compression or dynamic programming ideas. But for a fixed collection of mazes, product-state BFS is the standard exact method.

Common Pitfalls

• Running BFS on each maze independently even though the move sequence must be shared.
• Forgetting that a blocked move should usually leave that maze in place rather than invalidate the whole step.
• Treating this as a shortest-path problem in one maze instead of a shortest-path problem in the product graph.
• Underestimating the 16^k growth of the combined state space.
• Not storing visited combined states, which makes the search explode unnecessarily.

Summary

• If one move sequence controls all mazes, the correct state is the tuple of all positions.
• Use BFS on that combined state graph to get the least number of simultaneous moves.
• Independent per-maze shortest paths do not solve the coupled problem.
• For a modest number of 4x4 mazes, product-state BFS is exact and practical.
• The main challenge is managing state-space growth as the number of mazes increases.