javascript遞歸回溯法解八皇后問(wèn)題

javascript

遞歸回溯法解八皇后問(wèn)題：網(wǎng)上看到許多關(guān)于八皇后算法的文章， 很少能看到使用 javascript來(lái)實(shí)現(xiàn)的，今天就給大家使用 javascript來(lái)解決下這個(gè)問(wèn)題，有需要的小伙伴可以參考下。下面給大家分享的是回溯法解八皇后 ,帶詳細(xì)注解，這里就不多廢話了。functionNQueens(order){if(order<4){console.log('NQueensproblemapplyfororderbiggerthan3!');return;}varnQueens=[];varbackTracking=false;rowLoop:for(varrow=0;row<order;row++){//若出現(xiàn)row小于0,則說(shuō)明問(wèn)題無(wú)解if(row<0){console.log('ThisNQueensproblemhasnosolution!');break;}//第一次檢測(cè)到新的一行if(nQueens[row]===undefined){nQueens[row]=[];}//回溯時(shí)運(yùn)行的程序塊for(varcol=0;col<order;col++){//0為已經(jīng)檢測(cè)過(guò)并為能放置皇后的位置if(nQueens[row][col]===0){continue;}//回溯過(guò)程中，遇到能放皇后的位置，說(shuō)明這個(gè)位置在后面的驗(yàn)證沒(méi)有通過(guò)，需要重新處理elseif(backTracking&&nQueens[row][col]==1){//回溯時(shí)發(fā)現(xiàn),上一行也到行末 ,需要繼續(xù)回溯if(col===order-1){resetRow(nQueens,order,row);row=row-2;continuerowLoop;}//回溯的行還沒(méi)到行尾 ,標(biāo)0,繼續(xù)nQueens[row][col]=0;backTracking=false;continue;}//放置一個(gè)皇后nQueens[row][col]=1;//找到一個(gè)可以放置皇后的位置，跳出到下一行（一行上只能放一個(gè)皇后） 。if(isQueenValid(nQueens,row,col)){continuerowLoop;}//每一行都應(yīng)該有一個(gè)皇后，到列尾了還沒(méi)有找到合適的位置，說(shuō)明前面的皇后放置有問(wèn)題，需要回溯！elseif(col==order-1){backTracking=true;//0與1都表示這個(gè)位置已經(jīng)檢測(cè)過(guò)，因此要將本行清為 undefinedresetRow(nQueens,order,row);//減2是因?yàn)檠h(huán)尾還有個(gè)自加，其實(shí)就是回到上一行row=row-2;//退到外層循環(huán)，繼續(xù)continuerowLoop;}else{//未到行未，繼續(xù)檢測(cè)未檢測(cè)過(guò)的nQueens[row][col]=0;continue;};}}returnnQueens;}//回溯前,將本行清除functionresetRow(nQueens,order,row){for(varcol=0;col<order;col++){nQueens[row][col]=undefined;}}//檢測(cè)位置是否能放置皇后functionisQueenValid(nQueens,row,col){//行檢測(cè)for(vari=0;i<col;i++){if(nQueens[row][i]==1){returnfalse;}}for(varj=1;j<row+1;j++){列檢測(cè)左上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]+