N 皇后

题解思路

问题分析

N 皇后问题是一个经典的回溯算法问题，要求在一个 n × n 的棋盘上放置 n 个皇后，确保没有两个皇后能相互攻击。根据国际象棋的规则，皇后可以攻击同行、同列、同斜线上的棋子，因此我们需要确保在摆放皇后时，满足以下条件：

1. 同一行的皇后不能相互攻击。
2. 同一列的皇后不能相互攻击。
3. 同一对角线上的皇后不能相互攻击。

我们的目标是找到所有满足这些条件的皇后摆放方案，并将它们以特定格式输出。

解题思路

我们可以采用回溯法来逐步构建解决方案。具体思路如下：

1. 回溯法：我们逐行放置皇后，尝试每一列的位置，如果该位置合法（不在同一列、同一对角线），则将皇后放置在该位置，然后递归处理下一行的放置。
2. 合法性判断：
   • 使用三个集合来判断某个位置是否合法：
     • cols：记录哪些列已经有皇后。
     • diag1：记录主对角线上的位置（行 - 列）。
     • diag2：记录副对角线上的位置（行 + 列）。
   • 通过这三个集合，我们可以有效地判断一个位置是否与之前放置的皇后冲突。
3. 递归与回溯：如果放置皇后后没有冲突，则递归进入下一行；如果冲突，则回溯并尝试其他可能的位置。

复杂度分析

• 时间复杂度：最坏情况下，我们需要检查每行的每一列，因此时间复杂度是 O(n!)，其中 n 是皇后的数量。
• 空间复杂度：我们使用了三个集合来存储已使用的列和对角线，因此空间复杂度是 O(n)。

代码实现

Python 代码实现

def solveNQueens(n):
    result = []

    # 检查当前位置是否可以放置皇后
    def is_valid(row, col, cols, diag1, diag2):
        if col in cols or (row - col) in diag1 or (row + col) in diag2:
            return False
        return True

    # 回溯函数
    def backtrack(row, cols, diag1, diag2, board):
        # 如果所有的皇后都已放置，则保存当前解法
        if row == n:
            result.append(["".join(row) for row in board])
            return
        
        for col in range(n):
            if is_valid(row, col, cols, diag1, diag2):
                # 放置皇后
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                board[row][col] = 'Q'
                
                # 递归放置下一行
                backtrack(row + 1, cols, diag1, diag2, board)
                
                # 回溯
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
                board[row][col] = '.'

    # 初始化棋盘
    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return result

n = int(input())
solutions = solveNQueens(n)
for solution in solutions:
    for row in solution:
        print(row)
    print()  # 每个解法之间空一行

Java 代码实现

import java.util.*;

public class Main {
    
    // 判断当前位置是否合法
    public static boolean isValid(int row, int col, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
        return !cols.contains(col) && !diag1.contains(row - col) && !diag2.contains(row + col);
    }

    // 回溯函数
    public static void backtrack(int row, int n, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2, List<List<String>> result, char[][] board) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] rowArray : board) {
                solution.add(new String(rowArray));
            }
            result.add(solution);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, cols, diag1, diag2)) {
                board[row][col] = 'Q';
                cols.add(col);
                diag1.add(row - col);
                diag2.add(row + col);
                backtrack(row + 1, n, cols, diag1, diag2, result, board);
                board[row][col] = '.';  // 回溯
                cols.remove(col);
                diag1.remove(row - col);
                diag2.remove(row + col);
            }
        }
    }

    // 主函数
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        Set<Integer> cols = new HashSet<>();
        Set<Integer> diag1 = new HashSet<>();
        Set<Integer> diag2 = new HashSet<>();
        backtrack(0, n, cols, diag1, diag2, result, board);
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<List<String>> solutions = solveNQueens(n);
        for (List<String> solution : solutions) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();  // 每个解法之间空一行
        }
    }
}

C++ 代码实现

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;

// 判断当前位置是否合法
bool isValid(int row, int col, set<int>& cols, set<int>& diag1, set<int>& diag2) {
    return !cols.count(col) && !diag1.count(row - col) && !diag2.count(row + col);
}

// 回溯函数
void backtrack(int row, int n, set<int>& cols, set<int>& diag1, set<int>& diag2, vector<vector<string>>& result, vector<string>& board) {
    if (row == n) {
        result.push_back(board);
        return;
    }
    
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, cols, diag1, diag2)) {
            board[row][col] = 'Q';
            cols.insert(col);
            diag1.insert(row - col);
            diag2.insert(row + col);
            backtrack(row + 1, n, cols, diag1, diag2, result, board);
            board[row][col] = '.';  // 回溯
            cols.erase(col);
            diag1.erase(row - col);
            diag2.erase(row + col);
        }
    }
}

// 主函数
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<string> board(n, string(n, '.'));
    set<int> cols, diag1, diag2;
    backtrack(0, n, cols, diag1, diag2, result, board);
    return result;
}

int main() {
    int n;
    cin >> n;
    vector<vector<string>> solutions = solveNQueens(n);
    for (const auto& solution : solutions) {
        for (const auto& row : solution) {
            cout << row << endl;
        }
        cout << endl;  // 每个解法之间空一行
    }
    return 0;
}

Leetcode 62.N皇后-原题链接

题目内容

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

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

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

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

输入描述

输入只有一行，包含一个整数 $n$。

输出描述

输出所有不同的解决方案，每个方案占 $n$ 行，每行有 $n$ 个字符（'Q' 或 '.'），方案之间用一个空行分隔。

注意：方案的输出顺序不限，但每个方案内部的行顺序必须严格从上到下。

样例1

输入

4

输出

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

说明

如上图所示，$4$ 皇后问题存在两个不同的解法。

样例2

输入

1

输出

Q

提示：

• $1 <= n <= 9$