八皇后問題- 8 Queens Puzzle
Published in
Dec 27, 2021
八皇后問題可以說是一道相當經典的演算法題目,以西洋棋為背景,如何在一個8x8的棋盤上擺放八個皇后的棋子,讓任何一個皇后無法吃掉其中一個皇后,也是就是任何一個皇后的橫行、縱行、斜線上都不會出現其它的皇后,後來八皇后問題也被衍生為N皇后問題 — 在N*N的棋盤上放置N個皇后,試問有幾種解法?就讓我們用回溯法來解N皇后的問題吧!
先用四皇后來推演一下流程
- 假設現在有個4*4的棋盤,我們先將第一個皇后放在第一個格子裡面
2. 由於一個直行只能有一個皇后,所以接下來將第二個皇后放在第二行的第一個,不過因為皇后的橫列不可以有其它皇后,所以往下挪動一格
3. 真不巧,斜線上也不能出現其它皇后,因此要再往下挪動一格
4. 因此第二個皇后擺放在這個位置
5. 接下來放置第三個皇后,但會發現一個問題,不管放在哪個位置都不行,因次要使用回溯法來調整第二個皇后的位置,把他往下移動一格
6. 調整完之後第三個皇后也放好了
7. 不過在擺放第四個皇后的時候,又發生了一樣的問題,只好用回溯法再次倒回去
8. 重覆先前的步驟之後,總算能夠成功擺放四個皇后了!
用js實作
單看程式碼實在是過於抽象,為了幫助理解所以將陣列印出來看,就會比較清楚整體的運作流程為何
為了驗證程式碼是否正確,將input改為8,結果運算時間出乎我的意料,真的是所謂的讓子彈飛一會,非常的耗時,一度還讓我以為是否寫了無窮迴圈😂,還好最後成功印出92