CS 2360
Summer 1998
Homework Assignment 5
Due no later than 8:00am, Tuesday, August 4, 1998
Look here for other notes on the assignment
Caution: Must read through once fully before stopping to think.
The puzzle called "RushHour" (c. 1996, Binary Arts Corp.) begins with a
six-by-six grid of squares. Little plastic cars and trucks are distributed
across the grid in such a way as to prevent one special car from moving off
the grid, thereby escaping the traffic jam. The initial configuration of
cars and trucks is preordained by a set of cards, each containing a
different starting pattern. A player draws a card, sets up the cars and
trucks according to the pattern, and then tries to move the special car off
the grid by sliding the cars and trucks up and down or left and right,
depending on the starting orientation of the cars and trucks.
The grid looks something like this:
---------------------------
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | <-- this is the only escape from the grid
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
---------------------------
Cars occupy two contiguous squares, while trucks occupy three contiguous
squares. All vehicles are oriented horizontally or vertically, never on the
diagonal. Vehichles which are oriented horizontally may only move
horizontally; vehicles which are oriented vertically may only move
vertically. Vehicles may not be lifted from the grid, and there is never
any diagonal movement. Vehicles may not be partially on the grid and
partially off the grid.
The special car is called the X car. We'll represent it on the grid as two
contiguous squares with the letter X in them. (We'll represent all other
cars and trucks with different letters of the alphabet, but the special car
will always be labelled with the letter X.) The X car is always oriented
horizontally on the third row from the top; otherwise, the X car could
never escape. If it were the only car on the grid, it might look like this
(although it could start anywhere on that third row):
---------------------------
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | X | X | | | | | <-- the X car will always start on this row
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
---------------------------
Let's put a blocking car and a blocking truck on the grid now too. We'll
label the car as A and the truck as B:
---------------------------
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
| | X | X | B | | | |
| --- --- --- --- --- --- |
| | | | A | A | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
---------------------------
Car A is oriented horizontally on the fourth row, and it can slide only
left or right. Truck B is oriented vertically in the third column from the
left, and it can slide only up or down. If this configuration were the
starting state for a puzzle, it would be pretty simple for us to solve
it. To slide the X car all the way to the right and off the grid, we'd have
to move the B truck out of the way. But to move the B truck, we'll first
have to move the A car out of the B truck's path. So the first solution
step might be to move the A car to the right by one square:
---------------------------
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
| | X | X | B | | | |
| --- --- --- --- --- --- |
| | | | | A | A | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
---------------------------
(Note that moving the A car further to the right works, as does moving it
two squares to the left.) The next step would be to slide the B truck down
three squares:
---------------------------
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | X | X | | | | |
| --- --- --- --- --- --- |
| | | | B | A | A | | |
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
---------------------------
Now it's possible to move the X car all the way to the right and off the
grid. It's not necessary to move it off the grid though; it's sufficient to
move the X car to cover the rightmost two squares of the third row from the
top:
---------------------------
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | X | X |
| --- --- --- --- --- --- |
| | | | B | A | A | | |
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
---------------------------
Now we've solved the puzzle. Let's see Deep Blue do that! Uh huh, sure.
Anyway, let's take another look at solving this "RushHour" puzzle, but this
time from the perspective of a state-space search. The initial state in the
state space is any configuration of cars and trucks such that the X car is
always oriented horizontally on the third row from the top. The goal state
is any configuration of cars and trucks which can be obtained through
correct application of the operators, such that the X car covers the
rightmost two squares of the third row from the top. The operators are
simply these: move a horizontally-oriented vehicle to the left, move a
horizontally-oriented vehicle to the right, move a vertically-oriented
vehicle up, and move a vertically-oriented vehicle down.
Your assignment is to write a program called RUSH-HOUR which employs a
depth first state space search to solve a "RushHour" puzzle with any legal
initial state. RUSH-HOUR takes two arguments. The first is a description of
the initial-state as a list containing the board description and car
locations. For this initial configuration:
---------------------------
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
| | | | B | | | | |
| --- --- --- --- --- --- |
| | X | X | B | | | |
| --- --- --- --- --- --- |
| | | | A | A | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
| | | | | | | | |
| --- --- --- --- --- --- |
---------------------------
the list of lists passed to RUSH-HOUR would look like this:
'((6 6 6 2)
(b 2 0 3 v)
(a 2 3 2 h)
(x 0 2 2 h))
The first sub-list represents the board configuration, and the remaining
sub-lists represent the vehicles. The board configuration is in the
following format:
(x-size y-size exit-x-coordinate exit-y-coordinate)
The cars are represented as follows:
(car-name car-smallest-x-coordinate car-smallest-y-coordinate size
orientation)
Note that the indexes are zero-based. Also note that the exit is marked
with a coordinate that exceeds the maximum x-index. This indicates the
location of the exit is on the right edge of the board, on the row with
index 2 (which is the third row). The orientation can have one of two
values: h (horizontal) and v (vertical).
The above representation contains more information than it needs to. The
start positon of the car x, and the location of the exit, is fixed. It has
been included simply for completeness (and for any of you dying for a
chance to do more lisp hacking).
Pretty printed, the above representation is as follows:
- - b - - -
- - b - - -
x x b - - -
- - a a - -
- - - - - -
- - - - - -
We don't need to pass the goal state, as it will always be the same
regardless of the initial state. The goal state will always be a legally
obtained configuration of cars and trucks with the X car on the rightmost
two squares of the third row. (In the general case this will be more
complicated. The goal state would have the car perpendicular to the side
the goal is on, occupying the two closest spaces near the goal. You don't
need to do this, though, since the exit is fixed.)
The second argument is either nil or non-nil. If the value is non-nil, your
program should print to the terminal a trace of the sequence of states or
moves being tried as the search progresses. The trace should also point out
where the program runs into a dead end and has to backtrack, as well as
pointing out when the goal has been reached. If the second argument is nil,
no trace should be printed. (You'll want to look up some of the print I/O
stuff to make this pretty.)
To recap, the function definition should be of the form:
(defun rush-hour (initial-configuration trace-p)
...)
When (if?) the goal has been reached, RUSH-HOUR should terminate and return
a list of successive states that constitutes the path from the initial
state to the goal state. So, if Sunil invokes RUSH-HOUR in this way:
? (rush-hour
'((6 6 6 2)
(b 2 0 3 v)
(a 2 3 2 h)
(x 0 2 2 h))
nil)
your program should return something like this (although not necessarily
exactly this):
(((6 6 6 2)
(b 2 0 3 v)
(a 2 3 2 h)
(x 0 2 2 h))
((6 6 6 2)
(b 2 0 3 v)
(a 3 3 2 h)
(x 0 2 2 h))
((6 6 6 2)
(b 2 1 3 v)
(a 3 3 2 h)
(x 0 2 2 h))
((6 6 6 2)
(b 2 2 3 v)
(a 3 3 2 h)
(x 0 2 2 h))
((6 6 3 2)
(b 2 3 3 v)
(a 3 3 2 h)
(x 1 2 2 h))
((6 6 6 2)
(b 2 3 3 v)
(a 3 3 2 h)
(x 2 2 2 h))
((6 6 6 2)
(b 2 3 3 v)
(a 3 3 2 h)
(x 3 2 2 h))
((6 6 6 2)
(b 2 3 3 v)
(a 3 3 2 h)
(x 4 2 2 h)))
The above result is of course impossible to read, so it would be hard for
you to debug your program and see it in action when you ran it. Therefore,
if the program is invoked as follows:
? (rush-hour
'((6 6 6 2)
(b 2 0 3 v)
(a 2 3 2 h)
(x 0 2 2 h))
t)
we would expect to see a pretty printed trace of your program in action.
This would look something like the following:
Start state
- - b - - -
- - b - - -
x x b - - -
- - a a - -
- - - - - -
- - - - - -
a right
- - b - - -
- - b - - -
x x b - - -
- - - a a -
- - - - - -
- - - - - -
b down
- - - - - -
- - b - - -
x x b - - -
- - b a a -
- - - - - -
- - - - - -
b down
- - - - - -
- - - - - -
x x b - - -
- - b a a -
- - b - - -
- - - - - -
b down
- - - - - -
- - - - - -
x x - - - -
- - b a a -
- - b - - -
- - b - - -
x right
- - - - - -
- - - - - -
- x x - - -
- - b a a -
- - b - - -
- - b - - -
x right
- - - - - -
- - - - - -
- - x x - -
- - b a a -
- - b - - -
- - b - - -
x right
- - - - - -
- - - - - -
- - - x x -
- - b a a -
- - b - - -
- - b - - -
x right
- - - - - -
- - - - - -
- - - - x x
- - b a a -
- - b - - -
- - b - - -
Goal reached!
HINT: Figure out how to pretty-print the board first, since this can be
safely dissociated from the rest of the program. It will also give some
ideas on how you ought to be approaching your operators. The pretty
printout does not need to look *exactly* like the above. But it must
include at least the operator and a graphical representation of the board.
Your program may find a different path because your program may apply its
operators in a different order than the hypothetical program above does.
That's ok with us. The astute reader would have noted that in the trace
above we have assumed that the program picks the exact set of operations
that would take it to the goal state. You will be using depth first search,
which as we all know, leisurely winds its way through the search
space. Expect to see many, many more states in a real trace.
If the goal state can't be reached from the initial state, RUSH-HOUR should
just return nil.
If you wish, you can convert my representation for the "RushHour" puzzle
into any other representation of your choice if you think that would make
your life easier. I make no claim that the representation I'm using above
for passing the start state to your program is necessarily a great
representation to use in solving the problem. It just happens to be
convenient for representing the start state. So like I said, if you think
things might go easier for you if you use a different representation,
please feel free to do so. However, you still have to deal with my
representation as input to your function as specified above. Furthermore,
you'll need to convert your representation to my representation in order to
return the path from the initial state to the goal state in the correct
(i.e., my) format.
Same guidelines as in the past: lots of well-abstracted, well-named,
cohesive, and readable functions, but no global variables, no assignment,
and no iteration. You can use anything that doesn't have side effects
(except in printing your trace...printing is a side effect).
Oh, you can find out more about Binary Arts at www.puzzles.com. Have fun!