题解 | N皇后问题

1、解题思路

1. 回溯法：使用回溯法尝试在棋盘的每一行放置一个皇后。在放置皇后时，检查当前列和两个对角线是否已被其他皇后占用。如果当前位置安全，放置皇后并递归处理下一行。如果所有行都处理完毕，说明找到一个有效的摆放方法，计数加一。时间复杂度：O(n!)，空间复杂度：O(n)（递归栈的深度）。
2. 位运算优化：使用位运算来高效地检查列和对角线的占用情况。这种方法可以显著减少常数时间，但时间复杂度仍为 O(n!)。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    int Nqueen(int n) {
        // write code here
        int count = 0;
        vector<int> queens(n, -1);
        backtrack(0, queens, count);
        return count;
    }

    void backtrack(int row, vector<int>& queens, int& count) {
        int n = queens.size();
        if (row == n) {
            ++count;
            return ;
        }
        for (int col = 0; col < n; ++col) {
            if (isSafe(row, col, queens)) {
                queens[row] = col;
                backtrack(row + 1, queens, count);
                queens[row] = -1;
            }
        }
    }

    bool isSafe(int row, int col, vector<int>& queens) {
        for (int i = 0; i < row; ++i) {
            if (queens[i] == col || abs(row - i) == abs(col - queens[i])) {
                return false;
            }
        }
        return true;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 the n
     * @return int整型
     */
    public int Nqueen (int n) {
        // write code here
        int[] queens = new int[n];
        return backtrack(0, queens);
    }

    private int backtrack(int row, int[] queens) {
        int n = queens.length;
        if (row == n) {
            return 1;
        }
        int count = 0;
        for (int col = 0; col < n; ++col) {
            if (isSafe(row, col, queens)) {
                queens[row] = col;
                count += backtrack(row + 1, queens);
                queens[row] = -1;
            }
        }
        return count;
    }

    private boolean isSafe(int row, int col, int[] queens) {
        for (int i = 0; i < row; ++i) {
            if (queens[i] == col || Math.abs(row - i) == Math.abs(col - queens[i])) {
                return false;
            }
        }
        return true;
    }
}

3、复杂度分析

• 时间复杂度：O(n!)，因为需要生成所有可能的排列。
• 空间复杂度：O(n)，用于存储当前皇后的列位置和递归栈。