The following is an excerpt from the famous short story “The Lady or the Tiger” based on the story of a barbaric king in medieval times. The king builta 21- room house “House of Trials” with the lowest level as an arena. The roof of the house is built using a one- way mirror that allows spectators to see into the house. Belowis a blueprint of the king’s “House of Trials.” (The one way mirror is a modern addition)
The small rectangles between rooms designate doors.
Each numbered circle (vertex) represents a room and each line (edge) that joins two vertices is a door between rooms.
Problems:
- A blindfolded prisoner is led into the house and abandoned in one of the rooms, where his blindfold is removed.
- In another room a lady waits, and in a third room a tiger snarls.
- Unable to hear the cheers and jeers of curious spectators, the prisoner wanders through the house, from room to room to room, until he finds either the lady who leads him to marital bliss or the tiger that . . . .
If you examine the network in Figure 1, you will see that every room is accessible from every other room. So if the prisoner systematically moves through the house, he will eventually come upon either the lady or the tiger.
Each numbered circle (vertex) represents a room and each line (edge) that joins two vertices is a door between rooms.
Problem Statement
Write an application that simulates the movements of the prisoner through the rooms of the house. The application should:
- report the rooms that the prisoner visits, in the order that he visits them,
- as well as the final outcome— the lady or the tiger.
Java Solution
Before we can implement an algorithm that moves the prisoner through the house, we must decide on an internal representation of the house.
- We choose to represent Figures 1 and 2 as a two- dimensional array of rooms.
The rows and columns of rooms are indexed by the room numbers.If i and j are two room numbers, then
- if there is a door between room i and room j -- rooms( i, j) =1
- if there is no door between room i and room j -- rooms( i, j) =0
The prisoner “visits” rooms until he discovers the lady or the tiger.
To ensure that the program eventually terminates, the prisoner never revisits the same room.
Below is an algorithm (method) that systematically moves the prisoner through the house until the lady or the tiger is discovered.
(Notice that he never “visits” a room twice, although he may backtrack through a previously visited room.)
Algorithm for Search Method
Mark the initial room as visited.
Push the initial room onto a stack of room numbers.
// the room at the top of the stack is the room currently occupied by the prisoner
// the stack “remembers” previously visited rooms
while both the lady and the tiger are undiscovered
{
if there is an unvisited room r adjacent to the room on top of the stack (the current room)
Visit r;
mark r as visited.
if the lady or tiger is in r, the search is over
otherwise push r onto the stack, that is,
move the prisoner to room r.
else if there is no unvisited room adjacent to the room on top of the stack
backtrack to the previous room, that is,
pop the stack
// the most recently visited room is now on top of the stack
}
report the results
For example, using Figure 1 as a map, assume that the entry room is room 0; the tiger is in 4; and the lady in 14.
From room 0, the prisoner might move to room 1, then from 1 to 2.
Room 2 is a dead end; he can move to no unvisited rooms from 2 because he has already visited 0 and 1. So, he backtracks to room 1.
And, from 1 he can move to 3, then to 5, then to 6.
Room 6 is a dead end, so he backtracks to 5.
From 5, he can go to 7, and to 4, where he meets an unfortunate fate.
We use a stack to implement backtracking.
Each time the prisoner enters a room, push the room onto the stack.
If the prisoner is ever in a room that is a dead end, then pop the stack
backtrack, and continue from there.
The stack keeps track of previous rooms so the prisoner can easily backtrack.
Ouput results to a file and to the JTextArea
Output
Running the simulation twice with the same input data produces the following different results. Because the “ next room” is selected randomly , the outcomes differ.
Output 1
The starting room?: 0
The tiger is in 19
The lady is in 21
Starting in room 0 the prisoner visits rooms:
1 3 5 6 14 18 19
He found the tiger in room 19
Here is the trace
0 ->1-> 3-> 5-> 6.( backtrack to 5).->14.->18-> 19
The nextRoom method ( int room) accepts a room number and returns the number of an unvisited adjacent room, . The room need not be chosen randomly. For example, the room can be chosen as the first adjacent room that has a door and was not already visited. Or choose a random room number to add some non- determinism to the problem.
In the grid, rooms with doors are marked with a “1”. Also in the TWO D array of integers.
You should output the stack to the JTextArea after each traversal.
Classes Needed:
Class Room ( representing a square on the grid of rooms) – similar to checkers square class
Class TigerOrLadyGUI - sets up the components - a panel of buttons, outputarea etc. Runs the simulation from the actionlistener class.
Class DrawRooms - draws the grid of rooms and places the images for the lady , tiger etc.
Class TigerLilyMain - runs the applicaton
The GUI - as pictured or as you wish to arrange it.
1