Rush Hour - Solving the game

Question

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:

1. 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.
2. 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.
3. 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.
4. 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:

1. Finding some solution.
2. Finding an optimal solution (minimal number of moves)
3. 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?

Answer 1

There's actually a paper out of MIT which specifically references Rush Hour (I used the search term "sliding block puzzles")

Answer 2

I think recursion is a bad idea, unless you keep track of what you've already visited; you could end up recursing infinitely by moving a car back and forth.

Maybe this is a good start: Represent and store each board state as an undirected graph. Then for each possible move, check against past states to make sure you're not just hitting the same state again.

Now make another undirected graph where nodes represent states and edges represent the ability to get from one state to another via moving a car. Explore states until one of them is a solution. Then follow the edges back to the beginning to find out a move path.

Answer 3

You should recurse (your "backtracking" solution). This is probably the only way to solve puzzles like this; the question is how to do it fast.

As you noted, the search space will be large - but not too large, if you have a reasonable sized board. For example, you've drawn a 6x6 grid with 12 cars on it. Assuming each is a size-2 car, that gives 5 spaces/per, so at most 5^12 = 244,140,625 potential positions. This even fits in a 32-bit integer. So one possibility is to allocate a huge array, one slot per potential position, and use memoization to make sure that you don't repeat a position.

The next thing to note is that most of those "potential" positions aren't, in fact, possible (they'd involve cars overlapping). So instead, use a hash table to keep track of each position you've visited. This will have a small memory overhead per entry, but it'll probably be more space-efficient than the "huge array" solution. It will, however, take a bit longer for each entry access.

As the MIT paper in @Daniel's answer says, the problem is PSPACE-complete, meaning many of the tricks used to reduce the complexity of NP problems probably can't be used.

That said, either of the two above solutions to the repeated-position problem should work for smallish grids. It'll all be determined by how big the problem is, and how much memory your computer has; but the example you displayed should be no trouble at all, even for a ordinary desktop computer.

Answer 4

I wrote a sudoku solver. While the details are completely different, I think the overall problem is similar. For one thing, trying to do smart heuristics in a sudoku solver is much slower than a brute force solution. Trying every move, with a few simple heuristics and no duplicates is the way to go. It is slightly more difficult to check for duplicate board states in rush hour, but not much.

If you look at the board in you sample, there are only 4 valid moves. At any given time, there will only be a few valid moves.

At each level of recursion, copy the board state and try every valid move on the board. For each empty square, move every car that can onto that square. If the new board state is not in the history list, then recurse another level. By history list, I mean give each level of recursion access to each board that led to that state, probably in a linked list. Use hashes to quickly discard unequal states.

The key to this is having a simple board state that can be easily copied and modified. Probably an array with one int per square saying what car covers that square, if any. Then you just need to iterate through the squares and figure out legal moves. A legal move means empty squares between the test square and a car oriented towards it.

As with sudoku, the worst possible option would be a genetic algorithm.

Answer 5

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(); in slide
  • 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.

Wikipedia references

• Breadth-first search
• Row-major order

Answer 6

Just finished writing my implementation and experimenting with it. I agree with polygenelubricants that the state space is really small for the classic game (6x6 board). However, I tried a clever search implementation (A* search). I was curious regarding the reduction of explored state space in comparison to a simple BFS.

A* algorithm can be viewed as a generalization of BFS search. The decision of which path to explore next is determined by a score that combines both the path length (i.e. number of moves) and a lower bound on the remaining moves count. The way I chose to compute the latter, is to get the distance of the red car from the exit, and then add 1 for every vehicle in the way, since it has to be moved at least once in order to clear the way. When I replace the lower bound calculation with a constant 0, I get a regular BFS behavior.

After inspecting four puzzles from this list, I found that A* search explores in average 16% less states than a regular BFS.