javascript遞歸回溯法解八皇后問題

字號:


    javascript遞歸回溯法解八皇后問題:
    網(wǎng)上看到許多關(guān)于八皇后算法的文章,很少能看到使用javascript來實(shí)現(xiàn)的,今天就給大家使用javascript來解決下這個(gè)問題,有需要的小伙伴可以參考下。
    下面給大家分享的是回溯法解八皇后, 帶詳細(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, 則說明問題無解
    if(row < 0){
    console.log('This N Queens problem has no solution ! ');
    break;
    }
    //第一次檢測到新的一行
    if (nQueens[row] === undefined) {
    nQueens[row] = [];
    }
    //回溯時(shí)運(yùn)行的程序塊
    for (var col=0; col<order; col++) {
    //0為已經(jīng)檢測過并為能放置皇后的位置
    if (nQueens[row][col] === 0) {
    continue;
    }
    //回溯過程中,遇到能放皇后的位置,說明這個(gè)位置在后面的驗(yàn)證沒有通過,需要重新處理
    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;
    }
    //回溯的行還沒到行尾, 標(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è)皇后,到列尾了還沒有找到合適的位置,說明前面的皇后放置有問題,需要回溯!
    else if (col == order-1) {
    backTracking = true;
    //0與1都表示這個(gè)位置已經(jīng)檢測過,因此要將本行清為undefined
    resetRow(nQueens, order, row);
    //減2是因?yàn)檠h(huán)尾還有個(gè)自加,其實(shí)就是回到上一行
    row = row - 2;
    //退到外層循環(huán),繼續(xù)
    continue rowLoop;
    } else {
    //未到行未,繼續(xù)檢測未檢測過的
    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);
    以上就是本文的全部內(nèi)容了,希望大家能夠喜歡。