N皇后

[Cosen95]

leetcode: https://leetcode-cn.com/problems/n-queens/

[Cosen95]

题目难度hard，涉及到的算法知识有DFS和回溯。

思路分析

我们来以n=4这种情况来理一下思路：

• 一行选一个格子放置皇后（置为"Q"），一行行地往下选，第一行有四种选择。
• 在选下一行的皇后时，为了不发生列的冲突，有三种选择。
• 继续往下一行选择，去构建完整解，可能会遇到对角线冲突。
• 遇到冲突继续往下选择没有意义，得不出合法的解。需要回溯。

那么，什么是回溯呢？

• 遍历枚举出所有可能的选择。
• 按顺序尝试这些选择：作出一种选择，并往下递归。
• 如果这个选择产生不出正确的解，要撤销这个选择（将当前置为 "Q" 的格子恢复为 "."），回到之前的选择，并作出下一个可用的选择。

到这里，基本思路就有了：构建出一棵解的空间树，利用约束条件做充分的剪枝，用 DFS的方式，搜索整个空间树，找出所有的解，遇到得不出解的分支，就提前回溯。

代码实现

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const board = new Array(n)
    for(let i = 0; i < n; i++) {    // 棋盘初始化
        board[i] = new Array(n).fill('.')
    }
    const res = []
    const isValid = (row, col) => {
        for(let i = 0; i < row; i++) {
            for(let j = 0; j < n; j++) {    // 和皇后在同一列和正反对角线上的都不符合要求
                if(board[i][j] == 'Q' && (j == col || i + j == row + col || i - j == row - col))                 {
                    return false
                }
            }
        }
        return true
    }
    const helper = (row) => {
        if (row == n) { // 递归中止条件
            const copyBoard = board.slice()
            for (let i = 0; i < n; i++) {
                // 每一行拼接成字符串
                copyBoard[i] = copyBoard[i].join('')
            }
            // 所有合法的答案推入res
            res.push(copyBoard)
            return
        }
        for(let col = 0; col < n; col++) {
            if(isValid(row, col)) {
                // 如果符合放置要求（剪枝），则放置皇后
                board[row][col] = 'Q'
                console.log('row--前',row, col)
                // 往下递归
                helper(row+1)
                // 撤销当前选择
                console.log('row--后',row, col)

                board[row][col] = '.'
            }
        }
    }
    helper(0)
    return res
};