[Golang-Leetcode]N皇后问题-解题思路

「这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战」

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：[["Q"]]
 

提示：

1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

解题

这是一道经典的回溯法的例题，和前面写过的解数独类似，不过在这题中，无需在每个节点进行遍历，只需要每行填入一个就可以跳到下行进行判断，可以剪掉不少分支。

这里使用伪代码展示回溯问题通用代码：

main:
    初始化board
    backtrack(board, 0)
    return res
backtrack:
    if 终止条件 {
        添加可行解
        return
    }
    for col := 0, col < n; col++ {
        if !isValid(board, row, col) {
            // 不符合条件剪枝
            continue
        }
        更新board
        backtrack(board, row + 1)
        回溯
    }
isValid:
    验证该点是否可行
复制代码

初始化棋盘

本题中，我们使用二维数组进行存储棋盘，使用遍历的方式，为棋盘附上初始值：

    // 初始化棋盘
    board := make([][]string, n)
    for i := 0; i < n; i++ {
        board[i] = make([]string, n)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n;j++ {
            board[i][j] = "."
        }
    }
复制代码

回溯算法

在回溯算法中，我们需要修改的基本只有输出类型以及遍历方法。

在输出方面，可以使用strings.Join实现行数据到字符串数据（题目要求）的转换。

func backtrack(board [][]string, row int, n int) {
    if row == n {
        // 终止条件 - 所有行均完成遍历
        temp := make([]string, n)
        for i := 0; i < n; i++ {
            temp[i] = strings.Join(board[i],"")
        }
        res = append(res, temp)
        return 
    }
    
    for col := 0; col < n; col++ {
        // 遍历行元素
        if !isValid(board, row, col, n){
            // 条件不符合则剪枝
            continue
        }
        // 暂定改点为可行节点
        board[row][col] = "Q"
        // 遍历下一行
        backtrack(board, row + 1, n)
        // 回溯
        board[row][col] = "."
    }
}
复制代码

可行性判断

了解了回溯算法，那么现在想要得到题解，就简化为判断插入节点是否符合条件了。

由于在同行、同列、和对角线上的皇后会相互攻击，因此需要避免这种情况，我们需要在插入节点前，分别对行、列、两个方向上的对角线进行遍历判断，若已经存在皇后，则isValid返回假。

代码实现如下：

func isValid(board [][]string, row, col int, n int) bool {
    // 判断同行重复
    for i := 0; i < row; i++ {
        if board[i][col] == "Q" {
            return false
        }
    }
    // 判断同列重复
    for i := 0; i < n; i++{
        if board[row][i] == "Q" {
            return false
        }
    }
    // 判断左上重复
    for i, j := row - 1, col - 1; i >= 0 && j >= 0; i, j = i-1, j-1 {
        if board[i][j] == "Q" {
            return false
        }
    }
    // 判断左下重复
    for i, j := row - 1, col + 1; i >= 0 && j < n; i, j = i-1, j+1 {
        if board[i][j] == "Q" {
            return false
        }
    }
    return true
}
复制代码

提交结果