在我的 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:”)可以解决该问题。