谜题
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