从n皇后入门递归

题目

全排列代码

这个方法是和搜索 123 有多少种排列是一样的
默认从第一行往后搜索，因为是默认的每行一个，放在不同的列上
所以就只看 列 、主对角线、次对角线有没有被占即可
如果是满足条件的（行列和两个对角线都没有被占），则放置 皇后棋子，向下一行递归
之后回溯回来，把棋子和条件还原

对角线（左下到右上）：x + y 就是所在的对角线
对角线（右下到左上）：x - y + n ，+n 是因为有负数

/**
 * @author :Changersh
 * @date : 2022/11/2
 * n 皇后
 */

import java.io.*;
import java.util.*;
import java.lang.*;

public class acw_843 {
    private static int N = 20; // 因为对角线有 2n - 1 条
    private static char[][] s;
    private static int n;
    private static boolean[] col = new boolean[N];
    private static boolean[] diag = new boolean[N]; // 对角线
    private static boolean[] aDiag = new boolean[N]; // 反对角线
    public static void main(String[] args) {
        Kattio sc = new Kattio();
        n = sc.nextInt();
        s = new char[n][n];
        // 初始化
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                s[i][j] = '.';

        dfs(0);
        sc.close();
    }

    private static void dfs(int u) {
        if (u == n) {
            for (int i = 0; i < n; i++) {
                System.out.println(s[i]);
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!col[i] && !aDiag[u + i] && !diag[u - i + n]) {
                s[u][i] = 'Q';
                col[i] = aDiag[u + i] = diag[u - i + n] = true;
                dfs(u + 1);
                col[i] = aDiag[u + i] = diag[u - i + n] = false;
                s[u][i] = '.';
            }
        }
    }
}

class Kattio extends PrintWriter {
    // Kattio sc = new Kattio();
    // sc.close();
    private BufferedReader r;
    private StringTokenizer st;

    // 标准 IO
    public Kattio() {
        this(System.in, System.out);
    }

    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }

    // 文件 IO
    public Kattio(String intput, String output) throws IOException {
        super(output);
        r = new BufferedReader(new FileReader(intput));
    }

    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {
        }
        return null;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

全遍历搜索

一个个搜索，从第一行第一列开始，放置棋子
每个位置都有两种可能，放 或者 不放

当 y == n，到了这一行的末端边界，则 y = 0, x++，进入下一行
如果 x == n 则已经遍历完了，若此时 u == n，说明棋子也放完了，是满足的，就输出

#include 

using namespace std;

const int N = 10;

int n;
bool row[N], col[N], diag[N * 2], aDiag[N * 2];
char s[N][N];

void dfs(int x, int y, int u) {
	if (u > n) return;
	if (y == n) y = 0, x++;
	
	if (x == n) {
		if (u == n) {
			for (int i = 0; i < n; i++) puts(s[i]);
			puts("");
		}
		
		return;
	}
	
	dfs(x, y + 1, u);
	
	if (!row[x] && !col[y] && !diag[x + y] && !aDiag[x - y + n]) {
		s[x][y] = 'Q';
		row[x] = col[y] = diag[x + y] = aDiag[x - y + n] = true;
		dfs(x, y + 1, u + 1);
		s[x][y] = '.';
		row[x] = col[y] = diag[x + y] = aDiag[x - y + n] = false;
	}
	
	return;
}


int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			s[i][j] = '.';
	}
	
	dfs(0, 0, 0);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47