Please take your time to try the game and come up with a answer for it. 1.The Ru
ID: 2246959 • Letter: P
Question
Please take your time to try the game and come up with a answer for it.
1.The Rush Hour puzzle (also sometimes called Traffic Jam http://www.thinkfun.com/play-online/rush-hour/) is inspired by gridlock on city streets. Vehicles can move only forward and backward---they can't turn---and the object is to get the car represented by the red rectangle out through the opening at the right edge of the puzzle. (There are many other implementations of this puzzle on the web. Search for "rush hour" and "puzzle" to find them.)
Follow the link for more details and many example puzzles. For the questions above, assume that the puzzle contains 1-by-2-unit "cars" (including the red car) and 1-by-3-unit "trucks."
a. Describe states that make up the puzzle's state space and give an upper bound for the number of distinct states. Note that this bound may depend on the size of a puzzle instance.
b. Suggest a computer representation --- that is, data structure(s)--- for a puzzle state. Be explicit enough that you can answer part c precisely.
c. Given the representation you have described, what operators are necessary for transforming one state into another; that is, for implementing moves in the puzzle. Describe one representative operator in detail.
d. Suggest a heuristic state evaluation function that can guide a search of the puzzle's state space toward a/the goal state. Explain briefly why your heuristic is better than a blind search?
Explanation / Answer
Assumption: We are working with 6*6 board.
Suppose the game involves n_cars cars and n_trucks trucks.
Each car has at-most 5 possible moves(forward or backward or rest).
Each truck has at-most 4 possible moves(forward or backward or rest).
Upperbound for number of distinct states is (n_cars^5)*(n_trucks^4)
Objective: Clear the path of the red car to the exit. So need to make sure that none of the other cars or trucks block the path of the red car to the exit.
Puzzle state{
int n_cars; //Number of cars
int n_trucks; // Number of trucks
int [n_cars][2] car_location; // Each car occupies 2 blocks
int [n_trucks][3] truck_locations; // Each truck occupies 3 blocks
boolean red_car_path_obstructed(true/false); // Is the exit path available for red car in this state?
}
Sample Operator: Car move
boolean car_move(int car_id,int num_steps,boolean direction){
//if direction is true , move is to right by num_steps
//else if direction is false move is to left by num_steps
if(direction){
car_location[car_id][0]=car_location[car_id][0] +num_steps;
car_location[car_id][1]=car_location[car_id][1] +num_steps;
}
else{
car_location[car_id][0]=car_location[car_id][0] -num_steps;
car_location[car_id][1]=car_location[car_id][1] -num_steps;
}
if( state is invalid) { // collision with another car or truck or end of board
undo move and restore previous state
return false;
}
else return true;
} // end of car_move operation
A similar operation will be defined for truck move
Heuristic function:-
1) Identify all the objects blocking path of red car to exit.
2) Try to remove obstacles to red car by moving the problematic object (car or truck) if possible. If not possible try to identify the object due to which the identified problematic object is unable to move. Try to move it first recursively. The objective is to free the path of red car.If it is not at all possible to move this object at all move the current object to pending list and focus on the next problematic object.
3) Once all the objects have been processed ,iterate through the pending list to see if the object can move now. If not add it to the end of the pending list.
4) Continue till the path of red car is free.
Since this approach is goal driven it is better suited to the problem than random state space search.