DIV CSS 佈局教程網

JavaScript 實現 N 皇后問題:回溯法完整解析
編輯:關於JavaScript     

謎題

N 皇后問題:在 N×N 的國際象棋棋盤上放置 N 個皇后,要求任意兩個皇后都不處於同一行、同一列或同一條對角線上,也就是它們互不攻擊。

策略

回溯法。逐行嘗試落子,每放一個皇后就檢查它是否與之前已放好的皇后衝突;不衝突就進入下一行,衝突就換一個位置試。若一整行都找不到合法位置,就回退到上一行,撤掉上一行的皇后再繼續嘗試。

JavaScript 實現(以八皇后為例)

/**
 * N 皇后問題
 */
function getNQueens(order) {
  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++) {
    if (nQueens[row] === undefined) {
      nQueens[row] = [];
    }

    for (var col=0; col<order; col++) {
      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;
        }
        nQueens[row][col] = 0;
        backTracking = false;
        continue;
      }

      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;
        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;
    }
  }
  // 檢查左上方與右上方的對角線
  for (var j=1; j<row+1; j++) {
    if (nQueens[row-j][col]==1
        || (nQueens[row-j][col-j]!=undefined && nQueens[row-j][col-j]==1)
        || (nQueens[row-j][col+j]!=undefined && nQueens[row-j][col+j]==1)) {
      return false;
    }
  }
  return true;
}

// 以 0/1 矩陣形式列印棋盤
function printQueens(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 = rowText + queens[row][col] + '  ';
    }
    console.log(rowText);
  }
}

var queens = getNQueens(8);
printQueens(queens);

結果

1  0  0  0  0  0  0  0 
0  0  0  0  1  0  0  0 
0  0  0  0  0  0  0  1 
0  0  0  0  0  1  0  0 
0  0  1  0  0  0  0  0 
0  0  0  0  0  0  1  0 
0  1  0  0  0  0  0  0 
0  0  0  1  0  0  0  0

八個皇后分布在八行八列上,任意兩兩不同行、不同列、不同對角線,這裡輸出的只是其中一個合法解——八皇后總共有 92 個解。程式開頭對 order < 4 做了攔截,因為當 N 小於 4 時該問題本身無解。

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