Rush Hour - Solving the game
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.
Wikipedia references
- Breadth-first search
- Row-major order
Here is my answer. Its solves the grand master puzzle in just under 6 seconds.
It use a breadth first search (BFS). The trick is to look for a board layout that you have see before in earlier searches and abort that sequence. Due to the BFS if you have seen that layout before you have already got there a shorter way so let that squence keep trying to solve it rather than this longer one.
#!perl
# Program by Rodos rodos at haywood dot org
use Storable qw(dclone);
use Data::Dumper;
print "Lets play Rush Hour! \n";
# Lets define our current game state as a grid where each car is a different letter.
# Our special car is a marked with the specific letter T
# The boarder is a * and the gloal point on the edge is an @.
# The grid must be the same witdh and height
# You can use a . to mark an empty space
# Grand Master
@startingGrid = (
['*','*','*','*','*','*','*','*'],
['*','.','.','A','O','O','O','*'],
['*','.','.','A','.','B','.','*'],
['*','.','T','T','C','B','.','@'],
['*','D','D','E','C','.','P','*'],
['*','.','F','E','G','G','P','*'],
['*','.','F','Q','Q','Q','P','*'],
['*','*','*','*','*','*','*','*']
);
# Now lets print out our grid board so we can see what it looks like.
# We will go through each row and then each column.
# As we do this we will record the list of cars (letters) we see into a hash
print "Here is your board.\n";
&printGrid(\@startingGrid);
# Lets find the cars on the board and the direction they are sitting
for $row (0 .. $#startingGrid) {
for $col (0 .. $#{$startingGrid[$row]} ) {
# Make spot the value of the bit on the grid we are looking at
$spot = $startingGrid[$row][$col];
# Lets record any cars we see into a "hash" of valid cars.
# If the splot is a non-character we will ignore it cars are only characters
unless ($spot =~ /\W/) {
# We will record the direction of the car as the value of the hash key.
# If the location above or below our spot is the same then the car must be vertical.
# If its not vertical we mark as it as horizonal as it can't be anything else!
if ($startingGrid[$row-1][$col] eq $spot || $startingGrid[$row+1] eq $spot) {
$cars{$spot} = '|';
} else {
$cars{$spot} = '-';
}
}
}
}
# Okay we should have printed our grid and worked out the unique cars
# Lets print out our list of cars in order
print "\nI have determined that you have used the following cars on your grid board.\n";
foreach $car (sort keys %cars) {
print " $car$cars{$car}";
}
print "\n\n";
end;
&tryMoves();
end;
# Here are our subroutines for things that we want to do over and over again or things we might do once but for
# clatiry we want to keep the main line of logic clear
sub tryMoves {
# Okay, this is the hard work. Take the grid we have been given. For each car see what moves are possible
# and try each in turn on a new grid. We will do a shallow breadth first search (BFS) rather than depth first.
# The BFS is achieved by throwing new sequences onto the end of a stack. You then keep pulling sequnces
# from the front of the stack. Each time you get a new item of the stack you have to rebuild the grid to what
# it looks like at that point based on the previous moves, this takes more CPU but does not consume as much
# memory as saving all of the grid representations.
my (@moveQueue);
my (@thisMove);
push @moveQueue, \@thisMove;
# Whlst there are moves on the queue process them
while ($sequence = shift @moveQueue) {
# We have to make a current view of the grid based on the moves that got us here
$currentGrid = dclone(\@startingGrid);
foreach $step (@{ $sequence }) {
$step =~ /(\w)-(\w)(\d)/;
$car = $1; $dir = $2; $repeat = $3;
foreach (1 .. $repeat) {
&moveCarRight($car, $currentGrid) if $dir eq 'R';
&moveCarLeft($car, $currentGrid) if $dir eq 'L';
&moveCarUp($car, $currentGrid) if $dir eq 'U';
&moveCarDown($car, $currentGrid) if $dir eq 'D';
}
}
# Lets see what are the moves that we can do from here.
my (@moves);
foreach $car (sort keys %cars) {
if ($cars{$car} eq "-") {
$l = &canGoLeft($car,$currentGrid);
push @moves, "$car-L$l" if ($l);
$l = &canGoRight($car,$currentGrid);
push @moves, "$car-R$l" if ($l);
} else {
$l = &canGoUp($car,$currentGrid);
push @moves, "$car-U$l" if ($l);
$l = &canGoDown($car,$currentGrid);
push @moves, "$car-D$l" if ($l);
}
}
# Try each of the moves, if it solves the puzzle we are done. Otherwise take the new
# list of moves and throw it on the stack
foreach $step (@moves) {
$step =~ /(\w)-(\w)(\d)/;
$car = $1; $dir = $2; $repeat = $3;
my $newGrid = dclone($currentGrid);
foreach (1 .. $repeat) {
&moveCarRight($car, $newGrid) if $dir eq 'R';
&moveCarLeft($car, $newGrid) if $dir eq 'L';
&moveCarUp($car, $newGrid) if $dir eq 'U';
&moveCarDown($car, $newGrid) if $dir eq 'D';
}
if (&isItSolved($newGrid)) {
print sprintf("Solution in %d moves :\n", (scalar @{ $sequence }) + 1);
print join ",", @{ $sequence };
print ",$car-$dir$repeat\n";
return;
} else {
# That did not create a solution, before we push this for further sequencing we want to see if this
# pattern has been encountered before. If it has there is no point trying more variations as we already
# have a sequence that gets here and it might have been shorter, thanks to our BFS
if (!&seen($newGrid)) {
# Um, looks like it was not solved, lets throw this grid on the queue for another attempt
my (@thisSteps) = @{ $sequence };
push @thisSteps, "$car-$dir$repeat";
push @moveQueue, \@thisSteps;
}
}
}
}
}
sub isItSolved {
my ($grid) = shift;
my ($row, $col);
my $stringVersion;
foreach $row (@$grid) {
$stringVersion .= join "",@$row;
}
# We know we have solve the grid lock when the T is next to the @, because that means the taxi is at the door
if ($stringVersion =~ /\T\@/) {
return 1;
}
return 0;
}
sub seen {
my ($grid) = shift;
my ($row, $col);
my $stringVersion;
foreach $row (@$grid) {
$stringVersion .= join "",@$row;
}
# Have we seen this before?
if ($seen{$stringVersion}) {
return 1;
}
$seen{$stringVersion} = 1;
return 0;
}
sub canGoDown {
my ($car) = shift;
return 0 if $cars{$car} eq "-";
my ($grid) = shift;
my ($row, $col);
for ($row = $#{$grid}; $row >= 0; --$row) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
# See how many we can move
$l = 0;
while ($grid->[++$row][$col] eq ".") {
++$l;
}
return $l;
}
}
}
return 0;
}
sub canGoUp {
my ($car) = shift;
return 0 if $cars{$car} eq "-";
my ($grid) = shift;
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
# See how many we can move
$l = 0;
while ($grid->[--$row][$col] eq ".") {
++$l;
}
return $l;
}
}
}
return 0;
}
sub canGoRight {
my ($car) = shift;
return 0 if $cars{$car} eq "|";
my ($grid) = shift;
my ($row, $col);
for $row (0 .. $#{$grid}) {
for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
if ($grid->[$row][$col] eq $car) {
# See how many we can move
$l = 0;
while ($grid->[$row][++$col] eq ".") {
++$l;
}
return $l;
}
}
}
return 0;
}
sub canGoLeft {
my ($car) = shift;
return 0 if $cars{$car} eq "|";
my ($grid) = shift;
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
# See how many we can move
$l = 0;
while ($grid->[$row][--$col] eq ".") {
++$l;
}
return $l;
}
}
}
return 0;
}
sub moveCarLeft {
# Move the named car to the left of the passed grid. Care must be taken with the algoritm
# to not move part of the car and then come across it again on the same pass and move it again
# so moving left requires sweeping left to right.
# We need to know which car you want to move and the reference to the grid you want to move it on
my ($car) = shift;
my ($grid) = shift;
# Only horizontal cards can move left
die "Opps, tried to move a vertical car $car left" if $cars{$car} eq "|";
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
die "Tried to move car $car left into an occupied spot\n" if $grid->[$row][$col-1] ne ".";
$grid->[$row][$col-1] = $car;
$grid->[$row][$col] = ".";
}
}
}
}
sub moveCarRight {
# Move the named car to the right of the passed grid. Care must be taken with the algoritm
# to not move part of the car and then come across it again on the same pass and move it again
# so moving right requires sweeping right to left (backwards).
# We need to know which car you want to move and the reference to the grid you want to move it on
my ($car) = shift;
my ($grid) = shift;
# Only horizontal cards can move right
die "Opps, tried to move a vertical car $car right" if $cars{$car} eq "|";
my ($row, $col);
for $row (0 .. $#{$grid}) {
for ($col = $#{$grid->[$row]}; $col >= 0; --$col ) {
if ($grid->[$row][$col] eq $car) {
die "Tried to move car $car right into an occupied spot\n" if $grid->[$row][$col+1] ne ".";
$grid->[$row][$col+1] = $car;
$grid->[$row][$col] = ".";
}
}
}
}
sub moveCarUp {
# Move the named car up in the passed grid. Care must be taken with the algoritm
# to not move part of the car and then come across it again on the same pass and move it again
# so moving right requires sweeping top down.
# We need to know which car you want to move and the reference to the grid you want to move it on
my ($car) = shift;
my ($grid) = shift;
# Only vertical cards can move up
die "Opps, tried to move a horizontal car $car up" if $cars{$car} eq "-";
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
die "Tried to move car $car up into an occupied spot\n" if $grid->[$row-1][$col] ne ".";
$grid->[$row-1][$col] = $car;
$grid->[$row][$col] = ".";
}
}
}
}
sub moveCarDown {
# Move the named car down in the passed grid. Care must be taken with the algoritm
# to not move part of the car and then come across it again on the same pass and move it again
# so moving right requires sweeping upwards from the bottom.
# We need to know which car you want to move and the reference to the grid you want to move it on
my ($car) = shift;
my ($grid) = shift;
# Only vertical cards can move up
die "Opps, tried to move a horizontal car $car down" if $cars{$car} eq "-";
my ($row, $col);
for ($row = $#{$grid}; $row >=0; --$row) {
for $col (0 .. $#{$grid->[$row]} ) {
if ($grid->[$row][$col] eq $car) {
die "Tried to move car $car down into an occupied spot\n" if $grid->[$row+1][$col] ne ".";
$grid->[$row+1][$col] = $car;
$grid->[$row][$col] = ".";
}
}
}
}
sub printGrid {
# Print out a representation of a grid
my ($grid) = shift; # This is a reference to an array of arrays whch is passed as the argument
my ($row, $col);
for $row (0 .. $#{$grid}) {
for $col (0 .. $#{$grid->[$row]} ) {
print $grid->[$row][$col], " ";
}
print "\n";
}
}
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.
There's actually a paper out of MIT which specifically references Rush Hour (I used the search term "sliding block puzzles")