前幾天看知乎的時(shí)候，在 Scala 相關(guān)的話題下面看到一篇回答 《一行scala能實(shí)現(xiàn)怎樣喪心病狂的代碼？》https://www.zhihu.com/question/51038841/answer/123883134，其中提到了實(shí)現(xiàn)全排列和八皇后的簡(jiǎn)潔寫法：

八皇后

全排列

感覺很有意思，對(duì)于我來說是些新穎解法。其中全排列是遞歸的函數(shù)式寫法，而八皇后則是利用 Scala 的 API 基于全排列進(jìn)行解決的。

很自然的，就想起了力扣上有這么兩道題：46. 全排列 和 51. N 皇后 ，目前的官方題解都基本是靠回溯的方法來解決的。所以用遞歸函數(shù)式的方法在力扣上進(jìn)行了這兩道題的解答嘗試，專門學(xué)習(xí)了一下，下面也分享一下相關(guān)的經(jīng)歷。

1 第一次嘗試：直接修改代碼

根據(jù)上面知乎看到的“一行代碼”，我們針對(duì)力扣的題目要求進(jìn)行修改。題目大致如下：

46. 全排列

給定一個(gè)不含重復(fù)數(shù)字的數(shù)組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

51. N 皇后

按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

n 皇后問題 研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個(gè)整數(shù) n ，返回所有不同的 n 皇后問題 的解決方案。

每一種解法包含一個(gè)不同的 n 皇后問題 的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

來源：力扣（LeetCode） 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

修改后提交的代碼如下：

全排列

N 皇后

可以看到 N 皇后的執(zhí)行時(shí)間較長(zhǎng)，有待優(yōu)化。我們最后會(huì)使用遞歸方式解決 N 皇后問題，暫且不著急，我們先學(xué)習(xí)一下遞歸的函數(shù)式全排列實(shí)現(xiàn)，并且解析一下 N 皇后問題的基本思路，然后利用學(xué)到的知識(shí)，來重寫 N 皇后問題的實(shí)現(xiàn)。

2 遞歸的解題思路

2.1 全排列：刪除法

根據(jù)《Haskell 函數(shù)式編程入門（第 2 版）第 1 卷》6.4.1 排列問題中的講解，我們可以看到，上面的全排列代碼其實(shí)就是按照如下思路求解的：

在全排列的過程中，所有在列表中的元素必須開頭至少一次。然后，當(dāng)某一元素 x 開頭時(shí)，只要對(duì)除這一元素的列表進(jìn)行排列，就得到了以 x 開頭的排列，那么若生成每一個(gè)元素開頭的排列，就得到了整個(gè)列表的全部排列。

可以看出 for (x <- xs; rs <- perm(xs diff List(x))) yield x +: rs 這一步，對(duì)應(yīng)的含義就是：

1. 對(duì)于當(dāng)前需要求全排列的列表 xs 中的每一個(gè)元素 x（x <- xs）

