Leetcode 51. N皇后

力扣传送门(opens new window)

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×N 的棋盘，初始化所有位置为空（用 '.' 表示）。
2. 定义一个函数 solveNQueens，用于递归地尝试放置皇后。
3. 在 solveNQueens 函数中，逐行放置皇后。对于每一行，遍历列的位置，并检查是否可以放置皇后。
   • 如果可以放置皇后，将该位置标记为皇后（用 'Q' 表示），然后递归调用 solveNQueens 处理下一行。
   • 如果不能放置皇后，则回溯到上一行继续尝试其他位置。
4. 当成功放置 N 个皇后时，将当前棋盘状态添加到结果集中。
5. 最终返回结果集。

代码实现：

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>(); // 存储所有解决方案的列表
        char[][] board = new char[n][n]; // 创建一个二维字符数组来表示棋盘
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.'; // 初始化棋盘上的每个位置为空
            }
        }
        backtrack(board, 0, solutions); // 回溯算法求解
        return solutions;
    }

    private void backtrack(char[][] board, int row, List<List<String>> solutions) {
        if (row == board.length) {
            // 当成功放置 N 个皇后时，将当前棋盘状态添加到结果集中
            List<String> solution = new ArrayList<>();
            for (int i = 0; i < board.length; i++) {
                solution.add(new String(board[i]));
            }
            solutions.add(solution);
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = 'Q'; // 放置皇后
                backtrack(board, row + 1, solutions); // 递归处理下一行
                board[row][col] = '.'; // 回溯，撤销当前位置的皇后
            }
        }
    }

    private boolean isSafe(char[][] board, int row, int col) {
        // 检查同一列是否有皇后
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // 检查左上方是否有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 检查右上方是否有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}