Solving 15 puzzle

I'm trying to solve 15 puzzle using A* algorithm, but something really bad goes on in my get_solution() function that ruins performance. I guess there is a too much usage of maps in here, but I don't understand why it slows down my program so much. What do you think?

I would be really happy if you could review my coding style as well.

```
import random

# Class represents playing desk
class Desk(object):

SHUFFLE_NUMBER = 20 # changing to 200 and higher ruins everything

def __init__(self, width, height):
self.matrix =[]
for i in range(height):
row = [x + 1 for x in range(i width, (i+1) width)]
self.matrix.append(row)
self.matrix[height - 1][ width - 1] = 0

def height(self):
return len(self.matrix)

def width(self):
return len(self.matrix[0])

def __str__(self):
str_list = []
for r in self.matrix:
for c in r:
str_list.append(str(c) + "\t")
str_list.append("\n")
str_list.pop()
return "".join(str_list)

def __eq__(self, other):
if (self.width() != other.width() or self.height() != other.height()):
return False
for r in range(self.height()):
for c in range(self.width()):
if self.matrix[r][c] != other.matrix[r][c]:
return False;
return True

def __ne__(self, other):
return not self.__eq__(other)

def __hash__(self):
return hash(self.__str__())

def shuffle(self):
for i in range(Desk.SHUFFLE_NUMBER):
self.matrix = self.neighbors()[random.randint(0, len(self.neighbors()) - 1)].matrix

def get_element(self, row, col):
return self.matrix[row][col]

def set_element(self, row, col, value):
self.matrix[row][col] = value

def copy(self):
newDesk = Desk(self.width(), self.height())
for r in range(self.height()):
f

1. You can't fix what you can't measure

In order to improve the performance of your code, we need to be able to measure its performance, and that's hard to do, because your Puzzle15 class randomly shuffles the Desk associated with each instance, so it is not easy to set up and carry out a systematic test.

Let's fix that, by changing Puzzle15.__init__ so that it takes a Desk instance of our choosing:

def __init__(self, desk):
    self.desk = desk
    self.steps = 0

Now we can create some test cases:

def puzzle15_test_cases(n, width=4, height=4):
    """Generate 'n' pseudo-random (but repeatable) test cases."""
    random.seed(1252481602)
    for _ in range(n):
        desk = Desk(width, height)
        desk.shuffle()
        yield desk

TEST_CASES = list(puzzle15_test_cases(100))

And a function that times the solution of all the cases, using the timeit module:

from timeit import timeit

def puzzle15_time():
    """Return the time taken to solve the puzzles in the TEST_CASES list."""
    return timeit('[Puzzle15(desk).get_solution() for desk in TEST_CASES]',
                  'from __main__ import TEST_CASES, Puzzle15; gc.enable()',
                  number = 1)

(See here for an explanation of gc.enable().) It takes more than three minutes on my machine to solve all 100 test cases:

>>> puzzle15_time()
184.2024281024933

1. Use sets for fast lookup

The first obvious time sink is the open and closed sets. You implement these using lists, but Python's list does not have an efficient membership test: to implement neighbor in closed_set Python has to scan all the way along the list, comparing neighbor with each item in turn until it finds one that matches. By using set objects instead, we get a constant-time membership test. So change:

closed_set = []
openset = [start]

to:

closed_set = set()
openset = set([start])

and use the set.add() method instead of list.append(). This change gives us an immediate 28% speedup:

>>> puzzle15_time()
132.80268001556396

1. Use the power of the dictionary

The next obvious problem is lowest_score_element. You have a double loop:

for elem in openset:
    if (elem in score.keys()):

So for each position in openset, you construct a fresh list containing the keys of the dictionary score, and then you look up the position in the list (which, as explained above, might require comparing the position to every item in the list). You could just write:

for elem in openset:
    if elem in score:

so that the membership test uses the fast dictionary lookup.

But you don't even need to do this, because Python already has a function min for finding the smallest element in a collection. So I would implement the method like this:

def lowest_score_element(self, openset, score):
    return min(openset, key=score.get)

And that yields a very dramatic improvement:

>>> puzzle15_time()
3.443160057067871

1. Make positions immutable

Instances of the Desk class represent positions in the 15 puzzle. You need to look up these positions in sets and dictionaries, and that means they need to be hashable. But if you read the documentation for the special __hash__ method, you'll see that it says:


If a class defines mutable objects and implements a __cmp__() or __eq__() method, it should not implement __hash__(), since hashable collection implementations require that a object’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket).

Your Desk objects are currently mutable — they can be changed by the swap and set_element and shuffle methods. This makes them unsuitable for storing in sets or using as dictionary keys. So let's make them immutable instead. And at the same time, make the following improvements:

-
Use the more understandable name Position instead of Desk.

-
Write docstrings for the class and its methods.

-
Represent the matrix as a single tuple instead of a list-of-lists. This means that a cell can be fetched in a single lookup instead of two lookups.

-
Remove the get_element method (just look up cells directly, saving a method call) and remove the set_element method (it's not needed now that the class is immutable).

-
Represent the blank item as 15 rather than 0, to avoid the special case in heuristic_cost.

-
Remember where the blank element is, so that neighbours can be generated without having to search the matrix to find the blank.

-
Generate the neighbours instead of returning them as a list.

-
Speed up the __hash__ by using tuple.__hash__ instead of carrying out an expensive conversion to a string each time we want to compute the hash.

-
Rename swap and shuffle to swapped and shuffled since they now return new objects instead of modifying the old object in place.

-
Pass the number of swaps as a parameter to the shuffled method.

-
Avoid calling `self

StackExchange Code Review Q#33473, answer score: 27