Day28:八皇后问题- 8 Queens Puzzle

八皇后问题可以说是一道相当经典的演算法题目，以西洋棋为背景，如何在一个8x8的棋盘上摆放八个皇后的棋子，让任何一个皇后无法吃掉其中一个皇后，也是就是任何一个皇后的横行、纵行、斜线上都不会出现其它的皇后，後来八皇后问题也被衍生为N皇后问题 - 在N*N的棋盘上放置N个皇后，试问有几种解法?就让我们用回溯法来解N皇后的问题吧!

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

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

假设现在有个4*4的棋盘，我们先将第一个皇后放在第一个格子里面
由於一个直行只能有一个皇后，所以接下来将第二个皇后放在第二行的第一个，不过因为皇后的横列不可以有其它皇后，所以往下挪动一格
真不巧，斜线上也不能出现其它皇后，因此要再往下挪动一格
因此第二个皇后摆放在这个位置
接下来放置第三个皇后，但会发现一个问题，不管放在哪个位置都不行，因次要使用回溯法来调整第二个皇后的位置，把他往下移动一格
调整完之後第三个皇后也放好了
不过在摆放第四个皇后的时候，又发生了一样的问题，只好用回溯法再次倒回去
重覆先前的步骤之後，总算能够成功摆放四个皇后了!

用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

单看程序码实在是过於抽象，为了帮助理解所以将阵列印出来看，就会比较清楚整体的运作流程为何