I have written a class that creates a board for a Klotski game and I want to use breadth-first search to solve the given problem. Here is a bit of my code:
EDIT and DISCLAIMER: I added all the relevant class methods and functions in the code, although it is not optimized and I tried to make it shorter...
from copy import deepcopy
class Klotski:
def __init__(self, board, history=[]):
#Initialize the board as a matrix
self.board = deepcopy(board)
#Append the move history to an array
self.history = [] + history + [self.board]
def children(self): # returns the possible moves
moves = [self.try_move_down] # list of move functions
children = []
for row in range(len(self.board)): # will try to move every piece in every direction and return the possible moves
for col in range(len(self.board[row])):
for func in moves:
child = func(row, col)
if child:
children.append(child)
return children
def is_objective(self): # checks if the puzzle is complete
if self.board[3][1]==4 and self.board[4][2]==4:
return True
return False
In the moves list there are 4 different directions, but they are structured very similarly. I will include only 1 of the relevant moves methods:
def try_move_down(self, row, col): # will check the current piece to see if it can be moved downwards
if row<4:
if self.board[row][col]==1: # if the piece type is 1x1
if self.board[row+1][col]==0:
return self.move_down(row, col)
else:
return None
elif self.board[row][col]==4: # if the piece type is 2x2
if (col>0 and self.board[row][col-1]==4) or (row>0 and self.board[row-1][col]==4):
return None
if self.board[row+2][col]==0 and self.board[row+2][col+1]==0:
return self.move_down(row, col)
else:
return None
def move_down(self, row, col): # will move the current piece upwards
state=Klotski(self.board, self.move_history)
if state.board[row][col]==1: # piece type 1x1
state.board[row][col]=0
state.board[row+1][col]=1
elif state.board[row][col]==4: # piece type 2x2
state.board[row+2][col]=4
state.board[row+2][col+1]=4
state.board[row][col]=0
state.board[row][col+1]=0
return state.board
The problem arose when I created this function:
def bfs(problem:Klotski): # problem(Klotski) - the initial state
queue = [problem]
visited = set() # to not visit the same state twice
while queue:
current = queue.pop(0)
visited.add(str(current))
if current.is_objective(): # found the best solution
return current
child_list=current.children()
for child in child_list:
if str(child) not in visited: # avoid visiting the same state twice
queue.append(child)
return None
When I run this cycle, which should print the number of steps it took to solve the puzzle, as well as the board state at every step:
def print_sequence(state):
print("Steps:", len(state.history) - 1) # prints the sequence of states
for move in state.history:
print(move)
print()
print_sequence(bfs(Klotski([[1,4,4,1], [1,4,4,1], [1,1,1,1], [1,1,1,1], [1,0,0,1]])))
I get on my terminal this error message:
Traceback (most recent call last):
File "c:\Users\...\Code.py", line 229, in <module>
print_sequence(bfs(Klotski([[1,4,4,1], [1,4,4,1], [1,1,1,1], [1,1,1,1], [1,0,0,1]])))
File "c:\Users\...\Code.py", line 216, in bfs
if current.is_objective(): # found the best solution
AttributeError: 'list' object has no attribute 'is_objective'
What should I do to fix my problem?...
P.S.:Sorry for the long post and I'm a beginner. I tried to make the post more readable and shorter in size (even though it's still basically a massive code dump...). Also if there's a shorter way to recreate the problem feel free to tell me.
Klotskiinstance. I don't see this happening anywhere in the code you posted, so it must be in one of the move methods that you omitted. (Your colleague's change completely broke the program.current.is_objectiveis always true (since this doesn't actually call the method), so the program exited before it got to the point where the list got added to the queue.)Klotskiinstance you actually have alistinstance.