Sliding tiles solver in Python

Question

I've implemented the sliding blocks puzzle in Python to solve it using different algorithms. I'd like to know if the class "Sliding_blocks" is nicely designed or if I am missing concepts of OOP.

I think that the indices of the blocks are a bit obfuscated, because I mix tuples, lists and arrays (arrays are better to add but then I have to convert them to tuples at some point).

I use the A* algorithm with the number of misplaced blocks as heuristic function. It's quite slow and I think's it's because I have to create many copies of objects.

I'm more concerned with best practices than speed.

The code is:

#!/usr/bin/env python 
# -*- coding: utf-8 -*-
from __future__ import division
import numpy as np
from copy import copy, deepcopy
class Sliding_blocks():
 def __init__(self):
 self.size = 4
 self.block = self.generate_block()
 def generate_block(self):
 """Goal state"""
 block = np.arange(1,self.size**2)
 block.resize(self.size,self.size)
 return block
 def move(self, piece):
 """Moves the piece with index "piece" to free place, if possible"""
 if list(piece) in self.find_moves():
 self.block[tuple( self.find_free() )] = self.block[tuple(piece)]
 self.block[tuple(piece)] = 0
 return "success"
 else:
 return "error"
 def find_free(self):
 """Returns array of indices of the free cell"""
 free_position = np.where(self.block == 0)
 free_position = np.array(free_position).flatten()
 return free_position
 def find_moves(self):
 """Returns list of allowed indices to move"""
 from itertools import product
 free_position = self.find_free()
 return [list(free_position+i) for i in [[0,1],[1,0],[-1,0],[0,-1]] if tuple(i+free_position) in product(range(self.size),repeat=2)]
 def shuffle(self):
 steps = 30
 for i in xrange(steps):
 self.rand_move()
 def rand_move(self):
 from random import choice
 self.move(choice(self.find_moves()))
 #The following functions are used to find the solution
 def isWin(self):
 return (self.block == self.generate_block()).all()
 def total_misplaced(self):
 return np.sum( self.block != self.generate_block() )
def tree_search():#
 Game = Sliding_blocks()
 Game.shuffle()
 frontier = [[Game]]
 explored = []
 while 1:
 if frontier==[]: return "Error"
 path, frontier = remove_choice(frontier)
 endnode = path[-1]
 explored.append(endnode)
 if endnode.isWin(): return path
 #Iterate over all possible actions at endnode
 for action in allactions(endnode):
 if not action in explored and not action in frontier or action.isWin():
 pathtem=copy(path)
 pathtem.append(action)
 frontier.append(pathtem)
def allactions(obj):
 possible = obj.find_moves()
 actions = []
 for i in range(len(possible)): 
 actions.append(deepcopy(obj))
 actions[i].move(possible[i])
 return actions
#A*
def a_star(frontier):
 #Calculates the cost (lenght + number misplaced cells)
 #of all paths in frontier, returns the frontier
 #without the least expensive path and also returns that path
 lengths = [f[-1].total_misplaced()+cost(f) for f in frontier]
 shortest=[i for i,l in enumerate(lengths) if l<=min(lengths)]
 return frontier.pop(shortest[0]), frontier 
def cost(path): return len(path)
if __name__ == "__main__":
 remove_choice = a_star
 sol = tree_search()
 for s in sol: 
 print s.block
 print "\n"

• Tunaki: Hi, welcome to Code Review! This is a good first question and I hope you receive great answers!

Answer 1

Whether the code is well designed or not -- is hard to tell without using it. But I have several points:

1. It's good that you have small functions/methods which do one thing and do well. It's good that you wrote docstrings and comments.

2. shortest=[i for i,l in enumerate(lengths) if l<=min(lengths)] -- here you are calculating min(lengths) on each loop cycle. Calculate this and put into a variable.

3. Comply with PEP-8. def cost(path): return len(path) -> have two different lines. np.arange(1,self.size**2) use one space after commas. Game = Sliding_blocks() -- only classes should named CamelCased -> game = SlidingBlocks(). Use pylint to see all warnings.

4. Use enumerate:

   for i in range(len(possible)): 
    actions.append(deepcopy(obj))
    actions[i].move(possible[i])
   

Will become:

 for i, _possible in enumerate(possible): 
 action = deepcopy(obj)
 actions.append(action)
 action.move(_possible)

5. Move the imports to the top of the file

   def rand_move(self):
    from random import choice
   

6. Import module instead of objects from it.

   from itertools import product
   ...
   from random import choice
   

Will become:

import copy
import itertools
import random

7. Using constants? Name them uppercase and make global. Is it a setting? Pass it as an argument with a default value or store as a class attribute.

   def shuffle(self):
    steps = 30
    for i in xrange(steps):
    self.rand_move()
   

8. Fail early.

    if list(piece) in self.find_moves():
    self.block[tuple( self.find_free() )] = self.block[tuple(piece)]
    self.block[tuple(piece)] = 0
    return "success"
    else:
    return "error"
   

This can be rewritten as

 if list(piece) not in self.find_moves():
 return "error"
 ...
 return "success"

This will also reduce indentation.

return "error" -- this is a hardcoded string. Use a constant.

9. Indeed, using tuples and lists is hard to read and is slow

   if list(piece) in self.find_moves():
    self.block[tuple( self.find_free() )] = self.block[tuple(piece)]
    self.block[tuple(piece)] = 0
   

You should rethink this.