7-7 n皇后

n皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

输入格式:

共一行，包含整数 n (1 ≤ n ≤ 12)。

输出格式:

给出所有可能摆放情况的种数，结尾无空格换行。

输入样例:

在这里给出一组输入。例如：

4

输出样例:

在这里给出相应的输出。例如：

2

简化版代码

#include <iostream>

const int N = 15;
const int M = 30;

int ans, n;
bool x[N], y[M], z[M];

void dfs(int i)
{
    if (i == n) ++ans;
    for (int j = 0; j < n; ++j) {
        if (x[j] || y[N + j - i] || z[i + j]) continue;
        x[j] = y[N + j - i] = z[i + j] = true;
        dfs(i + 1);
        x[j] = y[N + j - i] = z[i + j] = false;
    }
}

int main()
{
    scanf("%d", &n);
    dfs(0);
    printf("%d", ans);
  
    return 0;
}

注释版代码

其中x​数组表示每列是否有皇后，y​和z​数组表示主对角线和副对角线是否有皇后。

#include <iostream>

const int N = 15;
const int M = 30;

int ans, n;
bool x[N], y[M], z[M];

// 深度优先搜索函数
void dfs(int i)
{
    // 如果已经遍历到最后一行，递增答案计数
    if (i == n) ++ans;

    // 尝试在当前行的每一列放置皇后
    for (int j = 0; j < n; ++j) {
        // 如果当前列、主对角线、副对角线已经有皇后，则跳过
        if (x[j] || y[N + j - i] || z[i + j]) continue;

        // 放置皇后并递归到下一行
        x[j] = y[N + j - i] = z[i + j] = true;
        dfs(i + 1);

        // 恢复状态，回溯
        x[j] = y[N + j - i] = z[i + j] = false;
    }
}

int main()
{
    // 输入棋盘大小
    scanf("%d", &n);

    // 开始深度优先搜索
    dfs(0);

    // 输出答案
    printf("%d", ans);

    return 0;
}

java版代码

import java.util.Scanner;

public class Main {
    static final int N = 15;
    static final int M = 30;
    static int ans, n;
    static boolean[] x = new boolean[N];
    static boolean[] y = new boolean[M];
    static boolean[] z = new boolean[M];

    // 深度优先搜索函数
    static void dfs(int i) {
        // 如果已经遍历到最后一行，递增答案计数
        if (i == n) ++ans;

        // 尝试在当前行的每一列放置皇后
        for (int j = 0; j < n; ++j) {
            // 如果当前列、主对角线、副对角线已经有皇后，则跳过
            if (x[j] || y[N + j - i] || z[i + j]) continue;

            // 放置皇后并递归到下一行
            x[j] = y[N + j - i] = z[i + j] = true;
            dfs(i + 1);

            // 恢复状态，回溯
            x[j] = y[N + j - i] = z[i + j] = false;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入棋盘大小
        n = scanner.nextInt();

        // 开始深度优先搜索
        dfs(0);

        // 输出答案
        System.out.println(ans);
    }
}

‍