0

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.

13
  • Somehow your queue is getting a list object added to it, rather than a Klotski instance. 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_objective is 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.) Commented Apr 11, 2023 at 21:18
  • Hi, thx for answering one of my questions. Also I have updated the post to include the omitted code that I mentioned, but it is kinda long and may hurt someone who knows how to optimize code. I'd be very grateful if you could take a look at it. <3 Commented Apr 11, 2023 at 23:14
  • " But "is_objective", as far as I know, is not an attribute, but instead a class method." Methods are attributes. A method is a kind of attribute. Commented Apr 11, 2023 at 23:16
  • In any case, the problem is that where you believe you have a Klotski instance you actually have a list instance. Commented Apr 11, 2023 at 23:17
  • 1
    Listen, you just dumped your whole code here, and provided a snippet of the error message (which doesn't include the stack trace, which would tell us exactly where this is happening). Please put a little bit of effort in providing a minimal reproducible example. Commented Apr 11, 2023 at 23:22

1 Answer 1

0

here!

When cheking the positions you append the items returned by . children(), which are the return of the movement functions, and move_down returns you the state.board - which is a list.

Probably you want these items returned by children to be instances of the board - so it should return state, not state.board. (state would have the method that is missing).

All in all, just change the last line here (and in other omitted move functions):

    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
           ...
        elif state.board[row][col]==4:                       # piece type 2x2
           ...
        return state    # <- changed this from `return state.board`

Also, do not ever use mutable objects as default arguments when declaring a function or method - change your __init__ to:


    def __init__(self, board, history=None):

        history = history or []  # This `[]` is inside the function and is a new list each time the method is executed. 
        #Initialize the board as a matrix
        self.board = deepcopy(board)

        #Append the move history to an array
        self.history = history + [self.board] 

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.