- 雜談：經典演算法之八皇后問題
- 0. 引言
- 1. 題目描述
- 2. 演算法決議
- 3. 代碼實作
0. 引言
八皇后問題也算是演算法問題中一道經典的不能夠更加經典的題目了，這里，這里，我們來考察一下八皇后問題的一般形式，即N皇后問題，
1. 題目描述
八皇后問題的問題描述相信大家也都清楚，我們直接給出N皇后演算法描述如下：
在一張 N × N N \times N N×N的棋盤上，放上N個國際象棋的皇后，使得他們互相之間不會吃掉對方，請問一共有多少種不同的擺放方法，
leetcode上面對這道題也有收錄，對應其中的51題和52題，他們唯一的差別就在于是否需要列印出完整的擺放方式，
不失一般性的，這里，我們就只統計擺放方法數量而不列印出具體的擺放方式了，
2. 演算法決議
這道題的典型解法就是深度優先遍歷方法，
我們考察第i行上的每一個位置，如果該位置上可以拜訪一個皇后，就在其上擺放一個皇后，然后考察下一行中的可行擺法，知道所有的行上都擺放了一個皇后之后，我們就將總次數加一，
3. 代碼實作
給出具體的python代碼實作如下：
class Solution:
def totalNQueens(self, n: int) -> int:
ans = 0
cache = []
def dfs(i):
nonlocal ans, cache
if i >= n:
ans += 1
return
for j in range(n):
if any(c == j or i-r == abs(c-j) for r, c in cache):
continue
cache.append((i, j))
dfs(i+1)
cache.pop()
return
dfs(0)
return ans
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/238066.html
標籤：python
上一篇：淘寶商品資訊爬取
下一篇：Python學習：Pandas庫