0

在我的 AI 课上，我们被分配为8 个正方形拼图编写求解器。我的程序适用于实现解决方案（最多 9 个）的情况，但远不止这些会导致无限递归。我正在存储以前的状态以防止重复相同的 2 个状态，所以我不确定出了什么问题。你们中的一个可以帮助我吗？谢谢。

class Queue:
    def __init__(self):
        self.content=[]
    def put(self, x):
        self.content.append(x)
    def empty(self):
        return len(self.content)==0
    def get(self):
        return self.content.pop(0)

class Board:
    def __init__(self, b, m=[]):
        self.board=b
        self.moves=m
        
    def clone(self):
        asdf=Board(list(self.board),list(self.moves))
        return asdf
    
    def swap(self, a, b):
        temp=self.board[b]
        self.board[b]=self.board[a]
        self.board[a]=temp
        
    def findblank(self):
        for i in range(9):
            if(self.board[i]==0):
                return i
        return 9
    
    def up(self):
        asdf=self.clone()
        a=asdf.findblank()
        b=a-3
        if a>=3:
            asdf.swap(a, b)
            asdf.moves.append("u")
            return asdf
        else:
            return self.clone()

    def down(self):
        asdf=self.clone()
        a=asdf.findblank()
        b=a+3
        if a<6:
            asdf.swap(a, b)
            asdf.moves.append("d")
            return asdf
        else:
            return self.clone()

    def left(self):
        asdf=self.clone()
        a=asdf.findblank()
        b=a-1
        if b%3 != 2:
            asdf.swap(a, b)
            asdf.moves.append("l")
            return asdf
        return self.clone()

    def right(self):
        asdf=self.clone()
        a=asdf.findblank()
        b=a+1
        if b%3 != 0:
            asdf.swap(a, b)
            asdf.moves.append("r")
            return asdf
        return self.clone()

    def check(self):
        solutions=[[0,1,2,3,4,5,6,7,8],[1,2,3,8,0,4,7,6,5],[1,2,3,4,5,6,7,8,0]]
        if self.board in solutions:
            return True
        return False

def bfs(q,seen=[]):
    if(q.empty()):
        print("No solution")
        print("Iterations:")
        print(len(seen))
        return Board([0,0,0,0,0,0,0,0,0])
    
    pos=q.get()
    if pos.check():
        print(len(seen))
        return pos
    
    seen.append(pos.board)
    
    if len(pos.moves)==0:
        lastmove="no."
    else:
        lastmove=pos.moves[-1]
          
    if (pos.up().board!=pos.board and lastmove!='d' and (pos.up().board not in seen)):
        q.put(pos.up())
              
    if (pos.down().board!=pos.board and lastmove!='u' and (pos.down().board not in seen)):
        q.put(pos.down())
              
    if (pos.left().board!=pos.board and lastmove!='r' and (pos.left().board not in seen)):
        q.put(pos.left())
              
    if (pos.right().board!=pos.board and lastmove!='l' and (pos.right().board not in seen)):
        q.put(pos.right())
        
    return bfs(q,seen)

def solve(board):
    q=Queue()
    q.put(board)
    return bfs(q)

board=Board([0,7,8,3,6,2,4,5,1])

solved=solve(board)
print(board.board[0],board.board[1],board.board[2])
print(board.board[3],board.board[4],board.board[5])
print(board.board[6],board.board[7],board.board[8])
print("to")
print(solved.board[0],solved.board[1],solved.board[2])
print(solved.board[3],solved.board[4],solved.board[5])
print(solved.board[6],solved.board[7],solved.board[8])

print("Number of Steps:")
print(len(solved.moves))

print("Steps:")
print(solved.moves)

已解决：代码没有问题；Python 的最大调用堆栈大小太小了。我让它迭代，它工作正常。核心问题是该程序具有指数时间复杂度，并且使其迭代（使用“while True:”）可以解决该问题。

4

0 回答 0