Please answer these parts for both parts. For each of the two puzzles described
ID: 2246582 • Letter: P
Question
Please answer these parts for both parts.
For each of the two puzzles described below:
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?
1.The Rush Hour puzzle (also sometimes called Traffic Jam http://cs.gmu.edu/~zduric/cs580/Railroad/) 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."
2. This puzzle is called Sokoban. Link to it is right here. https://webdocs.cs.ualberta.ca/~games/Sokoban/
The little figure can move vertically and horizontally, and the object is for the figure to push all the stones in the maze into specially-marked goal positions. Note that the figure can only push the stones; the puzzle cannot be solved from a configuration in which a stone is in a (non-goal) corner or only able to be pushed into such a corner, though such configurations are legal states of the puzzle.
For more details and many example puzzles, follow the link. For the questions above, assume that the maze has n spaces into which the figure and stones can move and that there are k stones.
Here's a link to an implementation of the puzzle that you can play. https://www.sokobanonline.com/
Explanation / Answer
a.
State of Sokobian:
The state of the Sokabian is a 2D-rectangular grid of squares to make the maze. The each square in the grid have the following states:
The Upper bound for the number of distinct states is shown below:
b.
Computer Representation of state:
The different types of the square represented by the computer have the following values for each state of the maze:
c.
Operators:
The different types of the operators for transforming one state into another are shown below:
This operator is used to move the state left side.
This operator is used to move the state right side.
This operator is used to move the state upwards
This operator is used to move the state downwards
d. Heuristic State Evaluation Function: