JavaScript实现N皇后问题算法谜题解答

谜题
N皇后问题。将N个皇后放置在NxN的国际象棋棋盘上，其中没有任何两个皇后处于同一行、同一列或同一对角线上，以使得它们不能互相攻击。
策略
回溯法。
JavaScript解
以8皇后问题为例：

代码如下:


/**
 * Created by cshao on 12/28/14.
 */

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;   } }
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; }
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





有用  |  无用 取消

猜你喜欢