八皇后問題- 8 Queens Puzzle

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

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

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

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

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

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

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

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

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

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

用 js 實作

const NQueens = (n) => {
  let answer = 0;
  let arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(Array.from({ length: n }).fill(null));
  }

  let i = 0; //第幾列(橫向)
  let j = 0; //第幾行(直向)
  let loop = true;
  while (loop) {
    console.log("i", i, "j", j);
    arr[i][j] = "Q";
    console.log("arr", arr);
    //檢查橫行、縱行、斜線是否有其它Q的flag
    let checkQExist = false;
    let k = 0;
    while (k < i) {
      //確認當前的Q上方是否有其它Q的存在
      if (arr[k][j] === "Q") {
        checkQExist = true;
      }
      k++;
    }
    k = 0;
    while (k < j) {
      //確認當前的Q左邊是否有其它Q的存在
      if (arr[i][k] === "Q") {
        checkQExist = true;
      }
      k++;
    }
    k = 1;
    let l = -1;
    while (i + k < n && j + l >= 0) {
      //確認當前的Q對角線(左下角)是否有其它Q的存在
      if (arr[i + k][j + l] === "Q") {
        checkQExist = true;
      }
      k++;
      l--;
    }
    k = -1;
    while (i + k >= 0 && j + k >= 0) {
      //確認當前的Q對角線(右上角)是否有其它Q的存在
      if (arr[i + k][j + k] === "Q") {
        checkQExist = true;
      }
      k--;
    }
    if (!checkQExist) {
      console.log("Q can put here");
      console.log(arr);
      //已經放到最後一行了
      if (j === n - 1) {
        answer++;
        console.log("perfect solution");
        console.log(arr);
        arr[i][j] = null;
        i++; //往下一列
      } else {
        //往下一行
        i = 0;
        j++;
      }
    }

    if (checkQExist) {
      console.log("Q exist!!");
      console.log(arr);
      arr[i][j] = null; //不能放這格所以要清空
      i++;
    }

    //檢查是否超出邊界
    const checkBoundary = () => {
      j--;
      for (let r = 0; r < arr.length; r++) {
        if (arr[r][j] === "Q") {
          arr[r][j] = null;
          console.log("r and j is", r, j);
          i = r + 1;
          break;
        }
      }
    };

    while (i >= n) {
      //如果橫列超過n 需檢查前一行
      checkBoundary();
      if (j < 0) {
        console.log("done");
        loop = false;
        break;
      }
    }
  }
  console.log("Number of solution", answer);
};

NQueens(4); //2

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

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