Depth First Game Trees

Having spent too much time writing search trees for solving puzzles I will now put an end to it by describing a template for the purpose. Any puzzle consists of a start state and a goal state and a set of rules to change state. The aim is to list the sequence of state changing actions that arrives at the goal state from a start state. Hence the general algorithm can be written as:

let seen-states = {start-state}

let Solve(current-state) =
  if current-state = goal-state
    return true
  else
    for-each action in possible-actions
        next-state = Do-Action(action, current-state)
        if NOT next-state in seen-states
          add-state(next-state, seen-states)
          if Solve(next-state)
             print-output action
             return true
    return false

Solve(start-state)

Notice that this is just the solution to the Water-Buckets problem with a few name changes. Simple as it is the devil is in details. In some problems like the Water-Buckets problem, the set of all possible states may small so that ‘seen-states’ can potentially store all of them in memory. In other cases the set of all states be may be too large. Think Rubik’s cube. In other cases the set of all possible states can be linearly ordered (we denote the relation as ‘<‘) and the state traversal never moves from  a state X to a state Y unless X < Y.  This is the case with BrianVita which is why the seen-states are not stored. This is easy to prove if you have a basic understanding of sets and relations.