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

網(wǎng)上看到許多關(guān)于八皇后算法的文章，很少能看到使用javascript來(lái)實(shí)現(xiàn)的，今天就給大家使用javascript來(lái)解決下這個(gè)問(wèn)題，有需要的小伙伴可以參考下。

下面給大家分享的是回溯法解八皇后, 帶詳細(xì)注解，這里就不多廢話了。

function NQueens(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++) {

//若出現(xiàn)row小于0, 則說(shuō)明問(wèn)題無(wú)解

if(row < 0){

console.log('This N Queens problem has no solution ! ');

break;

}

//第一次檢測(cè)到新的一行

if (nQueens[row] === undefined) {

nQueens[row] = [];

}

//回溯時(shí)運(yùn)行的程序塊

for (var col=0; col<order; col++) {

//0為已經(jīng)檢測(cè)過(guò)并為能放置皇后的位置

if (nQueens[row][col] === 0) {

continue;

}

//回溯過(guò)程中，遇到能放皇后的位置，說(shuō)明這個(gè)位置在后面的驗(yàn)證沒(méi)有通過(guò)，需要重新處理

else if (backTracking && nQueens[row][col] == 1) {

//回溯時(shí)發(fā)現(xiàn),上一行也到行末,需要繼續(xù)回溯

if (col === order-1) {

resetRow(nQueens, order, row);

row = row - 2;

continue rowLoop;

}

//回溯的行還沒(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)) {

continue rowLoop;

}

//每一行都應(yīng)該有一個(gè)皇后，到列尾了還沒(méi)有找到合適的位置，說(shuō)明前面的皇后放置有問(wèn)題，需要回溯！

else if (col == order-1) {

backTracking = true;

//0與1都表示這個(gè)位置已經(jīng)檢測(cè)過(guò)，因此要將本行清為undefined

resetRow(nQueens, order, row);

//減2是因?yàn)檠h(huán)尾還有個(gè)自加，其實(shí)就是回到上一行

row = row - 2;

//退到外層循環(huán)，繼續(xù)

continue rowLoop;

} else {

//未到行未，繼續(xù)檢測(cè)未檢測(cè)過(guò)的

nQueens[row][col] = 0;

continue;

};

}

}

return nQueens;

}

//回溯前, 將本行清除

function resetRow(nQueens, order, row) {

for (var col=0; col<order; col++) {

nQueens[row][col] = undefined;

}

}

//檢測(cè)位置是否能放置皇后

function isQueenValid(nQueens, row, col) {

//行檢測(cè)

for (var i=0; i<col; i++) {

if (nQueens[row][i] == 1) {

return false;

}

}

for (var j=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)) {

return false;

}

}

return true;

}

function printQ(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 = NQueens(8);

printQ(queens);

以上就是本文的全部?jī)?nèi)容了，希望大家能夠喜歡。

更多信息請(qǐng)查看IT技術(shù)專(zhuān)欄