跳到主要内容

N-Queens

描述​

The n-queens puzzle is the problem of placing n queens on an n × n chessboard such that no two queens attack each other.

Eight Queens

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

分析​

经典的深搜题。

设置一个数组 vector<int> C(n, 0), C[i] 表示第 i 行皇后所在的列编号，即在位置 (i, C[i])上放了一个皇后，这样用一个一维数组，就能记录整个棋盘。

代码 1​

# N-Queens
# 深搜+剪枝
# 时间复杂度O(n!*n)，空间复杂度O(n)
def solveNQueens(n: int) -> list[list[str]]:
    result = []
    C = [0] * n  # C[i]表示第i行皇后所在的列编号
    dfs(C, 0, result)
    return result

def dfs(C: list[int], row: int, result: list[list[str]]) -> None:
    N = len(C)
    if row == N:  # 终止条件，也是收敛条件，意味着找到了一个可行解
        solution = []
        for i in range(N):
            char_array = ['.'] * N
            for j in range(N):
                if j == C[i]:
                    char_array[j] = 'Q'
            solution.append(''.join(char_array))
        result.append(solution)
        return

    for j in range(N):  # 扩展状态，一列一列的试
        ok = isValid(C, row, j)
        if not ok:
            continue  # 剪枝，如果非法，继续尝试下一列
        # 执行扩展动作
        C[row] = j
        dfs(C, row + 1, result)
        # 撤销动作
        # C[row] = -1

def isValid(C: list[int], row: int, col: int) -> bool:
    """
    能否在 (row, col) 位置放一个皇后.
    Args:
        C: 棋局
        row: 当前正在处理的行，前面的行都已经放了皇后了
        col: 当前列
    Returns:
        能否放一个皇后
    """
    for i in range(row):
        # 在同一列
        if C[i] == col:
            return False
        # 在同一对角线上
        if abs(i - row) == abs(C[i] - col):
            return False
    return True

代码 2​

// N-Queens
// 深搜+剪枝
// 时间复杂度O(n!)，空间复杂度O(n)
public class Solution {
    public List<List<String>> solveNQueens(int n) {
        this.columns = new boolean[n];
        this.main_diag = new boolean[2 * n - 1];
        this.anti_diag = new boolean[2 * n - 1];

        List<List<String>> result = new ArrayList<>();
        int[] C = new int[n];
        Arrays.fill(C, -1); // C[i]表示第i行皇后所在的列编号
        dfs(C, 0, result);
        return result;
    }


    private void dfs(int[] C, int row, List<List<String>> result) {
        final int N = C.length;
        if (row == N) { // 终止条件，也是收敛条件，意味着找到了一个可行解
            List<String> solution = new ArrayList<>();
            for (int i = 0; i < N; ++i) {
                char[] charArray = new char[N];
                Arrays.fill(charArray, '.');
                for (int j = 0; j < N; ++j) {
                    if (j == C[i]) charArray[j] = 'Q';
                }
                solution.add(new String(charArray));
            }
            result.add(solution);
            return;
        }

        for (int j = 0; j < N; ++j) {  // 扩展状态，一列一列的试
            final boolean ok = !columns[j] && !main_diag[row - j + N - 1]  &&
                    !anti_diag[row + j];
            if (!ok) continue;  // 剪枝，如果非法，继续尝试下一列
            // 执行扩展动作
            C[row] = j;
            columns[j] = main_diag[row - j + N - 1] = anti_diag[row + j] = true;
            dfs(C, row + 1, result);
            // 撤销动作
            // C[row] = -1;
            columns[j] = main_diag[row - j + N - 1] = anti_diag[row + j] = false;
        }
    }
    // 这三个变量用于剪枝
    private boolean[] columns;  // 表示已经放置的皇后占据了哪些列
    private boolean[] main_diag;  // 占据了哪些主对角线
    private boolean[] anti_diag;  // 占据了哪些副对角线
}

相关题目​