A sliding-tile puzzle is a rectangular grid of tile with one empty space. You can slide a tile into an adjacent empty space. The object of the puzzle is to rearrange the tiles into a given goal state. Figure shows a typical instance of the 8-puzzle, which uses a 3 x 3 grid.

Typical instance of the 8-puzzle.

For this assignment, we will limit ourselves to n x n sliding-tile puzzles, where n > 1. Such a puzzle has tiles numbered 1 to n2-1plus the empty tile. For specific values of n, such puzzles are known as -puzzles. The most common are8-puzzles and 15-puzzles.

Given a sliding-tile puzzle state, you must be able to determinethe rules that are applicable to that state that can be used togenerate its successor states.

A rule has three parts:

?name ?a simple name for the rule (e.g., up, left, down,right)

?precondition function ?a Boolean function that accepts a stateand returns true if the rule is applicable to state

?action function ?a function that accepts a state and returnsthe successor state obtained by applying the rule.

You can use these rules to implement functions such asapplicable-rule, which returns a list of the rules applicable to agiven state, and successor-state, which returns the successor statefor a given state and rule.

To do: Encode the rules for the sliding-tilepuzzle. Remember that it is easiest to consider moving the emptyspace up, left, down, or right. Using these rules, write routinesto determine the rules applicable to a state and the successorstate given a state and rule to apply. Note that you couldimplement these as iterators or have them return lists (or vectors)or rules and states.

7 5 8 2 3 Start State 4 6 1 3 6 1 4 7 Goal State 2 5 8