1. Formulate the 8-Queens problem as a constraint satisfaction problem with 8 variables (one for each column) whose domain is the set of possible row positions.  Then trace forward checking and domain splitting with arc consistency. A (near-solution) state is shown below.

2. Formulate the blocks world using STRIPS planning operators. The actions are stack  (move one block to the top of another) and unstack  (move one block to the table). The robot can hold only one block at a time.

To simplify the world, assume the only objects are the blocks and the table, and that the only relations are the on relation between (table and) blocks and the clear predicate on table and blocks. Also assume that it is not possible for more than one block to directly support another block (and vice versa).

3. The Sussman anomaly, shown below, is a simple planning problem that could not be solved by the early linear planners.  Show how a partial order planner would solve this problem with the blocks world operators de  ned above.

  C 

  B    A 

Start State

Goal State