2. 獲取到 xs 排除掉 x 的列表（xs diff List(x)），遞歸求它的全排列（perm(xs diff List(x)）

3. 然后對(duì)于遞歸求得的全排列的每一個(gè)排列 List rs，我們把 x 插入到它的頭部（yield x +: rs）

4. 這樣我們就得到了 xs 的全排列

對(duì)應(yīng)的 Haskell 代碼如下：

可以看到，思路是相當(dāng)簡(jiǎn)潔的。

2.2 N 皇后：基于全排列

N 皇后的代碼最后的 .map(_.map {("." * n).updated(_, 'Q')}.toList) 其實(shí)就是在把標(biāo)記皇后位置的索引 序列轉(zhuǎn)換為相應(yīng)字符串，這里就不多講了。我們主要關(guān)注前面的核心代碼。

根據(jù)《Haskell 函數(shù)式編程入門（第 2 版）第 1 卷》6.5 八皇后問題中的講解，我們可以看出，核心代碼部分的思路就是：

1. 生成 0 到 n 的全排列（(0 until n).permutations）

2. 篩選出不在對(duì)角線上的即可（.filter(_.zipWithIndex.combinations(2) forall {case Seq((a, b), (c, d)) => a + b != c + d && a + d != b + c })）

對(duì)應(yīng)的 Haskell 代碼如下：

需要注意這里索引都是從 1 開始的。

其中 noSameDiag 對(duì)應(yīng)篩選出不在對(duì)角線上的函數(shù)，zip [1..] xs 即對(duì)應(yīng) Scala 的 zipWithIndex，而 abs (i1 - i) /= abs (p1 - p) 在將絕對(duì)值拆開、減法移到等號(hào)對(duì)面后就等效于 Scala 代碼中的 case Seq((p1, i1), (p2, i2)) => p1 + i1 != p2 + i2 && p1 + i2 != i1 + p2（變量名針對(duì)性的修改了一下）。

而 permutation 則為插入法實(shí)現(xiàn)的全排列（后續(xù)我們會(huì)分析一下這另一種思路的全排列實(shí)現(xiàn)），其中插入過程的實(shí)現(xiàn)是 insert 函數(shù)；而我們的 Scala 代碼是直接使用了 API 提供的方法。（換句話說，力扣 46. 全排列我們也有一個(gè)一行的解法：nums.toList.permutations.toList，笑）

如果使用 Haskell 代碼的思路，自行實(shí)現(xiàn)插入法全排列的話，等效的 Scala 代碼如下：

因?yàn)樗悸坊疽恢?，耗時(shí)依舊較長(zhǎng)，文章最后我們會(huì)給出一個(gè)較快的解法。

3 全排列的另一種思路：插入法

在閱讀 N 皇后的 Haskell 代碼時(shí)，我們可以發(fā)現(xiàn)，全排列還有一種解法：插入法

其實(shí)在《Haskell 函數(shù)式編程入門（第 2 版）第 1 卷》6.4.1 排列問題中的講解中有這種思路的介紹：

第一種方法采用的是遞歸地插入的思想?，F(xiàn)在，假設(shè)我們要得到 [1,2,3] 的全部排列并且已經(jīng)求出列表 [1,2] 的全排列，即 [[1,2],[2,1]]，如何生成 [1,2,3] 的全排列呢？只需要分別將 3 插入到 [1,2] 與 [2,1] 的中間和兩邊的空隙里就可以了。兩個(gè)數(shù)，有三個(gè)位置可以插入，所以最后的全排列是 6 種：[3,1,2], [1,3,2], [1,2,3], [3,2,1], [2,3,1], [2,1,3]。

對(duì)應(yīng) Haskell 代碼其實(shí)就是 N 皇后中我們看到的 permutation 方法。

那么我們是否可以將這種思路使用 Scala 實(shí)現(xiàn)呢？顯然也是可以的，代碼如下

我們可以看出，模式匹配在函數(shù)式編程中的靈活應(yīng)用可以大大減輕這些思路的實(shí)現(xiàn)。（不得不吐槽一下，截至 Java 18，現(xiàn)在還沒有這種程度的模式匹配功能?。?br>

4 N 皇后降低耗時(shí)的嘗試：基于遞歸

我們可以嘗試使用遞歸的思路降低 N 皇后的耗時(shí)：

同樣的思路的另一種寫法：

可以看出相比之前上千的耗時(shí)，效果比較顯著。主要的思路就是使用 nQueens 的遞歸，一行一行的填入不沖突的皇后。這樣計(jì)算到第 k 行的填充索引隊(duì)列就是對(duì)應(yīng) nQueens(k) 的結(jié)果。

5 總結(jié)

通過上述方法，我們可以看出，我們可以使用遞歸的函數(shù)式調(diào)用的方法，來避免命令式寫法中顯式書寫回溯邏輯，但是實(shí)現(xiàn)的方式會(huì)決定耗時(shí)的多少。這里我們分享了兩種全排列的遞歸函數(shù)式實(shí)現(xiàn)方式：插入法和刪除法；而 N 皇后問題，我們也分享了兩種實(shí)現(xiàn)方式：基于全排列和基于遞歸。

具體的 Scala 實(shí)現(xiàn)差異和底層原理，日后有時(shí)間我再深入研究一下分享分享。目前還是才疏學(xué)淺，先提供這些書寫方式供大家參考啦~