Describe the initial state, goal test, successor function, and path-cost function for the following problems.
  1. (From ACM Programming Competition NY 2003) You are given a 7 by 7 board of holes, where some holes are filled with pegs. You may jump a peg over an adjacent peg to remove that adjacent peg, as long as the jumping peg lands in an unoccupied hole. There are some holes that may never be occupied by a peg. The goal is to leave the board with exactly one peg at a specified location. Here are some sample initial peg configurations (where x is a hole that can never be occupied by a peg, e is an empty hole, o is a hole containing a peg, E is an initially empty hole where the last peg should end in, O is an initially occupied hole, where the last peg should end in):
    x x e e e x x
    x x o e e x x
    e e o e e e e
    e e o O e e e
    e e e e e e e
    x x e e e x x
    x x e e e x x
    
    x x e E e e e
    x e e e e e e
    e e e o o e e
    e e e x e e e
    e e e e e e e
    e e e e e e e
    e e e e e e e
    
  2. You are given six coin denominations (for example 1, 5, 10, 25, 50, 100) and a target amount. The objective is to come up with a minimum "coin formula" whose total is the target amount. Additions and subtractions of the denominations are allowed in the formula, and you wish to use the smallest number of coins possible. This demonstrates how the currency can be used during purchase transactions (additions comprise the amount tendered, subtractions represent change). In the example given, the minimum coin formulas for some target amounts are:
    31 = 25 + 5 + 1
    47 = 50 - 1 - 1 -1
    90 = 100 - 10
  3. (From ACM Programming Competition NY 2003) You are given an m by n chessboard with obstacles (positions that should never be traversed) and an initial location. The goal is to find a "rook circuit", a tour of all (non-obstacle) positions using a rook such that the positions are visited exactly once and the final location is the initial location.
  4. (From Exercise 3.7d of the textbook) 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.