八數(shù)碼問題也稱為九宮問題。在3×3的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始狀態(tài)轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)棋子步數(shù)最少的移動(dòng)步驟。

使用算法：廣度搜索算法

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廣度搜索解決八數(shù)碼難題的詳細(xì)內(nèi)容，更多關(guān)于python廣度搜索八數(shù)碼的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！