"""
 backtrack_class_permute.py

 Backtrack is a python template class for backtrack search,
 a recursive depth-first search of a tree of possible moves,
 where each "move" is typically an extension of the current result,
 and a downward branch of the tree.

 Permute is a class that inherits from Backtrack,
 showing an explicit example of how this works.

 $ python backtrack_class_permute.py
  in search   []
  in search       ['a']
  in search           ['a', 'b']
  in search               ['a', 'b', 'c']
  in search           ['a', 'c']
  in search               ['a', 'c', 'b']
  in search       ['b']
  in search           ['b', 'a']
  in search               ['b', 'a', 'c']
  in search           ['b', 'c']
  in search               ['b', 'c', 'a']
  in search       ['c']
  in search           ['c', 'a']
  in search               ['c', 'a', 'b']
  in search           ['c', 'b']
  in search               ['c', 'b', 'a']
 ['a', 'b', 'c']
 ['a', 'c', 'b']
 ['b', 'a', 'c']
 ['b', 'c', 'a']
 ['c', 'a', 'b']
 ['c', 'b', 'a']

 Jim Mahoney | cs.marlboro.edu | Apr 2013 | MIT License
"""

class Backtrack(object):
    """ A generic backtrack search.
        To implement a specific problem, you'll need to override
        at least __init__() , is_solution() , and get_moves()
        in a class which inherits from this.
    """

    def __init__(self):
        self.result = []         # the current (partial) solution 
        self.solutions = []      # saved full solutions

    def is_solution(self):
        """ Return True if self.result is a full solution of the problem. """
        return False

    def process_solution(self):
        """ Do something with this solution. """
        # The default is to save each solution as a string.
        self.solutions.append(str(self.result))

    def get_moves(self):
        """ Return list of possible extensions to current result. """
        return []

    def do_move(self, move):
        """ Move down the tree, i.e. extend self.result with move. """
        self.result.append(move)

    def undo_move(self, move):
        """ Move up the tree, i.e. remove last move from self.result. """
        self.result.pop()

    def search(self, verbose=False):
        """ Do the recursive depth-first backtrack tree search. """
        if verbose:
            print " in search   " + "    "*len(self.result) + str(self.result)
        if self.is_solution():
            self.process_solution()
        else:
            for move in self.get_moves():
                self.do_move(move)
                self.search(verbose)
                self.undo_move(move)

class Permute(Backtrack):
    """ An example of a backtrack search: find permutations of some symbols """
    # The variables in this implementation are :
    #    result        (partial) list of permuted symbols
    #    in_result     list of True/False marking symbols in/out of result[]
    #    move          index (i.e. 0, 1, 2, ...) into self.symbols[]

    def __init__(self, symbols = ['a', 'b', 'c']):
        super(Permute, self).__init__()    # Call Backtrack __init__()
        self.symbols = symbols             # e.g. ['a', 'b', 'c']
        self.N = len(symbols)              # e.g. 3
        self.in_result = [False] * self.N  # e.g. [False, False, False]

    def is_solution(self):
        return len(self.result) == self.N  # all N symbols in result?

    def do_move(self, move):
        self.result.append(self.symbols[move])  # grow result
        self.in_result[move] = True             # mark symbol used
        
    def undo_move(self, move):
        self.result.pop()                       # shrink result
        self.in_result[move] = False            # mark symbol unused

    def get_moves(self):
        """ Return a list of the indices of the symbols
            that aren't yet in self.result """
        moves = []                      # Accumulate legit moves here.
        for i in xrange(self.N):        # Consider each index e.g. (0, 1, 2)
            if not self.in_result[i]:   #  if that symbol isn't in result yet
                moves.append(i)         #    then it is a possible move.
        return moves

def main():
    p = Permute(symbols = ['a', 'b', 'c'])
    p.search(verbose = True)
    for s in p.solutions:
        print s

if __name__ == "__main__":
    main()