Q-1: Write a program to solve the
water-jugs problem. You have three 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.
Q-2: Write a program to solve the bridge-crossing problem. Four people come to a
river during the night. There is a narrow bridge, but it can only hold two people
at a time. They have one torch and, because it’s night, the torch has to be used
when crossing the bridge. Person A can cross the bridge in one minute, person B
in two minutes, person C in five minutes, and person D in eight minutes. When
two people cross the bridge together, they must move at the slower person’s pace.
Find an optimal plan that requires the shortest time for the four people to cross
the bridge.
Q-3: Consider three heuristic functions generated from the following relaxed problems for the 15-puzzle:
- A tile can move from square A to square B if A is adjacent to B.
- A tile can move from square A to square B if B is blank.
- A tile can move from square A to square B.
The function from problem (1) is the Manhattan-distance
heuristic, the function from problem (2) is the Gaschnig's heuristic,
and the function from problem (3) gives the number of misplaced tiles.
Compare these three heuristic functions by measuring the execution time of the 15-puzzle program.
Q-4: Write a program to solve the vehicle-moving problem: n vehicles occupy squares (1, 1) through (n,
1) (i.e., the bottom row) of an n x n grid. The vehicles must be moved
to the top row but in reverse order; so the vehicle i that starts in
(i, 1) must end up in (n – i + 1, n). On each time step, every one of
the n vehicles can move one square up, down, left, or right, or stay
put; but if a vehicle stays put, one other adjacent vehicle (but not
more than one) can hop over it. Two vehicles cannot occupy the same
square.
Q-5 (optional): A classical planning problem can be formulated as a
satisfiability problem. This planning-as-satisfiability approach finds
a bounded-length sequence of states, where the first state corresponds
to the initial state, the last state satisfies the goal condition, and
each pair of successive states constitutes a valid action. Write a
program for the vehicle-moving problem using the
planning-as-satisfiability formulation.