Please answer these parts for the puzzle below. For the puzzles described below:
ID: 2246790 • Letter: P
Question
Please answer these parts for the puzzle below.
For the puzzles described below:
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
1.
a.
The puzzle’s state space is as follows:
· The rush hour is a kind of two-dimension puzzle.
· The square consists of m x m puzzle.
· The elements of the puzzle can be trucks or cars of different colors which occupy the puzzle blocks.
· The number of blocks occupied by the truck is about 1/3 and by car is about 1/2.
· The puzzle consists of only one leaving gate.
· The objective is to exit the red car from the gate.
· For the final state of the puzzle, there can be more than a single occurrence of the state.
· The location of car and trucks are also considered as the state of the puzzle.
· Therefore, the position of the objects is also considered as the state of the puzzle.
· The red car location is also considered to be a state of the puzzle.
· The elements of the puzzle are numbered and their various possible locations is a state space.
Upper bounds for the different states are as follows:
· Th objects can only move in the forward direction or in the backward direction.
· Therefore, the maximum number of movements taken by the truck would be (m-2) possible locations, and the car will move to only (m-1) possible locations.
· Any single set combination from the given set of combinations is the final location.
Example:
If the count of cars in the puzzle is “q”, and the count of truck is “p”, then the upper bound for the given puzzle is as follows:
p*(m-2)*q*(m-1)
Therefore, the upper bound of the puzzle depends upon the number of objects in the puzzle, and on the size of the puzzle.
b.
· The two-dimension array or the two-dimension vector can be used to represent the puzzle.
· Each element of the puzzle is numbered.
· Thus, their various locations are a state space.
Example:
If the object car is numbered as 1 and if it occupies the last two blocks of the puzzle, then the last two blocks are marked as 1.
c.
· The operations that can be used to move the objects is substitution operation.
· The ability to reach the location from one location to another is done by detecting the path between them, without violating the movement conditions (i.e the movement can only be a forward movement or be a backward movement).
· And the number of blocks between them must be null.
· The object from which the movement will start, substituted with 0.
d.
· The movement of other objects plays an important role to attain the goal.
· The “minimum-maximum” heuristic is much more effective than the blind search.
· Since, it considers all the possible paths to move to the final position, and choose the most optimal path by performing the iterations.
· It also, uses the mathematical calculations to determine the distance between the current object states and the goal states.