JavaScript实现N皇后问题算法谜题解答
谜题
N皇后问题。将N个皇后放置在NxN的国际象棋棋盘上，其中没有任何两个皇后处于同一行、同一列或同一对角线上，以使得它们不能互相攻击。
策略
回溯法。
JavaScript解
以8皇后问题为例：
/** *Createdbycshaoon12/28/14. */
functiongetNQueens(order){ if(order<4){ console.log('NQueensproblemapplyfororderbiggerthan3'); return; }
varnQueens=[]; varbackTracking=false; rowLoop: for(varrow=0;row<order;row++){ if(nQueens[row]===undefined){ nQueens[row]=[]; }
for(varcol=0;col<order;col++){ if(nQueens[row][col]===0){ continue; }elseif(backTracking&&nQueens[row][col]==1){ if(col===order-1){ resetRow(nQueens,order,row); row=row-2; continuerowLoop; } nQueens[row][col]=0; backTracking=false; continue; } nQueens[row][col]=1; if(isQueenValid(nQueens,row,col)){ continuerowLoop; }elseif(col==order-1){ backTracking=true; resetRow(nQueens,order,row); row=row-2; continuerowLoop; }else{ nQueens[row][col]=0; continue; }; } }
returnnQueens; }
functionresetRow(nQueens,order,row){ for(varcol=0;col<order;col++){ nQueens[row][col]=undefined; } }
functionisQueenValid(nQueens,row,col){ for(vari=0;i<col;i++){ if(nQueens[row][i]==1){ returnfalse; } } for(varj=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)){ returnfalse; } } returntrue; }
functionprintQueens(queens){ for(varrow=0;row<queens.length;row++){ varrowText=''; for(varcol=0;col<queens.length;col++){ if(queens[row][col]===undefined){ queens[row][col]=0; } rowText=rowText+queens[row][col]+' '; } console.log(rowText); } }
varqueens=getNQueens(8); printQueens(queens);