title: Python3 RushHour solver using iterative deepening
body: <p>I'm trying to create a RushHour puzzle solver using iterative deepening depth-first search. Now when I execute the script it generates too much nodes and rapidly eats the whole memory (allocation speed around 20MB/s). I know my solution for storing states of the board is not perfect but it shouldn't eat so much memory. (The whole project can be found here <a href="https://j91321@bitbucket.org/j91321/rushhour.git" rel="nofollow" title="here"> here</a> )</p>
  
  <pre><code>import map from node import Node
  
  
  def all_moves(node):  # returns all valid moves for node
      state = node.state
      output = []
      for i in state.cars:
          car_id = i[0]
          y = i[1]
          x = i[2]
          for action in actions:
              movement = state.is_movable(action, y, x)
              if movement[1] != 0:
                  movement.append(car_id)
                  movement.append(action)
                  output.append(movement)
      return output
  
  
  def generate_all_child(node):  # creates every new state based on list of valid moves and makes it a child
      for move in all_moves(node):
          action = move[-1]
          car = move[0]
          car_id = move[-2]
          for step in range(1, move[1]+1):
              child_state = node.state.action(car_id, car, action, step)
              child_node = Node(child_state, node)
              node.add_child(child_node)
  
  
  def dls(node, node_depth):
      if node_depth &gt;= 0:
          generate_all_child(node)
          if node.state.is_solved():
              return node
          for child in node.children:
              dls(child, node_depth-1)
  
  
  stack = [] actions = ["left", "right", "up", "down"]
  
  mapa = map.Map() mapa.load("krizovatka.csv") mapa.display_matrix() mapa.load_cars() root = Node(mapa, None) stack.append(root)
  
  depth = 5 for i in range(1, depth+1):
      print(i)
      final = dls(root, i)
      print(len(root.children))
  </code></pre>