iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
自我挑戰組

每日攝取一點資料結構和演算法系列 第 28

Day28:八皇后問題- 8 Queens Puzzle

https://ithelp.ithome.com.tw/upload/images/20210928/20128604lgEZqCdYrQ.jpg

八皇后問題可以說是一道相當經典的演算法題目,以西洋棋為背景,如何在一個8x8的棋盤上擺放八個皇后的棋子,讓任何一個皇后無法吃掉其中一個皇后,也是就是任何一個皇后的橫行、縱行、斜線上都不會出現其它的皇后,後來八皇后問題也被衍生為N皇后問題 - 在N*N的棋盤上放置N個皇后,試問有幾種解法?就讓我們用回溯法來解N皇后的問題吧!

https://ithelp.ithome.com.tw/upload/images/20210928/20128604qSFfNrIfoe.png

圖片來源:https://medium.com/nerd-for-tech/genetic-algorithm-8-queens-problem-b01730e673fd

先用四皇后來推演一下流程

  1. 假設現在有個4*4的棋盤,我們先將第一個皇后放在第一個格子裡面
    https://ithelp.ithome.com.tw/upload/images/20210928/20128604qlUtOKYcx4.png

  2. 由於一個直行只能有一個皇后,所以接下來將第二個皇后放在第二行的第一個,不過因為皇后的橫列不可以有其它皇后,所以往下挪動一格
    https://ithelp.ithome.com.tw/upload/images/20210928/20128604j9O8OaIdgq.png

  3. 真不巧,斜線上也不能出現其它皇后,因此要再往下挪動一格
    https://ithelp.ithome.com.tw/upload/images/20210928/2012860463K0xTDnF2.png

  4. 因此第二個皇后擺放在這個位置
    https://ithelp.ithome.com.tw/upload/images/20210928/201286045UVfCrOte2.png

  5. 接下來放置第三個皇后,但會發現一個問題,不管放在哪個位置都不行,因次要使用回溯法來調整第二個皇后的位置,把他往下移動一格
    https://ithelp.ithome.com.tw/upload/images/20210928/20128604NZP87EJXDJ.png

  6. 調整完之後第三個皇后也放好了
    https://ithelp.ithome.com.tw/upload/images/20210928/20128604G0jhOja3nA.png

  7. 不過在擺放第四個皇后的時候,又發生了一樣的問題,只好用回溯法再次倒回去
    https://ithelp.ithome.com.tw/upload/images/20210928/201286047X51NA142z.png

  8. 重覆先前的步驟之後,總算能夠成功擺放四個皇后了!
    https://ithelp.ithome.com.tw/upload/images/20210928/20128604K4KtbbFkAx.png

用js實作

const NQueens = (n) => {
    let answer = 0;
    let arr = [];
    for (let i = 0; i < n; i++) {
        arr.push(Array.from({ length: n }).fill(null));
    }

    let i = 0; //第幾列(橫向)
    let j = 0; //第幾行(直向)
    let loop = true;
    while (loop) {
        console.log("i", i, "j", j);
        arr[i][j] = "Q";
        console.log("arr", arr);
        //檢查橫行、縱行、斜線是否有其它Q的flag
        let checkQExist = false;
        let k = 0;
        while (k < i) {
            //確認當前的Q上方是否有其它Q的存在
            if (arr[k][j] === "Q") {
                checkQExist = true;
            }
            k++;
        }
        k = 0;
        while (k < j) {
            //確認當前的Q左邊是否有其它Q的存在
            if (arr[i][k] === "Q") {
                checkQExist = true;
            }
            k++;
        }
        k = 1;
        let l = -1;
        while (i + k < n && j + l >= 0) {
            //確認當前的Q對角線(左下角)是否有其它Q的存在
            if (arr[i + k][j + l] === "Q") {
                checkQExist = true;
            }
            k++;
            l--;
        }
        k = -1;
        while (i + k >= 0 && j + k >= 0) {
            //確認當前的Q對角線(右上角)是否有其它Q的存在
            if (arr[i + k][j + k] === "Q") {
                checkQExist = true;
            }
            k--;
        }
        if (!checkQExist) {
            console.log("Q can put here");
            console.log(arr);
            //已經放到最後一行了
            if (j === n - 1) {
                answer++;
                console.log("perfect solution");
                console.log(arr);
                arr[i][j] = null;
                i++; //往下一列
            } else {
                //往下一行
                i = 0;
                j++;
            }
        }

        if (checkQExist) {
            console.log("Q exist!!");
            console.log(arr);
            arr[i][j] = null; //不能放這格所以要清空
            i++;
        }

        //檢查是否超出邊界
        const checkBoundary = () => {
            j--;
            for (let r = 0; r < arr.length; r++) {
                if (arr[r][j] === "Q") {
                    arr[r][j] = null;
                    console.log("r and j is", r, j);
                    i = r + 1;
                    break;
                }
            }
        };

        while (i >= n) {
            //如果橫列超過n 需檢查前一行
            checkBoundary();
            if (j < 0) {
                console.log("done");
                loop = false;
                break;
            }
        }
    }
    console.log("Number of solution", answer);
};

NQueens(4); //2

單看程式碼實在是過於抽象,為了幫助理解所以將陣列印出來看,就會比較清楚整體的運作流程為何
https://ithelp.ithome.com.tw/upload/images/20210928/20128604A2syyRXPOL.png

為了驗證程式碼是否正確,將input改為8,結果運算時間出乎我的意料,真的是所謂的讓子彈飛一會,非常的耗時,一度還讓我以為是否寫了無窮迴圈/images/emoticon/emoticon04.gif,還好最後成功印出92

維基百科提供的N皇后解答
https://ithelp.ithome.com.tw/upload/images/20210928/20128604pXFlLTWVrh.png


上一篇
Day27:Backtracking -回溯法
下一篇
Day29:刷起來! leetcode
系列文
每日攝取一點資料結構和演算法30

尚未有邦友留言

立即登入留言