Problem 6: Rush Hour

Loyola College > Department of Computer Science > Dr. James Glenn > HS Programming Contest > Problems > Problem 6: Rush Hour

Introduction

Rush Hour is a puzzle game played on a rectangular grid. The grid contains vehicles placed on the grid horizontally or vertically. Vehicles are 1 square wide and are 2 or more squares long. The object of the game is to slide one distinguished vehicle off the board through an opening in one side. Vehicles can only move backwards and forward accoring to their orientation. Vehicles can not move through other vehicles.

A Rush Hour configuration with 5 vehicles
The goal is to slide the purple vehicle through the hole in the right edge.
The result of sliding the red vehicle three spaces to the right

Problem

Complete the RushHourMove class by writing the method isLegal. An instance of RushHourMove contains two configurations called initialBoard and finalBoard. The isLegal method must determine if it is possible to get from the initial configuration to the final configuration by moving at most one vehicle (so a move is considered legal even if nothing moves).

The configurations are modelled by RushHourBoard objects. Vehicles on the board are represented by unique character codes. For example, if there are 3 vehicles on a board, they may be represented by the characters 'A', 'B', and 'C'. RushHourBoard provides methods by which you can determine what vehicle, if any, is at a given position:

char getVehicleAt(int r, int c) returns the code for the vehicle that occupies row r, column c on the board, or RushHourBoard.EMPTY if that position is empty;
char[][] getBoard() returns an array set up with the same dimensions as the board and such that getBoard()[r][c] will be the same as getVehicleAt(r, c);
int getWidth() returns the number of columns on the board; and
int getHeight() returns the number of rows on the board.

Assumptions

You may assume that the initial and final boards are the same size.
You may assume that both boards are legal (for example, you won't find the same character in opposite corners of the board).
You may assume that both boards have the same number of vehicles and that the same character code is used for a particular vehicle on both boards (so if there is an 'A' somewhere on one board, there will be an 'A' on the other board as well, and both 'A's represent the same vehicle).
You may assume that the vehicles don't change size between the two boards (so if there are two 'A's on one board, there will be two 'A's on the second board).