Creating a tree without duplicates

Question

I am trying to create a tree with various possible states of a famous sliding puzzle

If you do not know this, this is one thing:

[3 5 2] [4 1] [8 6 7] 

Where you should do it like this:

 [1 2 3] [4 5 6] [7 8 ] 

In principle, each state generates new states, depending on how you can move the empty space (up, down, left or right).

I want to create a tree with all states, considering the root as the initial state of the puzzle, but when adding children (new states) to the tree, he must check that this state is not added anywhere in the tree

Could you help me with this? Thanks in advance:)

Here is my current code that throws a RecursionError: maximum recursion depth exceeded while calling a Python object

Node class:

 class Node(object): def __init__(self, value, parent=None): self.parent = parent self.value = value self.children = [] def append(self, obj): if obj is not self.parent and obj not in self.children and obj is not None: self.children.append(obj) def has_children(self): return len(self.children) > 0 def __iter__(self): yield self.value for v in chain(*map(iter, self.children)): yield v def find_root(self): p = self while p.parent is not None: p = p.parent return p 

Tree generation method (consider self as a puzzle state):

 def to_tree(self, parent=None): values = [] if parent is not None: for child in parent.find_root(): values.append(child) value = nd.Node(self, parent) if value not in values: children = [move[1].to_tree(value) for move in self.get_possible_movements()] for child in children: if child is not None: value.append(child) return value else: return None 

Answer 1

I will try to answer the immediate obstacle to your progress:

 RecursionError: maximum recursion depth exceeded while calling a Python object 

This means that the number of "active" function calls (and their local state) exceeds the limit. You can try to raise this limit (I'm halfway sure that this can be set up somewhere), but there is another, more general method for fixing this.

In pseudo code, a tree search (which is similar to what you are doing) looks like this:

 find(predicate, node): if predicate(node): return node # found it for child in node.children: res = find(predicate, child): if res: return res # found it return false # not found 

predicate is a function that returns a boolean indicating whether a found node is found that generalizes this search.

The problem is that at the highest tree height, this can exceed the recursion limit, as you saw. Another approach that avoids this limitation is to not use recursion. Instead of saving temporary states on the stack, create a dedicated container for them:

 find(predicate, node): temp = [node] while not temp.empty(): node = temp.pop() if predicate(node): return node # found it for child in temp.children: temp.push(child) return false # not found 

Now it’s important to note that the call depth moves to the temp container. However, let's look at the details, the push and pop calls, because they did not fully understand what they were doing. If you want to emulate a recursive version, you will have to use the stack (LIFO). In addition, you will have to push the children onto the stack in the reverse order, but the order of the children probably doesn't matter. This means that after the first iteration, you have all the direct children of this node in the container. At the second iteration, one direct child is removed and processed, which adds children to this node. In other words, the search first goes deeper into the tree, and so it is called “Deep First Search” (DFS).

A variation of this is called "Breadth First Search" (BFS). There you use a queue (FIFO) instead of a stack (LIFO) as a container. The state after the first iteration is the same, all direct children of this node. However, he then checks these children and adds his children to the container, but he is just starting to check his grandchildren after all the children have been checked.

One word on this non-recursive approach: it is at the same time a little more flexible if you consider it the basis for further development. For example, if you had several ways to reach the same node (i.e. if it wasn’t a tree), you can save all the children that you have already reached in the second container to avoid loops. Another way would be to arrange the children according to their distance from the decision, so as not to follow paths that do not provide benefits.

In general, recursion is a very rarely used tool. It is really important to understand, in particular, the recursive definition in mathematics, but using it in coding is often impractical. You will find people who think differently, but this is more an opinion than a firm claim, although I can make some experience and success to support it.

Answer 2

Besides exceeding the maximum recursion depth, I think your implementation can also generate an infinite loop. Since the values list area is localized for each to_tree call, a central place to search does not exist if the state has already been visited. Here's a stack-based iteration example using the bit representation for the puzzle state set to an integer 4 * 9 = 36 bits. For instance:

 123 456 780 

Will be presented as:

 0001 0010 0011 0100 0101 0110 0111 1000 0000 

But connected together in the opposite direction:

  0| 8| 7| 6| 5| 4| 3| 2| 1 0000 1000 0111 0110 0101 0100 0011 0010 0001 0b000010000111011001010100001100100001 => 2271560481 initialState() => 2271560481 

Add some functions to create and display state:

 from sys import stdout def showState(state): mask = 15 for i in xrange(9): if i % 3 == 0 and i > 0: stdout.write("\n") stdout.write(str((state & mask) >> 4 * i)) mask = mask << 4 stdout.write("\n") def makeState(arr): state = 0 for i in xrange(9): state = state | (arr[i] << 4 * i) return state def initialState(): return makeState([1,2,3,4,5,6,7,8,0]) 

Now we need to find the zero index:

 def findZero(state): mask = 15 i = 0 while mask & state: mask = mask << 4 i = i + 1 return i 

And move the adjacent number to the cell with zero:

 def move(state, fromIdx, toIdx): x = (state & (15 << 4 * fromIdx)) >> 4 * fromIdx state = state & (2**36 - 1 ^ (15 << 4 * fromIdx) ^ (15 << 4 * toIdx)) state = state | (x << 4 * toIdx) return state def moves(idx): # 012 # 345 # 678 return [ [1,3], [0,2,4], [1,5], [0,4,6], [1,3,5,7], [2,4,8], [3,7], [4,6,8], [5,7] ][idx] 

Add a new version of the Node class you're working with:

 class Node(object): def __init__(self, state, parent=None): self.parent = parent self.state = state self.children = [] def append(self, obj): self.children.append(obj) 

Define the root and the states_to_nodes global object that will display the states you visited in the Node that contains this state as a value:

 root = Node(initialState()) states_to_nodes = {initialState(): root} 

The stack based iteration is performed here, which avoids the error of the maximum recursion depth:

 stack = [root] while stack: node = stack.pop() zero_index = findZero(node.state) for i in moves(zero_index): maybe_new_state = move(node.state, i, zero_index) if not maybe_new_state in states_to_nodes: new_node = Node(maybe_new_state) states_to_nodes[maybe_new_state] = new_node node.append(new_node) stack.append(new_node) else: node.append(states_to_nodes[maybe_new_state]) 

Output:

 example_state = makeState([5,1,3,8,6,0,2,7,4]) print "Example state:\n" showState(example_state) print "\nChildren states:\n" for child in states_to_nodes[example_state].children: showState(child.state) print """ Example state: 513 860 274 Children states: 510 863 274 513 806 274 513 864 270 """