八皇后問題- 8 Queens Puzzle

八皇后問題可以說是一道相當經典的演算法題目，以西洋棋為背景，如何在一個8x8的棋盤上擺放八個皇后的棋子，讓任何一個皇后無法吃掉其中一個皇后，也是就是任何一個皇后的橫行、縱行、斜線上都不會出現其它的皇后，後來八皇后問題也被衍生為N皇后問題 — 在N*N的棋盤上放置N個皇后，試問有幾種解法?就讓我們用回溯法來解N皇后的問題吧!

圖片來源:https://medium.com/nerd-for-tech/genetic-algorithm-8-queens-problem-b01730e673fd

先用四皇后來推演一下流程

1. 假設現在有個4*4的棋盤，我們先將第一個皇后放在第一個格子裡面

2. 由於一個直行只能有一個皇后，所以接下來將第二個皇后放在第二行的第一個，不過因為皇后的橫列不可以有其它皇后，所以往下挪動一格

3. 真不巧，斜線上也不能出現其它皇后，因此要再往下挪動一格

4. 因此第二個皇后擺放在這個位置

5. 接下來放置第三個皇后，但會發現一個問題，不管放在哪個位置都不行，因次要使用回溯法來調整第二個皇后的位置，把他往下移動一格

6. 調整完之後第三個皇后也放好了

7. 不過在擺放第四個皇后的時候，又發生了一樣的問題，只好用回溯法再次倒回去

8. 重覆先前的步驟之後，總算能夠成功擺放四個皇后了!

用js實作

單看程式碼實在是過於抽象，為了幫助理解所以將陣列印出來看，就會比較清楚整體的運作流程為何

為了驗證程式碼是否正確，將input改為8，結果運算時間出乎我的意料，真的是所謂的讓子彈飛一會，非常的耗時，一度還讓我以為是否寫了無窮迴圈😂，還好最後成功印出92

維基百科提供的N皇后解答