資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式檢查N皇后問題是否有解
假設我們有一個二進位制矩陣，其中0表示空單元格，1表示該單元格上的棋子皇后。我們需要檢查是否可以填充此棋盤並獲得有效的n皇后解。眾所周知，n皇后問題要求在n×n棋盤上放置n個皇后，使得任何兩個皇后都不能相互攻擊。
因此，如果輸入類似於
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
則輸出將為True，因為其中一個解類似於-
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
為了解決這個問題，我們將遵循以下步驟-
定義一個函式isSafe()。它將接收棋盤、i、j作為引數
對於r從0到棋盤大小，執行
如果r不等於i且board[r, j]等於1，則
返回False
r := i + 1, c := j + 1
當r < 棋盤行數且c < 棋盤列數時，執行
如果board[r, c]等於1，則
返回False
r := r + 1, c := c + 1
r:= i + 1, c := j - 1
當r < 棋盤行數且c >= 0時，執行
如果board[r, c]等於1，則
返回False
r := r + 1, c := c - 1
r := i - 1, c := j + 1
當r >= 0且c < 棋盤列數時，執行
如果board[r, c]等於1，則
返回False
r := r - 1, c := c + 1
r := i - 1, c := j - 1
當r >= 0且c >= 0時，執行
如果board[r, c]等於1，則
返回False
r := r - 1, c := c - 1
返回True
從主方法執行以下操作-
r := 0, c := 0
stack := 新棧
當r < 棋盤行數時，執行
如果board[r]中存在1，則
r := r + 1
進入下一輪迭代
否則，
found := False
當c < 棋盤列數時，執行
如果isSafe(board, r, c)為真，則
board[r, c] := 1
將[r, c]插入棧中
found := True
退出迴圈
c := c + 1
如果found為真，則
c := 0, r := r + 1
否則，
如果棧為空，則
返回False
m := 從棧中刪除頂部元素
r := m[0], c := m[1] + 1
board[r, c - 1] := 0
返回True
示例
讓我們看看以下實現以更好地理解-
class Solution: def solve(self, board): def isSafe(board, i, j): for r in range(len(board)): if r != i and board[r][j] == 1: return False r, c = i + 1, j + 1 while r < len(board) and c < len(board[0]): if board[r][c] == 1: return False r += 1 c += 1 r, c = i + 1, j - 1 while r < len(board) and c >= 0: if board[r][c] == 1: return False r += 1 c -= 1 r, c = i - 1, j + 1 while r >= 0 and c < len(board[0]): if board[r][c] == 1: return False r -= 1 c += 1 r, c = i - 1, j - 1 while r >= 0 and c >= 0: if board[r][c] == 1: return False r -= 1 c -= 1 return True r = c = 0 stack = [] while r < len(board): if 1 in board[r]: r += 1 continue else: found = False while c < len(board[0]): if isSafe(board, r, c): board[r][c] = 1 stack.append([r, c]) found = True break c += 1 if found: c = 0 r += 1 else: if not stack: return False m = stack.pop() r, c = m[0], m[1] + 1 board[r][c - 1] = 0 return True ob = Solution() matrix = [ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0] ] print(ob.solve(matrix))
輸入
[ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0] ]
輸出
True
181 次檢視
