DIV CSS 佈局教程網

用 JavaScript 遞迴與回溯法求解八皇后問題
編輯:JavaScript綜合知識     

八皇后問題是經典的演算法題目:在 8×8 的棋盤上放八個皇后,讓任意兩個皇后都不會互相威脅(同行、同列、同對角線皆不可)。網路上討論很多,但用 JavaScript 實作的相對少見,本文就來完整走一遍。

思路:為什麼用回溯法

最直觀的建模方式是「每一列只放一個皇后」。這樣一來,只要依序決定每一列皇后放在哪一行的哪個位置,並在每次放置後檢查是否合法;若後續發現無解,就退回上一列改放別的位置——這正是回溯法的核心。

完整實作

function NQueens(order) {
  // 4 皇后以下的問題無解(order 為 2、3 時)
  if (order < 4) {
    console.log('N Queens problem apply for order bigger than 3 !');
    return;
  }

  var nQueens = [];
  var backTracking = false;

  rowLoop: for (var row = 0; row < order; row++) {

    // 若 row 小於 0,代表所有可能都試完了,問題無解
    if (row < 0) {
      console.log('This N Queens problem has no solution !');
      break;
    }

    // 第一次拜訪這一列
    if (nQueens[row] === undefined) {
      nQueens[row] = [];
    }

    for (var col = 0; col < order; col++) {

      // 0 代表這個位置檢查過但不能放,直接跳過
      if (nQueens[row][col] === 0) {
        continue;
      }

      // 回溯時遇到「當初放得進去」的位置,代表它在後續驗證中被推翻,需要重來
      else if (backTracking && nQueens[row][col] == 1) {
        // 如果已經在該列末端,還得再往上回溯一層
        if (col === order - 1) {
          resetRow(nQueens, order, row);
          row = row - 2;
          continue rowLoop;
        }
        // 否則標記為 0,繼續往後找
        nQueens[row][col] = 0;
        backTracking = false;
        continue;
      }

      // 嘗試在 (row, col) 放皇后
      nQueens[row][col] = 1;

      // 合法就換下一列
      if (isQueenValid(nQueens, row, col)) {
        continue rowLoop;
      }
      // 走到該列末端仍找不到位置,代表前面某列的選擇有問題,需要回溯
      else if (col == order - 1) {
        backTracking = true;
        resetRow(nQueens, order, row);   // 清空本列,讓它能重新嘗試
        row = row - 2;                   // 迴圈尾會 +1,所以這裡 -2 等於回到上一列
        continue rowLoop;
      }
      else {
        nQueens[row][col] = 0;
        continue;
      }
    }
  }
  return nQueens;
}

// 回溯前清空該列的所有標記
function resetRow(nQueens, order, row) {
  for (var col = 0; col < order; col++) {
    nQueens[row][col] = undefined;
  }
}

// 判斷 (row, col) 是否可以放皇后
function isQueenValid(nQueens, row, col) {
  // 同列檢查
  for (var i = 0; i < col; i++) {
    if (nQueens[row][i] == 1) return false;
  }
  // 檢查左上方 45 度與右上方 45 度的對角線
  for (var j = 1; j < row + 1; j++) {
    if (nQueens[row - j][col] == 1
     || nQueens[row - j][col - j] == 1
     || nQueens[row - j][col + j] == 1) {
      return false;
    }
  }
  return true;
}

function printQ(queens) {
  for (var row = 0; row < queens.length; row++) {
    var rowText = '';
    for (var col = 0; col < queens.length; col++) {
      if (queens[row][col] === undefined) queens[row][col] = 0;
      rowText += queens[row][col] + ' ';
    }
    console.log(rowText);
  }
}

var queens = NQueens(8);
printQ(queens);

三個容易看錯的地方

1. 為什麼是 row = row - 2?因為在 for 迴圈中,每次迭代結束都會自動執行 row++。要回到上一列,就必須先減 2,加上迴圈自身的加一,淨效果才是 -1。

2. 為什麼要用 0 和 1 兩種標記?回溯時需要區分兩種狀態:這個位置「檢查過且不可用」(0),還是「曾經放得進去但後續被推翻」(1)。只有 1 才需要在回溯時重新嘗試,0 則可以直接跳過,這 distinction 讓回溯邏輯得以正確運作。

3. 為什麼用 labelled continue?continue rowLoop 直接跳到外層迴圈的下一次迭代,跳過 col++ 的剩餘流程。若用一般的 continue,只會跳過內層迴圈,邏輯就錯了。

更簡潔的現代寫法

如果只想要「找出所有解」,用遞迴會比回溯狀態機清楚得多:

function solveNQueens(n) {
  var results = [];

  function place(row, cols, diag1, diag2, current) {
    if (row === n) {
      results.push(current.slice());
      return;
    }
    for (var col = 0; col < n; col++) {
      var bit = 1 << col;
      // 檢查該位置的三個方向是否已被佔用
      if ((cols & bit) || (diag1 & (1 << (row + col))) || (diag2 & (1 << (row - col + n)))) {
        continue;
      }
      current.push(col);
      place(row + 1, cols | bit,
            diag1 | (1 << (row + col)),
            diag2 | (1 << (row - col + n)),
            current);
      current.pop();
    }
  }

  place(0, 0, 0, 0, []);
  return results;
}

console.log(solveNQueens(8).length);  // 92 組解

這個版本用位元運算記錄「哪些欄、哪兩條對角線已被佔用」,把每次合法性檢查壓到幾個位元運算,八皇后共有 92 組解,跑起來幾乎是瞬時的。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved