2-1.
 a. Moving a car from position a to position b is illegal if
  - it is not a direct forward or backward motion
  - it is the ice cream truck and some other car is blocking it
  - it is any other car and some other car is blocking it
 otherwise it is legal

   The third condition is relaxed in the given heuristic.  Note that
   the ice cream truck is being handled differently (otherwise all
   heuristic values would be "1").

 b. optimal sequence with f values

   initial board: 3
   green truck up: 4
   pink car left: 5
   green truck down: 5
   green car down: 5
   red car out=goal: 5

2-2.

   Here's one idea.  For each car that is in the way of the ice cream
   truck, add one.  Look to see if it has room to get out of the way.
   If not, add one and delete all cars that it may touch to get out.
   Finally, add one for the moving ice cream truck itself.

 a. why admissible

   Any car that's blocked must also get out of the way.  By deleting
   any car that might be touched, this makes sure we don't double
   count a car that could move once and get out of the way of multiple
   cars.  This keeps it admissible.

 b. relaxation?

    Sure.  Say at a given state the set of cars blocking the icecream car
    is A. Then we are allowing the cars blocking cars in set A to drive
    over other cars.

 c. give f values

   initial board: 4
   green truck up: 4
   pink car left: 5
   green truck down: 5
   green car down: 5
   red car out=goal: 5

2-3.

 a. 3^n-n*(n-1)*2^(n-3)

 b. Introduce a set of n-1 counting variables and connected them up in
    a binary tree over the nodes of the graph.  Each can take on values
    "0, 1, 2, many".  The ones connected to coloring nodes have legal
    values:

	node1 node2 counting-var
          *     *       0
          *     B       1
          B     *       1
          B     B       2

    where the * values take on R or G for a total of 9 legal values.

    The other counting variables in the tree have legal value lists
    that look like this:

	child-1	child-2	parent
	0	0	0
	0	1	1
	1	0	1
	1	1	2
	0	2	2
	2	0	2
	1	2	many
	2	1	many
	2	2	many
	many	1	many
	1	many	many
	many	2	many
	2	many	many
	many	many	many
	0	many	many
	many	0	many

   Finally, the root of the counting-var tree is constrained to have
   values 0, 1, or many.  What this does is add up all the blue values
   (igoring precise values greater than 2) and insist that the total
   is not equal to 2.