# Game of 15 - A* search

I would be really thankful for review of this homework. I'm trying to write better code in terms of readability and design patterns.

This program solves the classic 15 slider puzzle with A* search. The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle. If the size is 3×3 tiles, the puzzle is called the 8-puzzle or 9-puzzle, and if 4×4 tiles, the puzzle is called the 15-puzzle or 16-puzzle named, respectively, for the number of tiles and the number of spaces. The object of the puzzle is to place the tiles in order (see diagram) by making sliding moves that use the empty space.

https://en.wikipedia.org/wiki/15_puzzle

# python3.5

import heapq
import itertools
import numpy as np

class Board:
def __init__(self, board):
self.goalconfig = list(range(1, 16)) + [0]
self.board = board
self.distancefromstart = 0
self.parent = None
self.distance = self.calculate_distance()

def __repr__(self):
return ('\nBoard: \n{} \nDistance: {}\nFrom start:{}'.
format(np.matrix(self.board).reshape(4, 4),
self.getdistance(), self.distancefromstart))

def __gt__(self, board2):
return self.gettotaldistance() > board2.gettotaldistance()

def __lt__(self, board2):
return self.gettotaldistance() < board2.gettotaldistance()

def calculate_distance(self):
"""
:return: Sum of taxicab distances between board and goal
"""
distance = 0
for index, tile in enumerate(self.board):
if tile is not self.goalconfig[index]:
distance += self.taxicabdistance(index,
self.goalconfig.index(tile))

return distance

def getdistance(self):
return self.distance

def gettotaldistance(self):
return self.distance + self.distancefromstart

def taxicabdistance(self, index1, index2):
y1, x1 = divmod(index1, 4)
y2, x2 = divmod(index2, 4)
return abs(x2 - x1) + abs(y2 - y1)

def swapwithindex(self, index):
"""
:swaps index and empty cell.
:return: Board object
"""
tempboard = self.board[:]
index0 = tempboard.index(0)
tempboard[index0], tempboard[index] = tempboard[index], tempboard[
index0]
return Board(tempboard)

def allpositions(self):
"""
:return: List of possible boards that could be generated from instance board
"""
import random
empty = self.board.index(0)
movable = [index for index in range(16) if
self.taxicabdistance(empty, index) == 1]
boards = []
for move in movable:
boards.append(self.swapwithindex(move))
random.shuffle(boards)
return boards

def solver(board):
"""
:board: Board object
:closed: processed nodes
:distancesdict: hashtable of proc.nodes
:return: List of boards leading to solution
"""

def pushpositions(board, queue, closed, distancesdict):
"""
pushes all position of the board to priority queue
:param queue: priority queue list
:param board: Board object
"""
if board.getdistance() == 0:
return board
for childboard in board.allpositions():
childboard.parent = board
childboard.distancefromstart = board.distancefromstart + 1
if childboard.getdistance() == 0:
return childboard
try:
if distancesdict[
str(childboard.board)] > childboard.gettotaldistance():
heapq.heappush(queue, childboard)
distancesdict[
str(childboard.board)] = childboard.gettotaldistance()
except KeyError:
heapq.heappush(queue, childboard)
distancesdict[
str(childboard.board)] = childboard.gettotaldistance()

open = []
closed = []
distancesdict = {str(board.board): 0}
result = None
heapq.heappush(open, board)
while open:
top = heapq.heappop(open)
result = pushpositions(top, open, closed, distancesdict)
if result:
# todo Refactor when result found
return result
distancesdict[str(top.board)] = top.gettotaldistance()
closed.append(top)

board = Board([1, 2, 3, 4, 5, 6, 7, 8, 13, 9, 10, 12, 14, 11, 15, 0])

result = solver(board)

while True:
print(result)
if result.parent:
result = result.parent
else:
break


1. Don't import modules you're not using. (import itertools)
2. Don't import modules in the middle of your code. All the imports should be called at the beginning of the script (import random). This will make your code easier to read.
3. Use _ to split the name of your methods.
getdistance()      -> get_distance()
gettotaldistance() -> get_total_distance()
taxicabdistance()  -> taxi_cab_distance()
swapwithindex()    -> swap_with_index()
allpositions()     -> all_positions()
pushpositions()    -> push_positions()

1. The same rule as above goes for your variable names.
2. I'd rather stick with PyCharm suggestion of keeping the line length < 120 characters, but that's rather a matter of preference
3. Add if __name__ == '__main__' directive which will allow you you to have that code execute only when you want to run the module as a program, and not have it execute when someone just wants to import your module and call your functions themselves

Revised code:

import heapq
import numpy as np
import random

class Board:
def __init__(self, board):
self.goal_config = list(range(1, 16)) + [0]
self.board = board
self.distance_from_start = 0
self.parent = None
self.distance = self.calculate_distance()

def __repr__(self):
return ('\nBoard: \n{} \nDistance: {}\nFrom start:{}'.
format(np.matrix(self.board).reshape(4, 4), self.get_distance(), self.distance_from_start))

def __gt__(self, board2):
return self.get_total_distance() > board2.get_total_distance()

def __lt__(self, board2):
return self.get_total_distance() < board2.get_total_distance()

def calculate_distance(self):
"""
:return: Sum of taxicab distances between board and goal
"""
distance = 0
for index, tile in enumerate(self.board):
if tile is not self.goal_config[index]:
distance += self.taxi_cab_distance(index, self.goal_config.index(tile))

return distance

def get_distance(self):
return self.distance

def get_total_distance(self):
return self.distance + self.distance_from_start

def taxi_cab_distance(self, index1, index2):
y1, x1 = divmod(index1, 4)
y2, x2 = divmod(index2, 4)
return abs(x2 - x1) + abs(y2 - y1)

def swap_with_index(self, index):
"""
:swaps index and empty cell.
:return: Board object
"""
temp_board = self.board[:]
index0 = temp_board.index(0)
temp_board[index0], temp_board[index] = temp_board[index], temp_board[index0]
return Board(temp_board)

def all_positions(self):
"""
:return: List of possible boards that could be generated from instance board
"""
empty = self.board.index(0)
movable = [index for index in range(16) if
self.taxi_cab_distance(empty, index) == 1]
boards = []
for move in movable:
boards.append(self.swap_with_index(move))
random.shuffle(boards)
return boards

def solver(board):
"""
:board: Board object
:closed: processed nodes
:distances: hashtable of proc.nodes
:return: List of boards leading to solution
"""

def push_positions(board, queue, closed, distances):
"""
pushes all position of the board to priority queue
:param queue: priority queue list
:param board: Board object
"""
if board.get_distance() == 0:
return board
for childboard in board.all_positions():
childboard.parent = board
childboard.distance_from_start = board.distance_from_start + 1
if childboard.get_distance() == 0:
return childboard
try:
if distances[str(childboard.board)] > childboard.get_total_distance():
heapq.heappush(queue, childboard)
distances[
str(childboard.board)] = childboard.get_total_distance()
except KeyError:
heapq.heappush(queue, childboard)
distances[str(childboard.board)] = childboard.get_total_distance()

open, closed, distances, result = [], [], {str(board.board): 0}, None
heapq.heappush(open, board)
while open:
top = heapq.heappop(open)
result = push_positions(top, open, closed, distances)
if result:
# todo Refactor when result found
return result
distances[str(top.board)] = top.get_total_distance()
closed.append(top)

if __name__ == '__main__':
board = Board([1, 2, 3, 4, 5, 6, 7, 8, 13, 9, 10, 12, 14, 11, 15, 0])

result = solver(board)

while True:
print(result)
if result.parent:
result = result.parent
else:
break