JavaScript實作N皇后問題演算法謎題答案_javascript技巧

謎題

N皇后問題。將N個皇后放置在NxN的國際象棋棋盤上，其中沒有任何兩個皇后處於同一行、同一列或同一對角線上，以使得它們不能互相攻擊。

策略

回溯法。

JavaScript解

以8皇后問題為例：

複製程式碼 程式碼如下:

/**
 * 由cshao於2014年12月28日創作。
 */

function getNQueens(order) {
  if (order     console.log('N Queens problem apply for order bigger than 3');
    return;
  }

  var nQueens = [];
  var backTracking = false;
  rowLoop:
  for (var row=0; row     if (nQueens[row] === undefined) {
      nQueens[row] = [];
    }

    for (var col=0; 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     nQueens[row][col] = undefined;
  }
}

function isQueenValid(nQueens, row, col) {
  for (var i=0; i

    if (nQueens[row][i] == 1) {
      return false;
    }
  }
  for (var j=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     var rowText = '';
    for (var col=0; 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