LeetCode-热题100：51. N 皇后

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

代码及注释

func solveNQueens(n int) [][]string {
    // 初始化结果集
    res := make([][]string, 0)
    
    // 初始化棋盘
    board := make([][]rune, n)
    for i := 0; i < n; i++ {
        board[i] = make([]rune, n)
        for j := 0; j < n; j++ {
            board[i][j] = '.'
        }
    }

    // 判断当前位置是否可以放置皇后
    var isValid func(row, col int) bool 
    isValid = func(row, col int) bool {
        // 检查同列是否有皇后
        for i := 0; i < row; i++ {
            if board[i][col] == '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
    }

    // 回溯函数
    var backtrack func(row int)
    backtrack = func(row int) {
        // 找到一个解决方案
        if row == n {
            tmp := make([]string, n)
            for i := 0; i < n; i++ {
                tmp[i] = string(board[i])
            }
            res = append(res, tmp)
            return
        }

        // 尝试在当前行的每一列放置皇后
        for col := 0; col < n; col++ {
            if isValid(row, col) {
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
            }
        }
    }
    
    // 从第 0 行开始放置皇后
    backtrack(0)
    
    // 返回结果集
    return res
}

代码解释：

1. 初始化结果集和棋盘

   res := make([][]string, 0)
   board := make([][]rune, n)
   

   • res 用于存储所有的解决方案。
   • board 初始化为一个 n x n 的棋盘，初始为全 '.'。

2. 判断当前位置是否可以放置皇后

   var isValid func(row, col int) bool
   

   • isValid 函数用于判断在 (row, col) 位置是否可以放置皇后。它会检查同列、左上方和右上方是否有皇后。

3. 回溯函数

   var backtrack func(row int)
   

   • backtrack 函数是主要的递归函数，用于尝试在当前行的每一列放置皇后，并继续下一行。

4. 找到一个解决方案

   if row == n {
       tmp := make([]string, n)
       for i := 0; i < n; i++ {
           tmp[i] = string(board[i])
       }
       res = append(res, tmp)
       return
   }
   

   当 row 达到 n 时，表示找到一个完整的解决方案。将当前的棋盘状态保存到 res 中。

5. 尝试在当前行的每一列放置皇后

   for col := 0; col < n; col++ {
       if isValid(row, col) {
           board[row][col] = 'Q'
           backtrack(row + 1)
           board[row][col] = '.'
       }
   }
   

   从左到右遍历当前行的每一列，如果当前位置可以放置皇后，则递归地尝试下一行，并在回溯时移除当前的皇后。

6. 从第 0 行开始放置皇后

   backtrack(0)
   

   从第 0 行开始调用 backtrack 函数。

7. 返回结果集

   return res
   

   返回所有找到的解决方案。

使用回溯算法来解决 N 皇后问题，通过递归遍历每一行的每一列，尝试找到所有可能的解决方案，并将有效的解决方案保存到返回集。