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