N-puzzle program solved using A* search 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 &lt; 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&lt;n):
        listOfMoves.append([x+1,y])
    if(x-1&gt;=0):
        listOfMoves.append([x-1,y])
    if(y-1&gt;=0):
        listOfMoves.append([x,y-1])
    if(y+1&lt;n):
        listOfMoves.append([x,y+1])

    return listOfMoves
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='')