八數碼問題也稱為九宮問題。在3×3的棋盤，擺有八個棋子，每個棋子上標有1至8的某一數字，不同棋子上標的數字不相同。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態和一個目標狀態，找出一種從初始狀態轉變成目標狀態的移動棋子步數最少的移動步驟。

使用算法：廣度搜索算法

python

import numpy as npclass State: def __init__(self, state, directionFlag=None, parent=None): self.state = state self.direction = [’up’, ’down’, ’right’, ’left’] if directionFlag: self.direction.remove(directionFlag) self.parent = parent self.symbol = ’ ’ def getDirection(self): return self.direction def showInfo(self): for i in range(3): for j in range(3): print(self.state[i, j], end=’ ’) print('n') print(’->n’) return def getEmptyPos(self): postion = np.where(self.state == self.symbol) return postion def generateSubStates(self): if not self.direction: return [] subStates = [] boarder = len(self.state) - 1 row, col = self.getEmptyPos() if ’left’ in self.direction and col > 0: s = self.state.copy() temp = s.copy() s[row, col] = s[row, col-1] s[row, col-1] = temp[row, col] news = State(s, directionFlag=’right’, parent=self) subStates.append(news) if ’up’ in self.direction and row > 0: s = self.state.copy() temp = s.copy() s[row, col] = s[row-1, col] s[row-1, col] = temp[row, col] news = State(s, directionFlag=’down’, parent=self) subStates.append(news) if ’down’ in self.direction and row < boarder: s = self.state.copy() temp = s.copy() s[row, col] = s[row+1, col] s[row+1, col] = temp[row, col] news = State(s, directionFlag=’up’, parent=self) subStates.append(news) if self.direction.count(’right’) and col < boarder: s = self.state.copy() temp = s.copy() s[row, col] = s[row, col+1] s[row, col+1] = temp[row, col] news = State(s, directionFlag=’left’, parent=self) subStates.append(news) return subStates def solve(self): openTable = [] closeTable = [] openTable.append(self) steps = 1 while len(openTable) > 0: n = openTable.pop(0) closeTable.append(n) subStates = n.generateSubStates() path = [] for s in subStates: if (s.state == s.answer).all(): while s.parent and s.parent != originState: path.append(s.parent) s = s.parent path.reverse() return path, steps+1 openTable.extend(subStates) steps += 1 else: return None, Noneif __name__ == ’__main__’: symbolOfEmpty = ’ ’ State.symbol = symbolOfEmpty originState = State(np.array([[2, 8, 3], [1, 6 , 4], [7, symbolOfEmpty, 5]])) State.answer = np.array([[1, 2, 3], [8, State.symbol, 4], [7, 6, 5]]) s1 = State(state=originState.state) path, steps = s1.solve() if path: for node in path: node.showInfo() print(State.answer) print('Total steps is %d' % steps)

以上就是python廣度搜索解決八數碼難題的詳細內容，更多關于python廣度搜索八數碼的資料請關注好吧啦網其它相關文章！