TPS 1

On a piece of paper, write your answer to the following question.

In the 8-tile game, 8 tiles numbered 1–8 are arranged in a 3x3 grid in some arbitrary order. There is one open space. The agent's goal is to rearrange the tiles so that they the are in order, with tiles 1, 2, and 3 in the first row, followed by tiles 4, 5, and 6 in the next, and 7 and 8 in the next row. The empty space should be in the bottom right corner of the grid. Tiles may be moved left, right, up, or down into the empty space.

1. What information would a solution to this problem entail? That is, what is the form of actions that the agent may perform to transition between states and eventually arrive at a goal state? (Recall that in "eat all the dots", actions are directions the agent can move in the grid world).

2. What is the size of the state space for this problem?