title: How to brute force a tree of 'yes/no' decisions?
body: <p>I want to solve a puzzle. But I simply don't know what kind of code is required for it. The problem is an exponential one.</p>
  
  <p><strong>Description:</strong></p>
  
  <p>The Player walks/runs one step at a time. Sometimes there will be a decision to be made; that is a yes/no question. Once the question is answered, the player continues walking until the next decision/question is reached. Continue this until the total distance is covered.</p>
  
  <p><img src="https://i.stack.imgur.com/CcEkq.png" alt="The problem is exactly like this."></p>
  
  <p>The problem is I want to see every possible route through this (many python lists such as ['y','y','n','y','n']). Here is the code I have written so far: (the Player is in a <code>Player()</code> class, I have removed it because it is unimportant here.)</p>
  
  <pre><code>class Solver(object):
      """ Solver object. """
  
  def __init__(self, field):
      self.field = field
      self.dinc = 113
      self.distance = 128
  
  def take_step(self, player):
      """ Takes a step and records players route. """
      # Adds 0 if there is no decision to be made on this step
      # Adds 1 if there is a decision to be made on this step
  
      player.run(self.dinc)
      if self._is_decision_time(player):
          player.route.append((player.step_id, 1))
      else:
          player.route.append((player.step_id, 0))
  
  def next_decision(self, player):
      """ Accepts a player object. Walks until reaches next decision. """
      while not self._is_decision_time(player):
          self.take_step(player)
      self.display_stats(player)
  
  def say_no(self, player):
      """ Simulates a no response. Resets danger. Updates route with decision. """
      player.route[-1] = (player.step_id, 'n')
      player.danger = 0
      print 'no!'
  
  def say_yes(self, player):
      """ Simulates a yes response. Updates route with decision. """
      player.route[-1] = (player.step_id, 'y')
      print 'yes!'
  </code></pre>
  
  <p>The solution of what I'm looking for is like this:</p>
  
  <ul>
  <li>Walk until a question is reached</li>
  <li>Make a copy of the route</li>
  <li>On route A say Yes</li>
  <li>On route B (the copy) say No</li>
  </ul>
  
  <p>Route A:<br>
  repeat what is above (this forks another two routes)</p>
  
  <p>Route B:<br>
  repeat what is above (this forks another two routes)</p>
  
  <p>Using the code I have so far, it is something like:</p>
  
  <pre><code>route_a = Player()
  solver = Solver()
  
  # walk until a battle is reached
  solver.next_decision(route_a)
  # make a copy of the route (there are now two routes A + route B)
  route_b = copy.deepcopy(route_a)
  
  # on route A say 'yes'
  solver.say_yes(route_a)
  # on route B say 'no'
  solver.say_no(route_b)
  # walk until the next decision is reached
  solver.next_battle(route_a)
  solver.next_battle(route_b)
  # Then?
  </code></pre>
  
  <p>This problem is exponential, because at each decision the route forks into two more routes. I need all of the possibilities; I happen to know there are less than 512 possibilities so a computer can solve it in an instant.</p>
  
  <p>Each route will be stored in a Player.route instance (as a list, eg: ['y','y','n','y'])</p>
  
  <p>I just have no idea how to solve a problem like this programmatically. I would appreciate some ideas as to how to structure code to solve a problem like this.</p>