Understanding Performance Bottlenecks in Python BFS Solvers

Building a Breadth-First Search (BFS) solver for sliding block puzzles like Rush Hour is a classic algorithmic exercise. While BFS is conceptually straightforward, implementing it efficiently in Python requires paying close attention to data structures and memory representation. If your solver is taking several seconds for paths with only 6 steps, you are likely suffering from high-overhead operations inside your core loop.

Looking at the profiling data (cProfile) from the implementation reveals the two main culprits:

  • NumPy Overhead on Small Arrays: Operations like np.flatnonzero, np.append, np.unique, and np.concatenate carry significant Python C-API wrapper overhead. When called millions of times on tiny 6x6 arrays, NumPy becomes 10x to 100x slower than pure Python.
  • Costly State Serialization & Queue Inefficiencies: Converting arrays to strings using ' '.join(board_arr.astype(str)) inside the core loop, combined with using list.pop(0) (an $O(N)$ operation), introduces heavy time and memory penalties.

Key Optimization Strategies

1. Ditch NumPy for Pure Python Primitive Types

NumPy excels at vectorized mathematical operations on large arrays. For small, state-space tree searches (like a 36-element board), native Python immutable types like tuple or bytes are orders of magnitude faster.

2. Use collections.deque for BFS Queue

Python's native list list.pop(0) takes $O(N)$ time because all subsequent elements must be shifted in memory. Replacing the queue with collections.deque allows $O(1)$ pops from the left using popleft().

3. Model Cars as Fixed Metadata

Instead of scanning the whole board using np.unique() and np.flatnonzero() on every state to determine vehicle orientation and position, maintain an initial list of cars (their ID, length, and orientation). A state only needs to track each car's top-left position (or index).

Optimized Rush Hour BFS Implementation

Here is a clean, highly optimized implementation using pure Python tuples and deque:

from collections import deque
from typing import NamedTuple, Tuple, List, Optional, Dict

BOARD_SIZE = 6

class Car(NamedTuple):
    id: int
    length: int
    is_vertical: bool

def solve_rush_hour(cars: List[Car], initial_positions: Tuple[int, ...], target_car_id: int = -1):
    """
    Solves Rush Hour using an optimized BFS approach.
    
    :param cars: Static metadata for each vehicle.
    :param initial_positions: Tuple containing the index of the top/leftmost cell for each car.
    :param target_car_id: ID of the primary vehicle that needs to reach the exit.
    """
    target_idx = next(i for i, car in enumerate(cars) if car.id == target_car_id)
    
    # Queue stores: (positions_tuple, steps_count)
    queue = deque([(initial_positions, 0)])
    visited: Dict[Tuple[int, ...], Optional[Tuple[int, ...]]] = {initial_positions: None}
    
    def get_board(positions: Tuple[int, ...]) -> List[int]:
        grid = [0] * (BOARD_SIZE * BOARD_SIZE)
        for i, car in enumerate(cars):
            pos = positions[i]
            step = BOARD_SIZE if car.is_vertical else 1
            for l in range(car.length):
                grid[pos + l * step] = car.id
        return grid

    while queue:
        current_pos, dist = queue.popleft()
        
        # Target vehicle reached the exit (row 2, column 4 for 6x6 grid standard)
        if current_pos[target_idx] % BOARD_SIZE == 4:
            return dist, current_pos
            
        board = get_board(current_pos)
        
        # Explore valid moves for each car
        for i, car in enumerate(cars):
            pos = current_pos[i]
            step = BOARD_SIZE if car.is_vertical else 1
            
            # Move Backward / Up
            for shift in range(1, BOARD_SIZE):
                new_pos = pos - shift * step
                if car.is_vertical:
                    if new_pos < 0 or board[new_pos] != 0:
                        break
                else:
                    if new_pos // BOARD_SIZE != pos // BOARD_SIZE or board[new_pos] != 0:
                        break
                
                next_state = list(current_pos)
                next_state[i] = new_pos
                next_state_tuple = tuple(next_state)
                
                if next_state_tuple not in visited:
                    visited[next_state_tuple] = current_pos
                    queue.append((next_state_tuple, dist + 1))

            # Move Forward / Down
            for shift in range(1, BOARD_SIZE):
                tail_pos = pos + (car.length - 1) * step
                new_tail_pos = tail_pos + shift * step
                new_pos = pos + shift * step
                
                if car.is_vertical:
                    if new_tail_pos >= BOARD_SIZE * BOARD_SIZE or board[new_tail_pos] != 0:
                        break
                else:
                    if new_tail_pos // BOARD_SIZE != tail_pos // BOARD_SIZE or board[new_tail_pos] != 0:
                        break
                
                next_state = list(current_pos)
                next_state[i] = new_pos
                next_state_tuple = tuple(next_state)
                
                if next_state_tuple not in visited:
                    visited[next_state_tuple] = current_pos
                    queue.append((next_state_tuple, dist + 1))
                    
    return -1, None # No solution found

Why This Approach is Faster

  • Minimal State Representation: State keys are tuples of vehicle coordinates (e.g., (12, 0, 14, ...)), allowing hash lookups and comparisons to run in nanoseconds.
  • No String Formatting Overhead: Eliminates millions of calls to .astype(str) and string concatenation.
  • Constant Time Queue Pops: deque.popleft() executes in $O(1)$ time, eliminating the overhead of standard list shifting.