We can use trees to help us understand how to solve problems.

States + Operators (State -> State)
Search: from Initial state to Final state (generalize with isFinal predicate)
BFS (with queue): Finding Shortest Solution
  Also keep Set of reached stated (so not loop back to explore any reached)
Examples
  Water Jug puzzle
    State    : amount of water in each jug.
    Operation: fill jug, empty jug, transfer jug x to jug y
               (amout(x)<amount-available(y) empty x into y;
                amout(x)>amount-available(y) top off y from x)
  Crossing the River: Farmer, feed, hen, fox
    State    : Side of each entity (and whether allowable)
    Operation: Farmer takes boat to other side with some entities
  15s Puzzle (8 puzzle)
    State    : Location of pieces
    Operation: Fill hole from top/bottom/left/right

Blind search vs. expand closest to solution (evaluation function)

Offer 3 pt extra credit to first student who solves another problem.

DFS + Backtracking:
Recursive call reduces problem size, increases
  solution Solve (Problem p, Solution s) {
    if (p is empty)
      return s;
    a = (choose aspect of p)
    p.remove(a);
    for (Iterator i = a.iterator(); i.hasNext(); ) {  //try all choices for a
      attempt = i.next();                             //maybe none!
      s.add(attempt)
      tempSol = Solve(p,s);                           //p smaller, s larger
      if (tempSol != null)
        return tempSol;
      s.remove(attempt)
    }

    return null;
}


Examples
  8 Queens
    P: row to fill; choose 1 row after another, iterator subset of columns
    S: Map[int/row] -> int/col
  Satisfiability: Illustrate with
    P: variable; choose F then T
    S: Map[String/variable] -> boolean
    -> NP complete, 3 Sat
  Maze exploration (also BFS, because find
    P: Extend to empty spot; choose open/adjacent
    S: Reachable + Last Reached
  Map coloring
    P: Regions left to color; choose possible colors
    S: Map[Region]->Color
  Blobs

DFS vs BFS

Game Playing
Opposing moves
Board evaluation (no good static function)
  Searching (when to stop) -inactive
Mini-max


