腳本之家
你與百萬開發(fā)者在一起
“還記得八皇后的解法嗎？”
“上個世紀的事情，不記得了?！?br>“…… 現(xiàn)在回憶一下？”
“開會，回頭說?！?br>“ fuck u ”
“ u shit ”
我有一個C++基友，這么稱呼是因為他入行時用的是C++。雖然在游走于騰訊、金山、阿里之后，如今已經(jīng)精通十八般武藝了，但說起來還是C++的標簽最刺眼。
當你有一個C++基友時，QQ里的日常，難免就會碰到上面那種聊天記錄了。
八皇后是一個古老的經(jīng)典問題：如何在一張國際象棋的棋盤上，擺放8個皇后，使其任意兩個皇后互相不受攻擊。
該問題由一位德國國際象棋排局家 Max Bezzel 于 1848年提出。嚴格來說，那個年代，還沒有“德國”這個國家，彼時稱作“普魯士”。
1850年，Franz Nauck 給出了第一個解，并將其擴展成了“ n皇后 ”問題，即在一張 n x n 的棋盤上，如何擺放 n 個皇后，使其兩兩互不攻擊。
歷史上，八皇后問題曾驚動過“數(shù)學王子”高斯(Gauss)，而且正是上面這個 Franz Nauck 寫信找高斯請教的。
在那天被基友問到時，我并非真的不記得了，而是我壓根就沒有做過。但我第一次遇見這個問題時，確實是在上個世紀，那是在小學微機教室里，參加市級計算機奧林匹克小學組競賽的培訓課上。
我還記得初次看到這個問題的第一反應——怎么可能擺8個！要知道我初學國際象棋時，經(jīng)常為了簡化局面，早早地就伺機兌掉皇后，因為皇后的威力實在是溢出了我童年的腦袋。一個皇后感覺就可以 hold 住全場了，怎么還可以擺8個互不干擾的呢？這肯定無解。
所以說，童言無忌這個說法，是有必要的。
一晃好多年。如今基友問過來了，我琢磨著是該補上這份跨世紀的作業(yè)了。
給老爸撥了個電話——
“喂，爸，家里的國際象棋放哪了？”
“…… 壓箱底了吧，得找找。怎么突然問這，你要研究西西里防御？”
“我現(xiàn)在開局都不走 e4 了，要研究也是后翼棄兵?！?br>“別特么瞎扯，給你根桿子你就爬啊，快說，有什么屁事？”
“我要研究八皇后問題?！?br>“講中文！”
“我有個問題想研究一下，要在國際象棋棋盤上擺放八個皇后，并且互相不受攻擊，求擺法?！?br>“哦，這樣啊…… 那你要國際象棋干嘛？”
“我想在國際象棋上試著擺擺啊?！?br>“國際象棋沒有八個皇后，你要國際象棋干嘛？”
“呃…… 那我可以拿八個兵當皇后做試驗?！?br>“那你直接畫個棋盤擺八個硬幣不是一回事？非要用國際象棋？脫褲子放屁，多此一舉！”
“…… ……”
“老子懶得翻箱子跟你找了，你干脆去買四副國際象棋，然后就有八個皇后了。還有事嗎？”
“沒…… 沒了，爸。”
“早點休息，多喝水，別熬夜。天氣冷了，注意加衣服……”
“好，好好?！?/p>
—— 對方掛斷，通話結束。
我默默地打開了淘寶，搜索“國際象棋”，準備買 4 副……
轉(zhuǎn)念一想，還是算了，自己畫吧。
轉(zhuǎn)念二想，懶得畫了，就在腦子里擺擺看吧。
首先，做點分析工作。
雖然還不知道最終的答案長什么樣，有多少個，但利用國際象棋的規(guī)則，可以知道的是，最終8個皇后的分布必定是：
每行有且只有1個，每列有且只有1個。
因為如果有某一行（或列）空置的話，則必然導致另有一行（或列）存在2個皇后。
顯而易見的結果背后，有一個數(shù)學概念叫做“抽屜原則”。
借助這個“抽屜”，接下來要做的就是一行一行地找出8個位置。 當然，按一列一列來做也可以，但在處理圖形圖像等信息時，優(yōu)先水平方向似乎更符合人的思維慣性，據(jù)說這是因為人的兩只眼睛是水平的。
（跑題了……）
心算8皇后感覺有點累，我打算簡化問題。
從2皇后開始，不過2皇后無解得太昭然若揭了。
換成3皇后，無解得也是一目了然。
進而思考4皇后的情況（在4X4的棋盤上放4個皇后）。
于是，有點思考的空間了。
一開始，棋盤是空的，第1個皇后可以任意放置，但為了思考方便，最好是按照秩序來嘗試，于是先將第1個皇后放置在棋盤第1行第1列格子里。
BTW，如果你覺得圖中的皇后圖標長得很像 ROLEX 的 Logo，是因為我用的就是 ROLEX 的 Logo 。 畢竟，他們長得實在是太像了。
第1行已經(jīng)有了皇后，下一步是尋找第2行皇后的位置。在這之前，需要計算出第2行此時未被第1個皇后攻擊的棋格分布。
上圖中呈現(xiàn)的是整個棋盤的狀態(tài)，但此時關注的重點在第2行。接下來，將第2個皇后放置于第2行第3列棋格中。
現(xiàn)在，第1行和第2行都有皇后了，重新計算棋盤狀態(tài)，以尋找第3行的皇后位置。
經(jīng)過計算，第3行的所有棋格已經(jīng)全部處于第1個和第2個皇后的聯(lián)合攻擊范圍內(nèi)了，雖然第4行還有空位，但已經(jīng)無關緊要，當前嘗試可以宣告 Game Over 了。
換句話說，剛才的第2個皇后位置不對。
調(diào)整一下，將第2個皇后從第3列挪到第4列再試試。
調(diào)整之后，繼續(xù)更新棋盤狀態(tài)。
此時，第3行有一個可用的空位，于是將第3個皇后放在這個棋格中。
然后再次更新棋盤狀態(tài)。
Oops！又遇到了類似的情況，第4行已經(jīng)沒有棋格可以用了，所以，剛才的第3個皇后位置不對。
但第3行只有一個空位可以用，而這唯一的一個空位又是錯誤的，這說明，問題還是出在第2個皇后的位置上。
再進一步回溯分析，可以發(fā)現(xiàn)，第2行可用的棋格已經(jīng)都嘗試過了，然而都不對。
所以，問題其實出在第1個皇后的位置上。也就是說，第一步將皇后放置于第1行第1列的擺法就錯了。
知錯就改，善莫大焉。將第1個皇后挪到第1行第2列，重頭再來。
繼續(xù)，更新棋盤狀態(tài)。
根據(jù)上圖，將第2個皇后置于第2行第4列。
繼續(xù)，更新棋盤狀態(tài)。
看上去不錯，接著，將第3個皇后置于第3行第1列。
繼續(xù)，更新棋盤狀態(tài)。
咦，似乎成了。
BINGO！4皇后的第一個解，找到了。
現(xiàn)在，回顧上面的整個過程，做點抽象，引入一點計算機的思維，就可以得出解題流程了。
步驟清楚了，現(xiàn)在需要思考的就是過程中很關鍵的一步——根據(jù)已放置的皇后計算下一行棋格狀態(tài)的邏輯實現(xiàn)。
這里需要回到國際象棋的規(guī)則本身了。
一個皇后在棋盤上的攻擊范圍如下圖所示：
對這個圖做點數(shù)學上的抽象分析：棋盤本身是一個標準的坐標平面，每個棋格都有著很明顯的坐標位置。
所以，上圖可以轉(zhuǎn)換成下面的模型：
受皇后攻擊的點，按照和皇后（Q點）的相對位置，可以分成4類： -
橫向（A1）
縱向（A2）
正斜（A3）
反斜（A4）
橫向攻擊其實不用考慮，因為解題的思路本身就是按行來推進的，先天就過濾掉橫向攻擊點了。
縱向攻擊很容易判斷，Q點 和 A2點 的 x坐標 相等，就處于攻擊范圍內(nèi)。
不那么直觀的是兩條斜線的情況，需要算一下。
將正斜線攻擊（A3類點）和反斜線攻擊（A4類點）的坐標轉(zhuǎn)換一下，表示成基于Q點的偏移——
Q：（ x0, y0 ）
正斜線 A3：（ x0 + m, y0 + m ）
反斜線 A4：（ x0 - m, y0 + m ）
通過觀察不難得出規(guī)律——
正斜線上的點： (x0 + m) – x0 = (y0 + m) – y0 即：A3點的橫坐標值 - Q點的橫坐標值 = A3點的縱坐標值 – Q點的縱坐標值
反斜線上的點： x0 + y0 = (x0 – m) + (y0 + m) 即：Q點橫坐標值 + Q點縱坐標值 = A4點橫坐標值 + A4點縱坐標值
自此，通過皇后所在的棋格判斷棋盤上另一處方格是否處于被攻擊狀態(tài)的邏輯就全部搞清楚了。
流程和方法都有了，是時候?qū)懘a實現(xiàn)具體程序了。
用什么語言來做這事呢？
QBasic，C，C#，Java，Python，Lua，JavaScript，PHP， ……
我在腦袋里慢慢遍歷著我所精通的20門語言，俗話說藝不壓身，但俗話卻沒說選擇困難癥，哎……
（以上這段純屬虛構）
最終，我決定用最近的新歡—— Go 語言來寫這個程序。
延續(xù)之前的思路，依然將重心放到4皇后的情況，直譯上面的分析過程，然后代碼差不多長這樣：
// 4皇后
package main
import (
'fmt'
)
func main() {
// 定義4個皇后，初始化坐標為[-1,-1]，即未放置于棋格中。
var (
queen1 = [2]int{-1, -1}
queen2 = [2]int{-1, -1}
queen3 = [2]int{-1, -1}
queen4 = [2]int{-1, -1}
)
// 放置第1個皇后
for i := 0; i < 4; i++ { // 遍歷棋盤上的第一行方格(rank1)
queen1[0] = i
queen1[1] = 0
// 更新第2行棋格狀態(tài)(此時已放置1個皇后)
rank2 := render(queen1)
// 放置第2個皇后
for i := 0; i < 4; i++ {
if !rank2[i] {
queen2[0] = i
queen2[1] = 1
// 更新第3行棋格狀態(tài)(此時已放置2個皇后)
rank3 := render(queen1, queen2)
// 放置第3個皇后
for i := 0; i < 4; i++ {
if !rank3[i] {
queen3[0] = i
queen3[1] = 2
// 更新第4行棋格狀態(tài)(此時已放置3個皇后)
rank4 := render(queen1, queen2, queen3)
// 放置第4個皇后
for i := 0; i < 4; i++ {
if !rank4[i] {
queen4[0] = i
queen4[1] = 3
// 到此，4個皇后均成功置于棋盤中
fmt.Println('solution:', queen1, queen2, queen3, queen4)
}
}
}
}
}
}
}
}
// 根據(jù)已放置的皇后，更新下一行棋格的狀態(tài)
// 返回一個含4個bool類型元素的數(shù)組，true表示受攻擊的，false表示未受攻擊。
func render(queens ...[2]int) [4]bool {
// 國際象棋棋盤中的一行，在英文中叫做：rank
var rank [4]bool
// 獲取已放置的皇后的數(shù)量，可以得到下一行的索引
y := len(queens)
// 遍歷下一行的棋格
for x := 0; x < 4; x++ {
for _, queen := range queens {
// 通過已放置的皇后的棋格坐標來判斷攻擊范圍
if x-queen[0] == y-queen[1] || // 正斜攻擊
x == queen[0] || // 縱向攻擊
x+y == queen[0]+queen[1] { // 反斜攻擊
rank[x] = true
// 一旦判斷出該棋格受到攻擊，則不用再計算后面的皇后對其影響
break
}
}
}
return rank
}
運行后結果如下：
共2種解，并分別給出了每種解法的4皇后的坐標分布。
說明一下：這里我用到一個包含兩整型元素的數(shù)組來表示皇后的坐標，每一個中括號里面的第1個數(shù)字表示 x軸 坐標（對應棋盤上的列），第2個數(shù)字表示 y軸 坐標（對應棋盤上的行）。
現(xiàn)在，4皇后已經(jīng)解決了，那8皇后呢？
很簡單，我只需要將 main 函數(shù)里面的 for 循環(huán)再寫4套，就搞定了，復制粘貼可是基本功啊。
(開個玩笑~)
雖然照著上面的代碼，寫8套循環(huán)也確實可以得到正確的結果，但應該沒有人有勇氣公開地這么干吧。 所以，上面的代碼充其量只能算是個草稿，接下來需要把它改成像樣的程序。
通過前面的分析以及上面的代碼，可以很明顯地看出4層循環(huán)體里的代碼邏輯是一樣的。
當循環(huán)遇上重復時…… 遞歸，就要來了。
但在遞歸之前，先做點小調(diào)整。
增加一個const n，用于定義棋盤的規(guī)格，避免直接使用字面量“4”；
將用于存儲皇后坐標的4個 array 合成1個 slice，這樣就不用做固定次數(shù)的初始化了，而且對 slice 的操作也使得代碼看上去更討巧一點。
然后，將之前代碼中，main 函數(shù)里的多重循環(huán)部分，精簡成一個遞歸的形式函數(shù)調(diào)用：
// 放置下一個皇后
// 函數(shù)的參數(shù)為已放置的皇后的坐標集
func place(queens [][2]int) {
// 獲取已放置的皇后數(shù)量
y := len(queens)
// 當已放置的皇后數(shù)量未達到n個之前，繼續(xù)求解動作
if y < n {
// 計算下一行的棋格狀態(tài)
nextRank := render(queens)
for x := 0; x < n; x++ {
// 當遍歷到下一行的可用棋格時
if !nextRank[x] {
// 放置一個皇后
queens = append(queens, [2]int{x, y})
// 然后繼續(xù)嘗試下一個皇后的放置
place(queens)
// 當上一句的遞歸調(diào)用結束時，表示本次求解過程的結束
// 此時，無論求解是否成功，均需要還原本次的狀態(tài)（即拿起皇后，準備嘗試下一次放置）
queens = queens[:y]
}
}
} else {
// 當n個皇后均已放置時，表示一次求解的完成
// TODO
}
}
之前代碼中，用于“根據(jù)已放置的皇后計算下一行棋格狀態(tài)”的 render 函數(shù)，無須調(diào)整。
最后，我覺得應該增加一點可視化的工作，將結果直觀的打印出來，雖然這不是解題的必要，但數(shù)據(jù)可視化絕對是一種人文關懷。
加個打印結果的函數(shù)：
// 打印結果
// 參數(shù)說明 - index：當前解法的序號；solution：皇后分布的坐標
func visualize(index int, solution [][2]int) {
fmt.Println('Solution ', index)
fmt.Println(strings.Repeat('-', 2*n-1))
for y := 0; y < n; y++ {
for x := 0; x < n; x++ {
if x == solution[y][0] && y == solution[y][1] {
fmt.Print('Q ')
} else {
fmt.Print('* ')
}
}
println()
}
fmt.Println(strings.Repeat('-', 2*n-1))
}
函數(shù) visualize 的調(diào)用，自然應該發(fā)生在 place 函數(shù)體的 else 部分，并且順便記錄一下解法的數(shù)量（加一個統(tǒng)計變量 total，統(tǒng)計解法總數(shù)）
else {
// 當n個皇后均已放置時，表示一次求解的完成
total++
visualize(total, queens)
}
最終的代碼長這樣：
// 8 QUEENS PUZZLE
package main
import (
'fmt'
'strings'
)
// 棋盤規(guī)格
const n int = 4
// 統(tǒng)計解法總數(shù)
var total int
func main() {
// 用于記錄已放置的皇后
var queens [][2]int
// 遞歸求解
place(queens)
}
// 放置下一個皇后
// 函數(shù)的參數(shù)為已放置的皇后的坐標集
func place(queens [][2]int) {
// 獲取已放置的皇后數(shù)量
y := len(queens)
// 當已放置的皇后數(shù)量未達到n個之前，繼續(xù)求解動作
if y < n {
// 計算下一行的棋格狀態(tài)
nextRank := render(queens)
for x := 0; x < n; x++ {
// 當遍歷到下一行的可用棋格時
if !nextRank[x] {
// 放置一個皇后
queens = append(queens, [2]int{x, y})
// 然后繼續(xù)嘗試下一個皇后的放置
place(queens)
// 當上一句的遞歸調(diào)用結束時，表示本次求解過程的結束
// 此時，無論求解是否成功，均需要還原本次的狀態(tài)（即拿起皇后，準備嘗試下一次放置）
queens = queens[:y]
}
}
} else {
// 當n個皇后均已放置時，表示一次求解的完成
total++
visualize(total, queens)
}
}
// 根據(jù)已放置的皇后，更新下一行棋格的狀態(tài)
// 返回一個含4個bool類型元素的數(shù)組，true表示受攻擊的，false表示未受攻擊。
func render(queens [][2]int) [n]bool {
var rank [n]bool
y := len(queens)
for x := 0; x < n; x++ {
for _, queen := range queens {
if x-queen[0] == y-queen[1] ||
x == queen[0] ||
x+y == queen[0]+queen[1] {
rank[x] = true
break
}
}
}
return rank
}
// 打印結果
// 參數(shù)說明 - index：當前解法的序號；solution：皇后分布的坐標
func visualize(index int, solution [][2]int) {
fmt.Println('Solution ', index)
fmt.Println(strings.Repeat('-', 2*n-1))
for y := 0; y < n; y++ {
for x := 0; x < n; x++ {
if x == solution[y][0] && y == solution[y][1] {
fmt.Print('Q ')
} else {
fmt.Print('* ')
}
}
println()
}
fmt.Println(strings.Repeat('-', 2*n-1))
}
運行結果如下：
將 const n int = 4 改成 const n int = 8 .
終于，得到八皇后的答案了。
共92種互不相同的解。
拿到結果了，可以再研究研究過程了。去掉可視化工作，只計算解法數(shù)量，然后看看程序的性能。
注釋掉 visualize 函數(shù)的調(diào)用，并將 main 函數(shù)改造一下，統(tǒng)計程序運行的時間：
func main() {
start := time.Now()
// 用于記錄已放置的皇后
var queens [][2]int
// 遞歸求解
place(queens)
end := time.Now()
elapsed := end.Sub(start)
fmt.Println('Total:', total)
fmt.Println('Elapsed:', elapsed)
}
在我老舊的一款ThinkPad E系列筆記本上
運行結果如下：
998微秒，不到1毫秒，看上去不錯。
至此，八皇后的問題徹底完結。
事實上，n 皇后的問題也順便完結了。
將常量 n 改成9，試試看：
共352種互不相同的解，耗時1.99毫秒。
n = 10 時：
8.99毫秒算出724種互不相同的解。
就這樣吧……
后 記
本來以為這個問題就算研究完了，直到有一天和老爸的另一次通話——
“你上次找老子要國際象棋的那個問題，后來想出來沒有？”
“爸，那小兒科我當天掛完電話，分分鐘就解出來了?！?br>“滾遠點，怕不是買了4副象棋吧？”
“怎么可能，我可以心算8盤棋?！?br>“滾遠點，你那個問題我后來也想了的，很簡單的問題啊?！?br>“??？”（What？？？ 老爸也解八皇后？）
“你題目只說了擺八個皇后，沒說不讓擺其它的棋子，對吧？你用其它的兵啊、馬啊等棋子把八個皇后隔開，就可以做到互不攻擊了?！?br>“@#￥%&$……”
“還有事嗎？”
“沒沒，沒了，爸?！保ǔ掷m(xù)暈眩中）
“早點休息，多喝水，天氣冷了注意加衣服，少熬夜。就這?！?/p>
——對方掛斷通話
附：老爸的解法
本文作者：sherrywasp
