下面給大家分享的是回溯法解八皇後, 帶詳細注解,這裡就不多廢話了。
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++) { //若出現row小於0, 則說明問題無解 if(row < 0){ console.log('This N Queens problem has no solution ! '); break; } //第一次檢測到新的一行 if (nQueens[row] === undefined) { nQueens[row] = []; } //回溯時運行的程序塊 for (var col=0; col<order; col++) { //0為已經檢測過並為能放置皇後的位置 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; } //回溯的行還沒到行尾, 標0, 繼續 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; //0與1都表示這個位置已經檢測過,因此要將本行清為undefined resetRow(nQueens, order, row); //減2是因為循環尾還有個自加,其實就是回到上一行 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++) { // 列檢測 左上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);
以上就是本文的全部內容了,希望大家能夠喜歡。