In this post, I present a solution to the Rush Hour problem appying A* algorithm developed with ChatGPT. A human programmer would typically use more descriptive data structures to make the code easier to follow. The initial solution didn’t work because the problem instance itself was invalid, but the algorithm was correct. Attempts to prompt ChatGPT to refactor the code for readability resulted in broken implementations, so I’ve decided to share the original version as it is.
Why A*?
A* (pronounced “A-Star”) is a search method that finds shortest paths or optimal solutions in graphs – more efficiently than brute force. It combines:
- what we’ve already paid (
g-cost: cost from the start to the current state), - with a reasonable guess of what’s left (
h-heuristic: estimated cost to the goal).
Together this gives the priority
![\[f(n)=g(n)+h(n),\]](https://phabe.ch/wp-content/ql-cache/quicklatex.com-957597a25a3ab0bf896c1010475a0726_l3.png "Rendered by QuickLaTeX.com")
and A* always expands the node with the smallest f. The heuristic guides the search towards the goal.
Guarantees:
If 
is admissible (never overestimates), A* returns an optimal solution. If is even consistent (satisfies the triangle inequality), A* is especially stable and efficient.
The Ingredients for A* (in general)
To use A*, we need:
- States: a precise description of “where we are” (e.g., game position).
- Actions/Neighbors: what states can we reach in one step?
- Cost model
g: what does a step cost? (constant 1, distance, time, …) - Goal test: recognize when we’re done.
- Heuristic
h: estimate of remaining cost to the goal. - Data structures:
- Open list (priority queue/heap) sorted by
f=g+h, - g-scores (best known cost per state),
- Parent pointers (to reconstruct the solution path at the end).
- Open list (priority queue/heap) sorted by
Basic loop:
- Start with the initial state in the open list.
- Pop the state with the smallest
f. - If it’s the goal → reconstruct path from goal to start and finish.
- Otherwise, generate neighbors, update their
g, computeh, push them into the open list if improved. - Repeat until solved or no states left.
Rush Hour as a Search Problem
Game idea: The red car must exit through the opening on the right edge. Cars are either horizontal or vertical and may only move along their axis.
1) State
A state is the position of each car. For efficiency, we only store the variable coordinate:
- Horizontal car: the leftmost column (anchor),
- Vertical car: the topmost row (anchor).
In the solver, this is a tuple of integers: state = (p_X, p_A, p_B, …).
2) Actions/Neighbors
A move means: one car slides along its axis any number of free cells (contiguously) – counts as one move.
For each state and each car:
- check how far it can move left/right (horizontal) or up/down (vertical),
- generate a neighbor state for each reachable end position.
In the code this is done by moves(...). Beforehand, occ(...) builds an occupancy grid to quickly check if cells are free.
3) Cost model g
Every move costs 1. This reflects the classic Rush Hour definition: minimize the number of moves (not the number of cells moved).
4) Goal test
We’re done when the right edge of the red car reaches the right border of the board (the exit).
In the code: is_goal(...).
5) Heuristic h (admissible & simple)
A very effective and admissible estimate is:
Count the cars that block the red car in its exit row, plus 1 (for the final red move).
Why admissible?
- Each blocking car must be moved at least once.
- The red car itself needs at least one move to exit.
- We never overestimate, so A* stays optimal.
In the code: h(...) counts blockers in the exit row and adds 1, unless the goal is already reached.
Conclusion – and the Code
We’ve built A* step by step and applied it to Rush Hour:
- States = car anchors,
- Actions = sliding cars any distance along their axis,
- Cost = 1 per move,
- Heuristic = blockers in exit row + 1,
- Open-list driven expansion until the goal, then path reconstruction.
The compact Python solver (A* + heuristic) is provided beneath. Keep in mind, that it’s worst case complexity is exponential. However, with a decent heuristic and 6×6 boards it’s very fast. If you’d like to dig deeper, focus on:
moves(...): neighbor generation (slide each car while checking free cells).solve(...): priority computationg+hin the heap – the heart of A*.parent: reconstructs the move sequence backward from the goal.
Next steps could include experimenting with alternative search strategies (IDA*), stronger heuristics, bidirectional search, or even comparing with a MILP formulation.
#!/usr/bin/env python3
"""Rush Hour (6x6) solver using A* with memoization.
Minimal English comments and Google-style docstrings.
"""
from dataclasses import dataclass
from typing import Dict, List, Tuple, Optional, Iterable, Set
import json
import heapq
@dataclass(frozen=True)
class Vehicle:
"""Represents a vehicle on the board.
Attributes:
id: Vehicle identifier. Red car must be "X".
row: Top-left row (0-based).
col: Top-left column (0-based).
length: Vehicle length (2 or 3).
orientation: 'H' for horizontal, 'V' for vertical.
"""
id: str
row: int
col: int
length: int
orientation: str
def cells(self, var_pos: int) -> List[Tuple[int, int]]:
"""Return occupied cells given the variable coordinate.
For horizontal vehicles, ``var_pos`` is the column; for vertical, the row.
Args:
var_pos: Variable coordinate along the movement axis.
Returns:
List of (row, col) cell coordinates occupied by the vehicle.
"""
if self.orientation == 'H':
r = self.row
c0 = var_pos
return [(r, c0 + k) for k in range(self.length)]
else:
c = self.col
r0 = var_pos
return [(r0 + k, c) for k in range(self.length)]
@dataclass
class Puzzle:
"""Rush Hour puzzle definition and state helpers."""
board_size: int
exit_row: int
vehicles: List[Vehicle]
def __post_init__(self):
"""Normalize vehicles and validate initial placement."""
xs = [v for v in self.vehicles if v.id == 'X']
if not xs:
raise ValueError("Missing red vehicle with id 'X'.")
if xs[0].orientation != 'H':
raise ValueError("Red vehicle 'X' must be horizontal.")
if xs[0].row != self.exit_row:
raise ValueError("Red vehicle 'X' must be placed on exit_row.")
others = [v for v in self.vehicles if v.id != 'X']
others.sort(key=lambda v: v.id)
self.vehicles = [xs[0]] + others
self._validate_initial()
def _validate_initial(self):
"""Validate bounds and collisions in the starting position."""
n = self.board_size
occ = [[None for _ in range(n)] for _ in range(n)]
for v in self.vehicles:
if v.length not in (2, 3):
raise ValueError(f"Vehicle {v.id}: invalid length {v.length}")
if v.orientation not in ('H', 'V'):
raise ValueError(f"Vehicle {v.id}: invalid orientation {v.orientation}")
if v.orientation == 'H':
if not (0 <= v.row < n):
raise ValueError(f"Vehicle {v.id}: row out of bounds")
if not (0 <= v.col <= n - v.length):
raise ValueError(f"Vehicle {v.id}: col out of bounds")
for k in range(v.length):
r, c = v.row, v.col + k
if occ[r][c] is not None:
raise ValueError(
f"Start overlap: {v.id} overlaps {occ[r][c]}"
)
occ[r][c] = v.id
else:
if not (0 <= v.col < n):
raise ValueError(f"Vehicle {v.id}: col out of bounds")
if not (0 <= v.row <= n - v.length):
raise ValueError(f"Vehicle {v.id}: row out of bounds")
for k in range(v.length):
r, c = v.row + k, v.col
if occ[r][c] is not None:
raise ValueError(
f"Start overlap: {v.id} overlaps {occ[r][c]}"
)
occ[r][c] = v.id
if not (0 <= self.exit_row < n):
raise ValueError("exit_row out of bounds")
def start_state(self) -> Tuple[int, ...]:
"""Return the compressed start state.
Returns:
Tuple of variable positions per vehicle: col for H, row for V.
"""
s = []
for v in self.vehicles:
s.append(v.col if v.orientation == 'H' else v.row)
return tuple(s)
def is_goal(self, state: Tuple[int, ...]) -> bool:
"""Check if red car reaches the exit.
Args:
state: Compressed state.
Returns:
True if the red car's right edge is at the board's right border.
"""
red = self.vehicles[0]
col = state[0]
right_edge = col + red.length - 1
return right_edge == self.board_size - 1
def occupancy(self, state: Tuple[int, ...]) -> List[List[Optional[int]]]:
"""Build an occupancy grid indexed by vehicle index.
Args:
state: Compressed state.
Returns:
2D grid with vehicle indices or None per cell.
"""
n = self.board_size
occ: List[List[Optional[int]]] = [[None for _ in range(n)] for _ in range(n)]
for i, v in enumerate(self.vehicles):
var = state[i]
for r, c in v.cells(var):
occ[r][c] = i
return occ
def generate_moves(self, state: Tuple[int, ...]) -> Iterable[Tuple[Tuple[int, ...], Tuple[str, str, int]]]:
"""Yield next states and move descriptors.
A *move* is any contiguous shift of a single vehicle by ≥1 cells.
Args:
state: Compressed state.
Yields:
Tuples of (next_state, (vehicle_id, direction, steps)).
Direction is 'L'/'R' for horizontal and 'U'/'D' for vertical.
"""
n = self.board_size
occ = self.occupancy(state)
for i, v in enumerate(self.vehicles):
var = state[i]
if v.orientation == 'H':
r = v.row
# Move left
steps = 0
c_left = var - 1
while c_left >= 0 and occ[r][c_left] is None:
steps += 1
new_state = list(state)
new_state[i] = var - steps
yield (tuple(new_state), (v.id, 'L', steps))
c_left -= 1
# Move right
steps = 0
c_right = var + v.length
while c_right < n and occ[r][c_right] is None:
steps += 1
new_state = list(state)
new_state[i] = var + steps
yield (tuple(new_state), (v.id, 'R', steps))
c_right += 1
else:
c = v.col
# Move up
steps = 0
r_up = var - 1
while r_up >= 0 and occ[r_up][c] is None:
steps += 1
new_state = list(state)
new_state[i] = var - steps
yield (tuple(new_state), (v.id, 'U', steps))
r_up -= 1
# Move down
steps = 0
r_down = var + v.length
while r_down < n and occ[r_down][c] is None:
steps += 1
new_state = list(state)
new_state[i] = var + steps
yield (tuple(new_state), (v.id, 'D', steps))
r_down += 1
def heuristic(self, state: Tuple[int, ...]) -> int:
"""Admissible heuristic: blockers in exit row + 1 if not solved.
Args:
state: Compressed state.
Returns:
Lower bound on remaining moves.
"""
red = self.vehicles[0]
red_col = state[0]
red_right = red_col + red.length - 1
if red_right == self.board_size - 1:
return 0
r = self.exit_row
occ = self.occupancy(state)
blockers: Set[int] = set()
for c in range(red_right + 1, self.board_size):
idx = occ[r][c]
if idx is not None:
blockers.add(idx)
return len(blockers) + 1
def a_star_solve(
puz: Puzzle, max_nodes: Optional[int] = None
) -> Tuple[Optional[List[Tuple[str, str, int]]], int, int]:
"""Solve the puzzle with A*.
Args:
puz: Puzzle instance.
max_nodes: Optional cap on node expansions before aborting.
Returns:
A tuple (moves, expansions, depth):
* moves: List of (vehicle_id, dir, steps) or None if unsolved/aborted.
* expansions: Number of expanded nodes.
* depth: Solution length in moves (or -1 if none).
"""
start = puz.start_state()
if puz.is_goal(start):
return [], 0, 0
g_score: Dict[Tuple[int, ...], int] = {start: 0}
parent: Dict[Tuple[int, ...], Tuple[Tuple[int, ...], Tuple[str, str, int]]] = {}
counter = 0
open_heap: List[Tuple[int, int, Tuple[int, ...]]] = []
h0 = puz.heuristic(start)
heapq.heappush(open_heap, (h0, counter, start))
counter += 1
in_open: Set[Tuple[int, ...]] = {start}
expansions = 0
while open_heap:
f, _, current = heapq.heappop(open_heap)
in_open.discard(current)
expansions += 1
if max_nodes is not None and expansions > max_nodes:
return None, expansions, -1
if puz.is_goal(current):
path: List[Tuple[str, str, int]] = []
s = current
while s in parent:
prev, mv = parent[s]
path.append(mv)
s = prev
path.reverse()
return path, expansions, len(path)
g = g_score[current]
for nxt, mv in puz.generate_moves(current):
tentative_g = g + 1
if tentative_g < g_score.get(nxt, 1_000_000_000):
g_score[nxt] = tentative_g
parent[nxt] = (current, mv)
if nxt not in in_open:
h = puz.heuristic(nxt)
heapq.heappush(open_heap, (tentative_g + h, counter, nxt))
counter += 1
in_open.add(nxt)
return None, expansions, -1
def parse_puzzle(obj: Dict) -> Puzzle:
"""Parse a puzzle from a dict (e.g., loaded from JSON).
Args:
obj: Dictionary with keys board_size, exit_row, vehicles.
Returns:
Parsed ``Puzzle`` instance.
"""
n = obj.get("board_size", 6)
exit_row = obj.get("exit_row", 2)
vs = []
for v in obj["vehicles"]:
vs.append(
Vehicle(
id=v["id"],
row=v["row"],
col=v["col"],
length=v["length"],
orientation=v["orientation"].upper(),
)
)
return Puzzle(board_size=n, exit_row=exit_row, vehicles=vs)
def pretty_board(puz: Puzzle, state: Tuple[int, ...]) -> str:
"""Render the board as ASCII for a given state.
Args:
puz: Puzzle instance.
state: Compressed state.
Returns:
A string representation of the board.
"""
n = puz.board_size
grid = [['.' for _ in range(n)] for _ in range(n)]
for i, v in enumerate(puz.vehicles):
var = state[i]
for r, c in v.cells(var):
grid[r][c] = v.id
grid[puz.exit_row][n - 1] = (
grid[puz.exit_row][n - 1].lower() if grid[puz.exit_row][n - 1] != '.' else '>'
)
lines = [' '.join(row) for row in grid]
return '\n'.join(lines)
EXAMPLE_PUZZLE = {
"board_size": 6,
"exit_row": 2,
"vehicles": [
{"id": "X", "row": 2, "col": 1, "length": 2, "orientation": "H"},
{"id": "A", "row": 0, "col": 0, "length": 2, "orientation": "H"},
{"id": "B", "row": 1, "col": 0, "length": 3, "orientation": "V"},
{"id": "C", "row": 4, "col": 0, "length": 2, "orientation": "V"},
{"id": "D", "row": 1, "col": 3, "length": 3, "orientation": "V"},
{"id": "E", "row": 5, "col": 2, "length": 3, "orientation": "H"},
{"id": "F", "row": 4, "col": 4, "length": 2, "orientation": "H"},
{"id": "G", "row": 0, "col": 5, "length": 3, "orientation": "V"},
],
}
def solve_and_print(puzzle_obj: Dict):
"""Solve a puzzle and print the move sequence and board states.
Args:
puzzle_obj: Dict describing the puzzle (JSON-compatible).
"""
puz = parse_puzzle(puzzle_obj)
path, expansions, depth = a_star_solve(puz)
print("Start state:")
print(pretty_board(puz, puz.start_state()))
print()
if path is None:
print("No solution found.")
return
print(f"Solved in {depth} moves, expanded states: {expansions}\n")
state = puz.start_state()
for i, mv in enumerate(path, 1):
vid, d, s = mv
print(f"Move {i:02d}: {vid}-{d}{s}")
idx = next(i for i, v in enumerate(puz.vehicles) if v.id == vid)
new_state = list(state)
if d == 'L':
new_state[idx] -= s
elif d == 'R':
new_state[idx] += s
elif d == 'U':
new_state[idx] -= s
elif d == 'D':
new_state[idx] += s
state = tuple(new_state)
print(pretty_board(puz, state))
print()
if __name__ == "__main__":
solve_and_print(EXAMPLE_PUZZLE)