Give the initial state, goal test, successor function, and cost function for each of the following. Choose a
formulation that is precise enough to be implemented.
ƒ You have to color a planar map using only 4 colors, in such a way that no two adjacent regions have
the same color.
Initial state: No regions colored.
Goal test: All regions colored, and no two adjacent regions have the same color.
Successor function: Assign a color to a region.
Cost function: Number of assignments.
ƒ A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling. He
would like to get the bananas. The room contains 2 stackable, movable, climbable 3-foot-high crates.
Initial state: Same as problem definition.
Goal test: Monkey has bananas.
Successor function: Hop on crate; Hop off crate; Push crate from one spot to another; Walk from one spot
to another; Grab bananas (if standing on crate).
Cost function: Number of actions.
ƒ You have a program that outputs the message “illegal input record” when fed a certain file of input
records. You know that processing of each record is independent of the other records. You want to
discover what record is illegal.
Initial state: Considering all input records.
Page 3 of 5
Goal test: Considering a single record, and it gives “illegal input” message.
Successor function: Run again on the first half of the records; run again on the second half of the records.
Cost function: Number of runs.
Note: This is a contingency problem; you need to see whether a run gives an error message or not to decide
what to do next.
ƒ You have 3 jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet. You can fill the
jugs up or empty them out from one to another or onto the ground. You need to measure out exactly
one gallon.
Initial state: jugs have values [0, 0, 0]
Goal test: jugs have values [i, j, k], where one of i, j, k is 1.
Successor function: given values [x, y, z], generate [12, y, z], [x, 8, z], [x, y, 3] (by filling); [0, y, z], [x, 0, z],
[x, y, 0] (by emptying); or for any two jugs with current values x and y, pour y into x; this changes the jug
with x to the minimum of x+y and the capacity of the jug, and decrements the jug with y by the amount
gained by the first jug.
Cost function: Number of actions.