Rush Hour - Solving the game
Rush Hour
if you're not familiar with it, the game consists of a collection of cars of varying sizes, set either horizontally or vertically, on a NxM grid that has a single exit.
Each car can move forward/backward in the directions it's set in, as long as another car is not blocking it. You can never change the direction of a car.
There is one special car, usually it's the red one. It's set in the same row that the exit is in, and the objective of the game is to find a series of moves (a move - moving a car N steps back or forward) that will allow the red car to drive out of the maze.
I've been trying to think how to solve this problem computationally, and I can really not think of any good solution.
I came up with a few:
- Backtracking. This is pretty simple - Recursion and some more recursion until you find the answer. However, each car can be moved a few different ways, and in each game state a few cars can be moved, and the resulting game tree will be HUGE.
- Some sort of constraint algorithm that will take into account what needs to be moved, and work recursively somehow. This is a very rough idea, but it is an idea.
- Graphs? Model the game states as a graph and apply some sort of variation on a coloring algorithm, to resolve dependencies? Again, this is a very rough idea.
- A friend suggested genetic algorithms. This is sort of possible but not easily. I can't think of a good way to make an evaluation function, and without that we've got nothing.
So the question is - How to create a program that takes a grid and the vehicle layout, and outputs a series of steps needed to get the red car out?
Sub-issues:
- Finding some solution.
- Finding an optimal solution (minimal number of moves)
- Evaluating how good a current state is
Example: How can you move the cars in this setting, so that the red car can "exit" the maze through the exit on the right?
(source: scienceblogs.com)
Answer
For classic Rush Hour, this problem is very tractable with a simple breadth first search. The claimed hardest known initial configuration requires 93 moves to solve, with a total of only 24132 reachable configurations. Even a naively implemented breadth-first search algorithm can explore the entire search space in under 1 second on even a modest machine.
References
- Wikipedia/Rush Hour (board game)
- Rush Hour Initial Configurations -- these are claimed to be the "hardest" problems
- Solver source at ideone.com - with output for the "hardest" input
The Java solver
Here's the complete source code of a breadth-first search exhaustive solver, written in C-style.
import java.util.*;
public class RushHour {
// classic Rush Hour parameters
static final int N = 6;
static final int M = 6;
static final int GOAL_R = 2;
static final int GOAL_C = 5;
// the transcription of the 93 moves, total 24132 configurations problem
// from http://cs.ulb.ac.be/~fservais/rushhour/index.php?window_size=20&offset=0
static final String INITIAL = "333BCC" +
"B22BCC" +
"B.XXCC" +
"22B..." +
".BB.22" +
".B2222";
static final String HORZS = "23X"; // horizontal-sliding cars
static final String VERTS = "BC"; // vertical-sliding cars
static final String LONGS = "3C"; // length 3 cars
static final String SHORTS = "2BX"; // length 2 cars
static final char GOAL_CAR = 'X';
static final char EMPTY = '.'; // empty space, movable into
static final char VOID = '@'; // represents everything out of bound
// breaks a string into lines of length N using regex
static String prettify(String state) {
String EVERY_NTH = "(?<=\\G.{N})".replace("N", String.valueOf(N));
return state.replaceAll(EVERY_NTH, "\n");
}
// conventional row major 2D-1D index transformation
static int rc2i(int r, int c) {
return r * N + c;
}
// checks if an entity is of a given type
static boolean isType(char entity, String type) {
return type.indexOf(entity) != -1;
}
// finds the length of a car
static int length(char car) {
return
isType(car, LONGS) ? 3 :
isType(car, SHORTS) ? 2 :
0/0; // a nasty shortcut for throwing IllegalArgumentException
}
// in given state, returns the entity at a given coordinate, possibly out of bound
static char at(String state, int r, int c) {
return (inBound(r, M) && inBound(c, N)) ? state.charAt(rc2i(r, c)) : VOID;
}
static boolean inBound(int v, int max) {
return (v >= 0) && (v < max);
}
// checks if a given state is a goal state
static boolean isGoal(String state) {
return at(state, GOAL_R, GOAL_C) == GOAL_CAR;
}
// in a given state, starting from given coordinate, toward the given direction,
// counts how many empty spaces there are (origin inclusive)
static int countSpaces(String state, int r, int c, int dr, int dc) {
int k = 0;
while (at(state, r + k * dr, c + k * dc) == EMPTY) {
k++;
}
return k;
}
// the predecessor map, maps currentState => previousState
static Map<String,String> pred = new HashMap<String,String>();
// the breadth first search queue
static Queue<String> queue = new LinkedList<String>();
// the breadth first search proposal method: if we haven't reached it yet,
// (i.e. it has no predecessor), we map the given state and add to queue
static void propose(String next, String prev) {
if (!pred.containsKey(next)) {
pred.put(next, prev);
queue.add(next);
}
}
// the predecessor tracing method, implemented using recursion for brevity;
// guaranteed no infinite recursion, but may throw StackOverflowError on
// really long shortest-path trace (which is infeasible in standard Rush Hour)
static int trace(String current) {
String prev = pred.get(current);
int step = (prev == null) ? 0 : trace(prev) + 1;
System.out.println(step);
System.out.println(prettify(current));
return step;
}
// in a given state, from a given origin coordinate, attempts to find a car of a given type
// at a given distance in a given direction; if found, slide it in the opposite direction
// one spot at a time, exactly n times, proposing those states to the breadth first search
//
// e.g.
// direction = -->
// __n__
// / \
// ..o....c
// \___/
// distance
//
static void slide(String current, int r, int c, String type, int distance, int dr, int dc, int n) {
r += distance * dr;
c += distance * dc;
char car = at(current, r, c);
if (!isType(car, type)) return;
final int L = length(car);
StringBuilder sb = new StringBuilder(current);
for (int i = 0; i < n; i++) {
r -= dr;
c -= dc;
sb.setCharAt(rc2i(r, c), car);
sb.setCharAt(rc2i(r + L * dr, c + L * dc), EMPTY);
propose(sb.toString(), current);
current = sb.toString(); // comment to combo as one step
}
}
// explores a given state; searches for next level states in the breadth first search
//
// Let (r,c) be the intersection point of this cross:
//
// @ nU = 3 '@' is not a car, 'B' and 'X' are of the wrong type;
// . nD = 1 only '2' can slide to the right up to 5 spaces
// 2.....B nL = 2
// X nR = 4
//
// The n? counts how many spaces are there in a given direction, origin inclusive.
// Cars matching the type will then slide on these "alleys".
//
static void explore(String current) {
for (int r = 0; r < M; r++) {
for (int c = 0; c < N; c++) {
if (at(current, r, c) != EMPTY) continue;
int nU = countSpaces(current, r, c, -1, 0);
int nD = countSpaces(current, r, c, +1, 0);
int nL = countSpaces(current, r, c, 0, -1);
int nR = countSpaces(current, r, c, 0, +1);
slide(current, r, c, VERTS, nU, -1, 0, nU + nD - 1);
slide(current, r, c, VERTS, nD, +1, 0, nU + nD - 1);
slide(current, r, c, HORZS, nL, 0, -1, nL + nR - 1);
slide(current, r, c, HORZS, nR, 0, +1, nL + nR - 1);
}
}
}
public static void main(String[] args) {
// typical queue-based breadth first search implementation
propose(INITIAL, null);
boolean solved = false;
while (!queue.isEmpty()) {
String current = queue.remove();
if (isGoal(current) && !solved) {
solved = true;
trace(current);
//break; // comment to continue exploring entire space
}
explore(current);
}
System.out.println(pred.size() + " explored");
}
}
There are two note-worthy lines in the source code:
- The
break;when a solution is found- This is now commented so that the breadth first search explores the entire search space, to confirm the numbers given in the linked website above
- The
current = sb.toString();inslide- Essentially this counts each movement of any car as one move. If a car is moved 3 spaces to the left, that's 3 moves. To combo this as one move (since it involves the same car moving in the same direction), simply comment this line. The linked website does not acknowledge combo, so this line is now uncommented to match the minimum number of moves given. With combo-counting, the 93-moves problem only requires 49 combo moves. That is, if there's a parking attendant in the lot that moves these cars around, he'd only only need to go in and out of a car 49 times.
Overview of the algorithm
The algorithm is essentially a breadth first search, implemented with a queue as is typical. A predecessor map is maintained so that any state can be traced back to the initial state. A key will never be remapped, and as entries are inserted in breadth-first search order, shortest path is guaranteed.
A state is represented as an NxM-length String. Each char represents an entity on the board, stored in row-major order.
Neighboring states are found by scanning all 4 directions from an empty space, looking for an appropriate car type, sliding it as room accommodates.
There is plenty of redundant work here (e.g. long "alleys" are scanned multiple times), but as mentioned before, although the generalized version is PSPACE-complete, the classic Rush Hour variant is very tractable by brute force.