# State space search for sliding tile puzzle

I am working on state space search (8 Puzzle) in Python and when I run my program with python3 -m profile, I find out that most of time program performs a few functions. I would like to optimize functions bellow (if it's possible).

I am using dictionary node, whose structure is:

{
'id': string,  # Unique ID of node, e. g. '123456708'.
'state': array,  # Numpy array 3x3 with unique numbers 1-8 and 0, e. g. [[1 2 3] [4 5 6] [7 0 8]].
'pos': tuple,  # Current position of 0 in node's state, e. g. (2, 1).
}


## swap

Function accepts 2D array, pos1 and pos2 and returns new array with swapped elements on positions.

# [1 2 3]                            [0 2 3]
# [4 5 6] -> swap((2, 1), (0, 0)) -> [4 5 6]
# [7 0 8]                            [7 1 8]
def swap(array, pos1, pos2):
result = numpy.copy(array)
result[pos1], result[pos2] = result[pos2], result[pos1]
return result


## create

Function that accepts state and pos of 0 in state and returns node with this state.

def create(state, pos):
return { 'id': hash(state.tostring()), 'state': state, 'pos': pos }


## move

Function, that accepts node and vector change and returns new node with changed state. New state is created when 0 in state is moved by vector (changeY, changeX) change. If new state has invalid index, return None instead.

# [1 2 3]                   [1 2 3]
# [4 5 6] -> move(-1, 0) -> [4 0 6]
# [7 0 8]                   [7 5 8]
def move(node, change):
newPos = (node['pos'] + change, node['pos'] + change) # numpy.add(node['pos'], change) is slower.

if 0 <= newPos <= 2 and 0 <= newPos <= 2: # Valid index
newState = swap(node['state'], node['pos'], newPos)
return create(newState, newPos)

return None # Invalid index.


## getSuccessors

Function that accepts node in state and returns all nodes which state is about -1 or 1 different vertically or horizontally (not both):

# [1 2 3]                       [1 2 3] [1 2 3] [1 2 3]
# [4 5 6] -> getSuccessors() -> [4 0 6] [4 5 6] [4 5 6]
# [7 0 8]                       [7 5 8] [0 7 8] [7 8 0]
def getSuccessors(node):
moves = [
move(node, (-1, 0)),
move(node, (1, 0)),
move(node, (0, -1)),
move(node, (0, 1)),
]

return list(filter(lambda node: node is not None, moves))


## findPath

Function accepts numpy 3x3 arrays init and goal and search successors of init until one of successors will be goal.

def findPath(init, goal):
explored = {} # Already explored nodes.
pos = numpy.where(init == 0)
unexplored = [create(init, (pos, pos))] # Unexplored nodes.

while True:
if not unexplored: # If there is no node to explore, puzzle has no solution.
return None

node = unexplored.pop(0) # Bfs algorithm is slow, but for testing purposes.

if numpy.array_equal(node['state'], goal):
return 'Success' # Should be path, but for now is not important.

explored[node['id']] = node

for successor in getSuccessors(node): # Add successors to unexplored nodes.
if successor['id'] not in explored:
unexplored.append(successor)



When I run this program python3 puzzle.py, it takes 13.36 seconds:

import time
import numpy
start = time.time()
init = numpy.array([[7, 2, 4], [5, 0, 6], [8, 3, 1]])
goal = numpy.array([[1, 3, 0], [5, 2, 6], [4, 7, 8]])
print(findPath(init, goal)) # 'Success'
end = time.time()
print(end - start) # 13.36 s


With python3 -m profile puzzle.py | grep "puzzle.py":

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000   52.771   52.771 profile:0(<code object <module> at 0x7fa52c125300, file "puzzle.py", line 1>)
1    0.131    0.131   52.752   52.752 puzzle.py:1(<module>)
1638628    6.305    0.000   25.991    0.000 puzzle.py:12(move)
409657    4.410    0.000   31.730    0.000 puzzle.py:21(getSuccessors)
1638628    1.330    0.000    1.330    0.000 puzzle.py:29(<lambda>)
1    3.066    3.066   52.195   52.195 puzzle.py:31(findPath)
1106988    3.519    0.000   14.525    0.000 puzzle.py:4(swap)
1106989    3.049    0.000    5.161    0.000 puzzle.py:9(create)


Most of the time was move executed (6.3 s), then getSuccessors (4.4 s), swap, findPath and create. Is there any way to optimize these functions? Here is the whole program (even slower than on my PC).

The initial approach definitely has a number of "bottlenecks" and space for optimizations. Let me present and explain the crucial points:

• starting with good naming: don't give Python identifiers/functions camelCased names. We'll have find_path, get_successors etc.
• explored dict accumulates a great number of dictionaries (nodes) indexed by their id attribute ("hash"). But those dictionaries are not used, only keys are used to keep track of processing unique ids (hashes). Memory-free solution for this point is using set instead to keep unique hashes. explored = set()
• unexplored list. At the end of the processing I noticed it grown to size of 53003. As the main operations on this list are appending to and popping out the 1st item - the optimized way would be to use a high-performance deque object (Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction)
• function move performs a lot of falsy calls (returning None). That makes the caller get_successors accumulate both valid and falsy movements (moves list) and perform filtration on each call. Instead, we'll make get_successors to work as generator function which yields only successfully moved nodes (after valid movements)
• looping over for successor in getSuccessors(node): performs a hundreds of redundant iterations testing successors(nodes) which hashes were already present in explored hash storage. To watch that happened you can add else: branch with debugging printing to if successor['id'] not in explored: ... condition within the loop. To avoid that, in connection to the previous Optimization tip, we'll extend get_successors function more to get correctly moved nodes that aren't present in explored hash-set.

From theory to practice:

import numpy as np
import time
from collections import deque

def swap(array, pos1, pos2):
result = np.copy(array)
result[pos1], result[pos2] = result[pos2], result[pos1]
return result

def create(state, pos):
return {'id': hash(state.tostring()), 'state': state, 'pos': pos}

def move(node, change):
new_pos = (node['pos'] + change, node['pos'] + change)  # np.add(node['pos'], change) is slower.

if 0 <= new_pos <= 2 and 0 <= new_pos <= 2:  # Valid index
new_state = swap(node['state'], node['pos'], new_pos)
return create(new_state, new_pos)

def get_successors(node, explored):
for new_pos in ((-1, 0), (1, 0), (0, -1), (0, 1)):
changed_node = move(node, new_pos)
if changed_node and changed_node['id'] not in explored:
yield changed_node

def find_path(init, goal):
explored = set()  # Already explored nodes.
pos = np.where(init == 0)
unexplored = deque([create(init, (pos, pos))])  # Unexplored nodes.

while True:
if not unexplored:  # If there is no node to explore, puzzle has no solution.
return None

node = unexplored.popleft()

if np.array_equal(node['state'], goal):
return 'Success'  # Should be path, but for now is not important.

for successor in get_successors(node, explored):  # Add successors to unexplored nodes.
unexplored.append(successor)

start = time.time()
init = np.array([[7, 2, 4], [5, 0, 6], [8, 3, 1]])
goal = np.array([[1, 3, 0], [5, 2, 6], [4, 7, 8]])

print(find_path(init, goal))
end = time.time()
print(end - start)


The output:

Success
5.768321752548218

• Thanks for useful hints and explanation. The program is now really 2 times faster. – Michal Oct 14 '19 at 11:42
• @Michal, you're welcome – RomanPerekhrest Oct 14 '19 at 15:24