N-puzzle program solved using A* search

Question

I coded the following program to solve the n-puzzle problem with n = 3. Are there any suggestions regarding readability and variable names?

import heapq
from random import shuffle
import math
n=3
fBoard = [1,2,3,
 4,5,6,
 7,8,0]
board = [i for i in range(9)]
shuffle(board)
print(board)
aStar()
class Board():
 def __init__(self,boardList,cost,parent):
 self._array = boardList
 self.heuristic = calcHeuristic(self._array)
 self.cost = cost
 self.totalCost = self.cost + self.heuristic
 self.parent = parent
 self.hashvalue = hash(tuple(self._array))
 def _printBoard(self):
 for var in range(len(self._array)):
 if var%3==0 and var!=0:
 print "\n",self._array[var],",",
 else:
 print self._array[var],",",
 def __hash__(self):
 return self.hashvalue
 def __eq__(self,other):
 return self._array == other._array
def aStar():
 pq = []
 cost = {}
 visited = {}
 start = Board(board,0,None)
 end = Board(fBoard,99,None)
 heapq.heappush(pq,(start.totalCost,start))
 while pq:
 tmp_tuple = heapq.heappop(pq)
 tmp_board = tmp_tuple[1]
 if tmp_board.heuristic == 0:
 end = tmp_board
 break
 index = tmp_board._array.index(0)
 x = index/3
 y = index%3
 listOfMoves = checkMove(x,y)
 for move in listOfMoves:
 moveBoard = tmp_board._array[:]
 moveIndex = move[0]*3 + move[1]
 moveBoard[index],moveBoard[moveIndex] = moveBoard[moveIndex],moveBoard[index]
 newBoard = Board(moveBoard,tmp_board.cost+1,tmp_board)
 new_cost = newBoard.totalCost
 if newBoard not in visited or new_cost < cost[newBoard]:
 cost[newBoard] = new_cost
 visited[newBoard] = 1
 newBoard.parent = tmp_board
 heapq.heappush(pq,(newBoard.totalCost,newBoard))
 var = end
 while var != start:
 print "\n"
 var._printBoard()
 var = var.parent
 print "\n"
 var._printBoard()
def manhattanDist(index,element):
 idx = fBoard.index(element)
 manhattan = 0
 fBoard_x = idx/3
 fBoard_y = idx%3
 x = index/3
 y = index%3
 manhattan += math.fabs(x-fBoard_x)
 manhattan += math.fabs(y-fBoard_y)
 return manhattan
def calcHeuristic(array):
 boardList = array
 heuristic = 0
 for var in boardList:
 x = var/3
 y = var%3
 if fBoard.index(var) != boardList.index(var):
 heuristic+=1
 heuristic+=manhattanDist(boardList.index(var),var)
 return heuristic
def checkMove(x,y):
 listOfMoves = [[x,y]]
 if(x+1<n):
 listOfMoves.append([x+1,y])
 if(x-1>=0):
 listOfMoves.append([x-1,y])
 if(y-1>=0):
 listOfMoves.append([x,y-1])
 if(y+1<n):
 listOfMoves.append([x,y+1])
 return listOfMoves

• Gareth Rees: See this question and its answer.

Answer 1

Are there any suggestions regarding readability and variable names?

You should follow PEP8, the official Python coding style guide. For example:

• Put spaces around operators. Instead of var%3==0, write as var % 3 == 0
• Put spaces after commas separating parameters. Instead of Board(fBoard,99,None), write as Board(fBoard, 99, None)
• Use snake_case for naming variables and methods instead of camelCase
• Use PascalCase for naming classes

What is an fBoard? It's not easy to guess, so that's not a good name.

Don't execute code in global scope

These lines are executed immediately when the script is imported, which is not good:

n=3
fBoard = [1,2,3,
 4,5,6,
 7,8,0]
board = [i for i in range(9)]
shuffle(board)
print(board)
aStar()

It would be better to move them into a main function, and call that function from a if __name__ == '__main__' guard, like this:

def main():
 n=3
 fBoard = [1,2,3,
 4,5,6,
 7,8,0]
 board = [i for i in range(9)]
 shuffle(board)
 print(board)
 aStar()
if __name__ == '__main__':
 main()

This will make your script more reusable, and it will help you avoid some obscure bugs that can happen by variable shadowing.

Get ready for Python 3

It's not too difficult to make this script work with Python 3 too. All it takes is adapting your print statements a little bit. In some cases it's as trivial as adding (...), for example:

print "\n"

Rewrite as:

print("\n")

When you don't want the automatic newline, for example here:

print "\n",self._array[var],",",

You can add the end='' parameter:

print("\n",self._array[var],",", end='')

• Janne Karila: The last example needs from __future__ import print_function at the top in Python 2.
• Janne Karila: For Python 3 compatibility, integer division must use //.
• Deepak: Thanks, any suggestions regarding design? use of classes and data structures?