patternpythonMinor
N-puzzle program solved using A* search
Viewed 0 times
searchprogramusingsolvedpuzzle
Problem
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 =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 listOfMovesSolution
Are there any suggestions regarding readability and variable names?
You should follow PEP8, the official Python coding style guide.
For example:
What is an
Don't execute code in global scope
These lines are executed immediately when the script is imported,
which is not good:
It would be better to move them into a
and call that function from a
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
In some cases it's as trivial as adding
Rewrite as:
When you don't want the automatic newline, for example here:
You can add the
You should follow PEP8, the official Python coding style guide.
For example:
- Put spaces around operators. Instead of
var%3==0, write asvar % 3 == 0
- Put spaces after commas separating parameters. Instead of
Board(fBoard,99,None), write asBoard(fBoard, 99, None)
- Use
snake_casefor naming variables and methods instead ofcamelCase
- Use
PascalCasefor 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='')Code Snippets
n=3
fBoard = [1,2,3,
4,5,6,
7,8,0]
board = [i for i in range(9)]
shuffle(board)
print(board)
aStar()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()print("\n")print "\n",self._array[var],",",print("\n",self._array[var],",", end='')Context
StackExchange Code Review Q#80000, answer score: 3
Revisions (0)
No revisions yet.