HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

N-puzzle program solved using A* search

Submitted by: @import:stackexchange-codereview··
0
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 listOfMoves

Solution

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

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.