今天是LeetCode專題第32篇，我們來看看八皇后問題的進階版——
N皇后問題。今天的文章對應LeetCode當中的51和52兩題，這兩題的題面幾乎完全一樣，都是N皇后問題，不同的是51題要求的是所有N皇后的擺放的情況，而52題只需要求所有擺放的種數。所以我們把這兩題合併在一篇文章當中分享。
N皇后問題
N皇后問題是非常經典的算法問題，也是面試當中的常客。早年許多面試官喜歡考察N皇后問題，本質上是想要通過這個問題考察候選人對於遞歸和搜索的掌握程度。遞歸和搜索可以說是算法的基礎，也是一個高階工程師必須掌握的內容。因此它非常的重要，現在雖然在面試當中出現得少了，但是它背後的算法的精髓卻一直沒有變。
我們來回顧一下N皇后的題面，在國際象棋的規則當中，皇后是最強大的。既可以橫著走，也可以豎著走，還能斜著走。如果我們要在棋盤上擺放多個皇后，只要其中兩個皇后
同行或者同列或者同對角線，那麼就認為她們的行動範圍產生了重疊，就會產生“衝突”。然而我們不希望這樣的事情發生，所以請問給定一個n*n的棋盤，要求在其中擺放n個皇后，有哪些擺放的方法？
當n=8的時候，就是大名鼎鼎的八皇后問題。我們也曾經在文章當中分享過，不熟悉或者新關注的同學可以點擊下方傳送門：
思路分析
八皇后問題已經是老生常談了，在我們探討解法之前，先來思考一個問題，用遞歸或者搜索解決的問題很多，為什麼只有N皇后問題如此經典呢？
是因為國際象棋比較流行嗎？還是因為這個問題很困難嗎？還是它的思路很巧妙嗎？由於這個問題是我自己提出的，書本上並沒有相關的答案，需要我們自己思考。我們先不公佈答案，帶著這個問題來分析一下這道題的思路。
我個人在解題的時候喜歡問問題，很多時候看似破朔迷離找不到頭緒的題目，多問幾個問題也許就能找到靈感。如果我們對數字敏感的話，很容易發現一個大問題，為什麼題目會讓我們在n*n的棋盤上擺放n個皇后呢？為什麼是n個，而不是2n個，也不是n+1個呢？
這個問題不難回答，因為題目當中規定了皇后不能同行擺放，所以每一行最多擺放一個皇后，一共有n行，那麼顯然最多隻能擺放n個皇后。但是如果我們繼續提問，既然這麼多限制條件，那為什麼一定能找到答案呢，會不會擺放n個皇后的解不存在呢？這當然是有可能的，我們很容易發現，當n=2和3的時候就沒有解法。
如果我們順著這個思路問下去，還可以挖掘出許多問題來。比如到底什麼樣的n可以使得一定有解呢？每一個n對應的解有沒有規律呢？這樣一直問下去，如果所有的問題都能解答，就說明這個問題就徹底吃透了。實際上這個問題背後是一個非常複雜的數學問題，會在之後開一篇文章單獨講解。
雖然不去深究這些問題，也一樣可以把題目做出來，但很多時候思維和能力的差距就體現在這些看似無用的思考上。
我們先把問題簡化，把解的存在性問題先放一放，既然題目要我們求，一定會給我們有解的n。而且我們也可以大概猜測得出結論，當n大於等於4的時候，N皇后問題一定有解。那麼，我們怎麼求解呢？
問題建模
我們幹想是沒有結果的，要對問題進行建模。建模這個詞很玄乎，聽起來很高端，而且在很多場景當中都會出現。比如機器學習當中，我們需要建模，還有專門的數學建模大賽，但是少有人會對建模這個詞進行解釋。
經過了一系列思考，我個人總結，所謂的建模，其實就是一個尋找和設計適應問題的解法的過程。模型就是從問題當中抽象出來的邏輯，比如N皇后擺放是問題本身，但是擺放的方法的邏輯才是模型。模型不是憑空出現的，是我們一點點構建的。這個過程有點像是搭積木，從無到有，從易到難，一點點將模型完善。
n*n的棋盤上擺放n個皇后，這個是問題本身，我們做第一層抽象。顯然，由於皇后之間不能同行也不能同列，那麼每一行和每一列只能擺放一個皇后。我們不能同時枚舉一個皇后擺放的行和列，我們優先考慮其中的行。不如做一個假設，由於皇后之間沒有差別，我們可以
假設每一行擺放的皇后是固定的。第一個皇后就擺放在第一行，第二個皇后就擺放在第二行。
進行了第一層抽象之後，問題清晰了許多，但是還是無法得出答案。所以我們還需要做第二層抽象和分析，每行固定一個皇后之後可以保證皇后之間不會同行發生衝突，但是不能保證不同列以及不同對角線。所以我們必須設計一個機制，來保證這一點。我們需要枚舉皇后所有擺放的情況，所以不能再固定皇后擺放的列，既然不能固定，但是可以記錄。由於我們已經確定了每一個皇后擺放的行，只要
記錄下它們擺放的列，就可以判斷是否會構成同列以及同對角線。到這裡，我們已經找到解法了，但是我們還可以再做第三層抽象。由於皇后已經固定了行號，我們可以用數組當中的下標代替皇后。下標0存儲的位置就是皇后0擺放的列號，0就是皇后0的行號，那麼我們用一個一維數組就存儲了皇后擺放的二維信息。
也就是說我們在遞歸的時候，只用一個數組就記錄了整個棋盤的情況，這個時候用代碼實現起來就要容易很多。
<code># code for leetcode 51
class Solution:
def dfs(self, n, queen, ret):
if len(queen) == n:
ret.append(queen[:])
return
for i in range(n):
# 如果同列
if i in queen:
continue
flag = False
# 判斷是否存在同對角線
for j, idx in enumerate(queen):
# len(queen)表示當前是第幾個皇后
if abs(len(queen) - j) == abs(idx - i):
flag = True
break
if flag:
continue
# 合法則放入i列
queen.append(i)
self.dfs(n, queen, ret)
queen.pop()
def transform(self, n, ret):
res = []
# 根據每個皇后擺放的列號還原棋盤
for arr in ret:
s = []
for i, idx in enumerate(arr):
row = ['.' for _ in range(n)]
row[idx] = 'Q'
s.append(''.join(row))
res.append(s)
return res
def solveNQueens(self, n: int) -> List[List[str]]:
ret = []
self.dfs(n, [], ret)
return self.transform(n, ret)/<code>
總結
最後，我們再回到一開始的問題，為什麼遞歸求解的問題這麼多，只有N皇后成為經典呢？
我覺得很重要的一個原因就在於這道題對應的建模過程，我們從無到有，抽絲剝繭，一點點將整個問題搭建起來，構建出了一個適配於當前問題的模型。並且經過我們的優化，這也是用遞歸實現的最佳模型。對於我們而言，把問題AC了其實並不重要，重要的是能夠掌握這個思路構建的能力，這樣以後我們就可以很方便地遷移到其他的問題場景當中，這才是學習的精髓。
吐槽一下，LeetCode把題目稍微變一下就成為一種新題的做法實在是……
今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
