[leetcode javascript解题]N-Queens

╰半橙微兮° 2022-06-12 06:45 32阅读 0赞

该题描述如下：

> The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.  
> ![这里写图片描述][SouthEast]  
> Given an integer n, return all distinct solutions to the n-queens puzzle.  
> Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.  
> For example,  
> There exist two distinct solutions to the 4-queens puzzle:  
> \[  
> \[“.Q..”, // Solution 1  
> “…Q”,  
> “Q…”,  
> “..Q.”\],
> 
> \[“..Q.”, // Solution 2  
> “Q…”,  
> “…Q”,  
> “.Q..”\]  
> \]

其实玩过国际象棋就知道，皇后可以斜着和横竖走，所谓皇后问题就是所有皇后所在位置互相不能吃到彼此。  
我的代码如下：

/** * @param {number} n * @return {string[][]} */
    var solveNQueens = function(n) {
        let result = [],
            i = 1,
            temp = [],
            // 检测是否符合要求的工具函数
            check = function(arr, num) {
                for (let k = 0; k < num; k++) {
                    if (arr[k] === arr[num] || Math.abs(arr[k] - arr[num]) === num - k) {
                        return false;
                    }
                }
                return true;
            },
            queens = '.'.repeat(n).split('');
        temp[0] = 0;
        // 回溯法求解
        while (i > 0) {
            temp[i - 1] += 1;
            while (temp[i - 1] <= n){
                if(check(temp, i - 1)) {
                    if (i === n) {
                       result.push(temp.slice(0, n));
                    }
                    temp[i] = 0;
                    i += 2;
                    break;
                } else {
                    temp[i - 1] += 1;
                }
            } 
            i--;
        }
        // 得到的实际上是数字解，比如[2,4,1,3]这种，所以需要转换一下
        return result.map((val) => {
            return val.map((item) => {
                let q = [...queens];
                q.splice(item - 1, 1, 'Q');
                return q.join('');
            })
        })
    };

我是通过回溯法来解的：

思路首先是设计工具函数，用于判定当前皇后落下棋盘时，会不会影响到之前的皇后，如果不影响才返回true。

然后回溯流程首先判断是从1开始，对应每一个小于皇后总数n的数，是否存在一个皇后满足条件，如果满足，直接break，去查询下一个皇后（+=2 再– 相当于+1），否则等遍历完了还不存在，就–，回到上一个皇后，上一个皇后往后重新找，相当于是一次回溯。

最后由于答案是要求\[‘…Q’\]这种，在解题过程中，为了不增加操作成本，我是Q的位置对应为数字储存的，最后才进行统一处理。

[SouthEast]: /images/20220612/292dfaaea3a5438c902ca0f6d5fd35ec.png