python - How to brute force a tree of 'yes/no' decisions? -

i want solve puzzle. don't know kind of code required it. problem exponential one.

description:

the player walks/runs 1 step @ time. there decision made; yes/no question. once question answered, player continues walking until next decision/question reached. continue until total distance covered.

the problem want see every possible route through (many python lists such ['y','y','n','y','n']). here code have written far: (the player in player() class, have removed because unimportant here.)

class solver(object):     """ solver object. """  def __init__(self, field):     self.field = field     self.dinc = 113     self.distance = 128  def take_step(self, player):     """ takes step , records players route. """     # adds 0 if there no decision made on step     # adds 1 if there decision made on 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 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 no response. resets danger. updates route decision. """     player.route[-1] = (player.step_id, 'n')     player.danger = 0     print 'no!'  def say_yes(self, player):     """ simulates yes response. updates route decision. """     player.route[-1] = (player.step_id, 'y')     print 'yes!' 

the solution of i'm looking this:

• walk until question reached
• make copy of route
• on route yes
• on route b (the copy) no

route a:
repeat above (this forks 2 routes)

route b:
repeat above (this forks 2 routes)

using code have far, like:

route_a = player() solver = solver()  # walk until battle reached solver.next_decision(route_a) # make copy of route (there 2 routes + route b) route_b = copy.deepcopy(route_a)  # on route 'yes' solver.say_yes(route_a) # on route b 'no' solver.say_no(route_b) # walk until next decision reached solver.next_battle(route_a) solver.next_battle(route_b) # then? 

this problem exponential, because @ each decision route forks 2 more routes. need of possibilities; happen know there less 512 possibilities computer can solve in instant.

each route stored in player.route instance (as list, eg: ['y','y','n','y'])

i have no idea how solve problem programmatically. appreciate ideas how structure code solve problem this.

actually, such data structure -- binary tree -- used in order avoid exponential problem mentioned. or, in other words, supposed list of 'y' , 'n' grow exponentially, don't need it, because have binary tree. know each way yes-or-no question.

but, if want print list asking for, in pseudo-code (since i'm lost c++, still can't program in python ;-) )

def recurse(node, s=''):     if node == end_node:         print s         return      recurse(node.left,  s + 'n')     recurse(node.right, s + 'y') 

then invoke function starting @ root or head node, i.e. recurse(root_node).