Creating a tree without duplicates

Question

I am trying to create a tree with the different possible states of the well-known sliding puzzle

In case you don't know it, it's the one like:

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

Where you have to make it like this:

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

Basically, every state generates new states, depending on how the blank space can be moved (upwards, downwards, to the left, or to the right)

What I want is to create the tree with all states given the root as the initial state of the puzzle, but when adding children (new states) to the tree, it should check that that state is not added already anywhere in the tree

Would you mind helping me achieve that? Thanks in advance :)

Here's my current code which throws 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

Dipstick

It looks like in your case if value not in values: statement is always evaluating to True. – Joost

Yes, it's called the puzzle8 game. – Feeney

One thing here: Since you can always move from A to B and vice versa, there can not be any ordering between the two that puts A under B in a tree nor one that puts B under A. Rather, what you have is a graph, where a vertex is a state and an edge is an atomic operation that slides one tile. – Columbus

Answer 1

I'll take a shot at answering the immediate impediment 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 a limit. You could try to raise that limit (I'm halfway sure this can be configured somewhere), but there's another another, more general technique to fixing that.

In pseudocode a search through a tree (which seems to be what you're 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

The predicate is a function that returns a boolean value indicating whether the searched node is found, which generalizes this search.

Problem here is, that by the sheer height of the tree, this can exceed the recursion limit, as you saw. A different approach that avoids this limit is to not use recursion. Instead of storing the temporary states on the stack, build 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, important point here is that the call depth is moved to the temp container. However, let's look at a detail, the push and pop calls, because it's not fully clear what they do. If you wanted to mimick above recursive version, you would have to use a stack (LIFO). In addition, you'd have to push the children on the stack in reverse order, but the order of the children is probably irrelevant. This means that after the first iteration, you have all the direct children of the given node in the container. In the second iteration, one direct child is removed and processed, which adds the children of that node. In other words, the search goes into the depth of the tree first and it's therefore called "Depth First Search" (DFS).

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

One word on this non-recursive approach: This is at the same time a bit more flexible if you take it as base for further development. For example, if you had multiple ways to reach the same node (i.e. if it was not a tree), you could store all children you have reached already in a second container in order to avoid loops. Another way would be to order the children according to their distance from a solution in order not to follow paths that don't provide a benefit.

In general, recursion is a very rarely used tool. It is indeed important to understand it, in particular a recursive definition in mathematics, but using it in coding is often unpractical. You will find people that think different though, this is more of an opinion than a solid claim, even though I can put some experience and success behind it to back it up.

Columbus

Thanks for the detailed insight, would you mind helping me with how I could achieve this to search for parent node, instead of children? Or what could be the best way to check every item in the tree from its root to the last of its leaves? (Sorry if I'm asking too much, I'm basically starting with Python) – Dipstick

Answer 2

In addition to exceeding maximum recursion depth, I think your implementation may also be generating an infinite loop. Since the scope of the values list is localized to each to_tree call, there is no central place to look up if a state has already been visited. Here's an example with a stack-based iteration, using bit representation for the puzzle state, fitted in a 4 * 9 = 36 bit integer. For example:

123
456
780

Would be represented as:

0001 0010 0011
0100 0101 0110
0111 1000 0000

But chained together in reverse:

   0|   8|   7|   6|   5|   4|   3|   2|   1
0000 1000 0111 0110 0101 0100 0011 0010 0001

0b000010000111011001010100001100100001
=> 2271560481

initialState()
=> 2271560481

Let's add some functions to make and show a 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 index of zero:

def findZero(state):
  mask = 15
  i = 0

  while mask & state:
    mask = mask << 4
    i = i + 1

  return i

And move a neighbouring 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]

Let's add a 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)

Set the root and a global object, states_to_nodes, that will map the visited states to the node that holds that state as a value:

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

Here's a stack-based iteration that avoids the maximum recursion depth error:

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
"""

Horseweed

Hi, sorry for coming back here so late ... Would you mind explaining how I could get the children states of every child and add it to the tree while keeping the whole tree without any duplicates? As your current solution only shows the children of the initial state. Thanks in advance – Dipstick

@JahirFiquitiva sure: states_to_nodes is a dictionary mapping a state (a state is the permutation of our 9 numbers stored in 36 bits) to its children. The while loop checks if the state is already stored, if not maybe_new_state in states_to_nodes:, and adds the children only if the state is not already mapped. This results in being able to look up each state's children. In this data structure, though, children can point to their ancestors. – Shipmaster