Introduction to Logic

 Problem 5.3 - Sequential Plans

Consider the 8-puzzle introduced in the notes. The initial state of the game is shown below on the left, and the ideal arrangement is shown on the right.

 1
 3
 4
 2
 5
 7
 8
 6
 1
 2
 3
 4
 5
 6
 7
 8

Recall that there are 4 feasible actions - up, down, left, right - and any of these actions is legal so long as the empty tile remains within the 3x3 grid. The reward for a state is the sum of rewards for each tile, with 10 points being awarded for each numbers tile in its ideal position and 20 points being awarded if the empty cell is in its proper position.

 1. Which of the following sequential plans is legal? a. [right,right,down,down] Legal Not Legal b. [right,right,right,down] Legal Not Legal c. [right,down,right,down] Legal Not Legal
 2. Which of the following sequential plans is terminal? a. [right,down,up,left] Terminal Not Terminal b. [right,down,right,down] Terminal Not Terminal c. [right,down,right,down] Terminal Not Terminal d. [right,down,right,down] Terminal Not Terminal
 3. Which of the following sequential plans is minimal? a. [right,down,up,left] Legal Not Legal b. [right,down,right,down] Legal Not Legal c. [right,down,right,down] Legal Not Legal d. [right,down,right,down] Legal Not Legal
 4. Which of the following sequential plans is optimal? a. [right,down,up,left] Legal Not Legal b. [right,down,right,down] Legal Not Legal c. [right,down,right,down] Legal Not Legal d. [right,down,right,down] Legal Not Legal