Please answer these parts for the puzzle described below. pay attention to part
ID: 2247038 • Letter: P
Question
Please answer these parts for the puzzle described below. pay attention to part c especially.
For the puzzle 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. (important)
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?
2. This puzzle is called Sokoban. Link to it is right here.
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.
Explanation / Answer
a. In sokoban a state consist of the positions of the boxes and the position of the players.every other element of the board cannot change its position and therefore neednt to be stored per state. therefore a state can be stored by using the following :
one integer array for storing all box position.one integer for storing the player position for better memory alignment the player position and the box position can be stored in a one integer array together,the data structure usally consist of additional data fiels like for stroing information about the state likes pushes needed to reach it or which box has been pushed last .Example
public class State {
int [] boxPosition;
int PlayerPosition;
}
b) the computer representation of the data structure is as follows
"N" beginning of new row [at(box1,po(3,5)),at(warehousemanpos,pos(3,4))],
[at(box1,po(3,6)),at(warehousemanpos,pos(3,5))],
[at(box1,po(3,7)),at(warehousemanpos,pos(3,6))],
Calling the planner
Go to directory contating idaStar.pl execute SICStus Prolog LoadidaStar.pl enter solve (Domain,problem,heuristic,solution)
EG: solve(blocksWorld,prob01,manhattan,Solution)
C) move operator is very important to change the data from one position to another
for example in blockworld domain
op(mov,%% move B1 off of B2 and onto B3[B1,B2,B3])
D) your heuristic is in a file called heuristic.pl with pl extension and it must be in the heuristic directory it is written in prolog and must signature like
h(StateFluents. HeuristicValue)
Calculation body