title: Tic Tac Toe with recursion (Python)
body: <p>I can't figure out how to tie these functions together for a hard AI, in which it can never lose. I'm supposed to be using recursion in some form or fasion and these function names and contracts were pre-written, I filled in the actual definition. Much googling later, I can't find anything that relates. Any ideas fellas?</p>
  
  <pre><code>"""
  
  
  State S2 is a *successor* of state S1 if S2 can be the the
  next state after S1 in a legal game of tic tac toe.
  
  safe: state -&gt; Bool
  successor: state x state -&gt; Bool
  
  1. If S is over, then S is safe if 'x' does not have 3 in a row in S.
  2. If it is o's move in S, then S is safe iff at least one successor of S is safe.
  3. If it is x's move in S, then S is safe iff all successors of S are safe.
  
  A *stateList* is a list of states. 
  """
  
  
  # safe: state-&gt; Bool
  #
  # A state S is *safe* if player 'o' can force a win or tie from S.
  
  def safe(S):
      if over(S): return not threeInRow('x',S)
      if turn(S)=='o': return someSafeSuccessor(S)
      if turn(S)=='x': return allSafeSuccessors(S)
  
  def threeInRow(p,S):
      if p == 'x':
          if all(t in S[0] for t in (1,2,3)):
              return True
          elif all(t in S[0] for t in (4,5,6)):
              return True
          elif all(t in S[0] for t in (7,8,9)):
              return True
          elif all(t in S[0] for t in (1,4,7)):
              return True
          elif all(t in S[0] for t in (2,5,8)):
              return True
          elif all(t in S[0] for t in (3,6,9)):
              return True
          elif all(t in S[0] for t in (1,5,9)):
              return True
          elif all(t in S[0] for t in (3,5,7)):
              return True
      else:
          if all(t in S[1] for t in (1,2,3)):
              return True
          elif all(t in S[1] for t in (4,5,6)):
              return True
          elif all(t in S[1] for t in (7,8,9)):
              return True
          elif all(t in S[1] for t in (1,4,7)):
              return True
          elif all(t in S[1] for t in (2,5,8)):
              return True
          elif all(t in S[1] for t in (3,6,9)):
              return True
          elif all(t in S[1] for t in (1,5,9)):
              return True
          elif all(t in S[1] for t in (3,5,7)):
              return True
  
  # someSafeSuccessor: state -&gt; Bool
  #
  # If S is a state, someSafeSuccessor(S) means that S has
  # at least one safe successor.
  
  def someSafeSuccessor(S):
      flag = False
      # flag means we have found a safe successor
      for x in successors(S):
          if safe(x): flag = True
      return flag
  
  # allSafeSuccessors: state -&gt; Bool
  #
  # If S is a state, allSafeSuccessors(S) means that every
  # successor of S is safe.
  def allSafeSuccessors(S):
    flag = True
    for x in successors(S):
      if not safe(x): flag = False
    return flag    
  
  
  # successors: state -&gt; stateList
  #
  # successors(S) is a list whose members are all of the successors of S.
  def successors(S):
    stateList=[]
    for i in range(1,10):
      if empty(i,S):
        stateList.extend(S[0],S[1]+[i])
    return stateList
  </code></pre>