javascript递归回溯法解八皇后问题
下面给大家分享的是回溯法解八皇后,带详细注解，这里就不多废话了。
functionNQueens(order){
if(order<4){
console.log('NQueensproblemapplyfororderbiggerthan3!');
return;
}
varnQueens=[];
varbackTracking=false;
rowLoop:
for(varrow=0;row<order;row++){
//若出现row小于0,则说明问题无解
if(row<0){
console.log('ThisNQueensproblemhasnosolution!');
break;
}
//第一次检测到新的一行
if(nQueens[row]===undefined){
nQueens[row]=[];
}
//回溯时运行的程序块
for(varcol=0;col<order;col++){
//0为已经检测过并为能放置皇后的位置
if(nQueens[row][col]===0){
continue;
}
//回溯过程中，遇到能放皇后的位置，说明这个位置在后面的验证没有通过，需要重新处理
elseif(backTracking&&nQueens[row][col]==1){
//回溯时发现,上一行也到行末,需要继续回溯
if(col===order-1){
resetRow(nQueens,order,row);
row=row-2;
continuerowLoop;
}
//回溯的行还没到行尾,标0,继续
nQueens[row][col]=0;
backTracking=false;
continue;
}
//放置一个皇后
nQueens[row][col]=1;
//找到一个可以放置皇后的位置，跳出到下一行（一行上只能放一个皇后）。
if(isQueenValid(nQueens,row,col)){
continuerowLoop;
}
//每一行都应该有一个皇后，到列尾了还没有找到合适的位置，说明前面的皇后放置有问题，需要回溯！
elseif(col==order-1){
backTracking=true;
//0与1都表示这个位置已经检测过，因此要将本行清为undefined
resetRow(nQueens,order,row);
//减2是因为循环尾还有个自加，其实就是回到上一行
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++){
//列检测左上45度右上45度
if(nQueens[row-j][col]==1||(nQueens[row-j][col-j]==1)||(nQueens[row-j][col+j]==1)){
returnfalse;
}
}
returntrue;
}
functionprintQ(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=NQueens(8);
printQ(queens);
以上就是本文的全部内容了，希望大家能够喜欢。