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?