# 递归-八皇后问题（回溯算法）
八皇后问题，是一个古老而著名的问题，是 回溯算法 的典型案例。
该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
使用回溯算法，高斯认为有 76 种方案。1854年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以解决此问题
可以去百度搜索下这个小游戏，自己玩几下感受下，还是很难的
# 八皇后思路分析
找出八皇后有多少种摆法，其实就是暴力穷举，思路如下：
- 第一个个皇后先放第一行第一列
- 第二个皇后放在第二行第一列，然后判断是否符合规则，如果不符合规则，则继续放在第 2 列，依次把所有列都放完，找到一个合适的列（某一遍）
- 继续第 3 个皇后，直到 8 个皇后都放到了棋盘上，并且没有违反规则，就算一个解答
- 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后放在第一列的所有正确解全部拿到
- 然后回头继续第一个皇后放第二列，后面继续循环执行前面 4 步
理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}，这个是存储结果，数组下标表示第几行，对应的值则为在那一列上摆放着
package cn.mrcode.study.dsalgtutorialdemo.datastructure.recursion;
import org.junit.Test;
/**
* 八皇后问题：
* <pre>
* 规则：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意 两个皇后 都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
* </pre>
*/
public class Queue8 {
// 共有多少个皇后
int max = 8;
/**
* 存放皇后位置的结果
* <pre>
* 下标：表示棋盘中的某一行
* 对应的值：表示在这一行上，该皇后摆放在哪一列
* 比如：array[0] = 1，表示在第 1 行的第 2 列上摆放了一个皇后
*
* 由于规则，一行只能有一个皇后，所以可以使用一维数组来代替二维数组的棋盘结果
* </pre>
*/
int[] array = new int[max];
int count = 0; // 统计有多少个结果
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0); // 从第 1 行开始放置
}
/**
* 放置第 n 个（行）皇后
*
* @param n
*/
private void check(int n) {
// n = 8，那么表示放第 9 个皇后，8 个皇后已经放完了
// 表示找到了一个正确的结果，打印这个结果，并返回
if (n == max) {
count++;
print();
return;
}
// 开始暴力对比，从该行的第一列开始尝试放置皇后，直到与前面所放置的不冲突
for (int i = 0; i < max; i++) {
// 在该行的第 i 列上放置一个皇后
array[n] = i;
// 检测与已经放置的是否冲突
if (judge(n)) {
// 如果不冲突，则表示该行的皇后放置没有问题
// 开始进入下一行的皇后放置
check(n + 1);
}
// 如果冲突，这里什么也不做
// 因为是从第一列开始放置，如果冲突，则尝试放置到第 2 列上，直到放置成功
}
}
/**
* 判定要放置的这一个皇后，和前面已经摆放的位置是否冲突
*
* @param n 第 n 个皇后
* @return
*/
private boolean judge(int n) {
for (int i = 0; i < n; i++) {
if (
/*
如果他们的摆放位置一样，说明是在同一列
x ....
x ....
*/
array[i] == array[n]
/*
检测是否是同一斜列
下标: 代表的是第几行
值：代表的是第几列
. x . . . n = 1,value = 1
x . . . . i = 0,value = 0
Math.abs(n - i) = 1
Math.abs(array[n] - array[i]) = 1
. . x . . n = 1,value = 2
. x . . . i = 0,value = 1
Math.abs(n - i) = 1
Math.abs(array[n] - array[i]) = 1
*/
|| Math.abs(n - i) == Math.abs(array[n] - array[i])
) {
return false;
}
}
return true;
}
/**
* 打印皇后的位置
*/
private void print() {
System.out.printf("第 %02d 个结果 ：", count);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
/**
* 下面是对于判定是否是同行，同列、同一斜列的分步骤测试，比较好理解
*/
@Test
public void judgeTest() {
/*
* . . . . . . . .
* x . . . . . . .
*/
Queue8 queue8 = new Queue8();
queue8.array[0] = 0;
//======== 放置第 1 个皇后
// 判断是否是同一列
/*
* x . . . . . . . // 计划放到这里
* x . . . . . . .
*/
queue8.array[1] = 0; // 从第一列开始放置
System.out.println("同一列，是否通过：" + queue8.judge(1));
/*
* . x . . . . . . // 计划放到这里
* x . . . . . . .
*/
queue8.array[1] = 1;
// 第一列不行，放置到第 2 列上
System.out.println("同一斜列，是否通过：" + queue8.judge(1));
/*
* . . x . . . . . // 计划放到这里
* x . . . . . . .
*/
queue8.array[1] = 2;
// 第 2 列不行，放置到第 3 列上,这个肯定是可以的
System.out.println("同一列或同一斜列，是否通过：" + queue8.judge(1));
//======== 放置第 3 个皇后
/*
* x . . . . . . . // 计划放到这里
* . . x . . . . .
* x . . . . . . .
*/
queue8.array[2] = 0;
// 与第一行的在同一列上了
System.out.println("同一列，是否通过：" + queue8.judge(2));
/*
* . x . . . . . . // 计划放到这里
* . . x . . . . .
* x . . . . . . .
*/
queue8.array[2] = 1;
// 第一列不行，放置到第 2 列
// 这里与第 2 行的同一斜列了，也是不行的
System.out.println("同一斜列，是否通过：" + queue8.judge(2));
}
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
输出结果如下
第 01 个结果 ：0 4 7 5 2 6 1 3
第 02 个结果 ：0 5 7 2 6 3 1 4
第 03 个结果 ：0 6 3 5 7 1 4 2
第 04 个结果 ：0 6 4 7 1 3 5 2
第 05 个结果 ：1 3 5 7 2 0 6 4
第 06 个结果 ：1 4 6 0 2 7 5 3
第 07 个结果 ：1 4 6 3 0 7 5 2
第 08 个结果 ：1 5 0 6 3 7 2 4
第 09 个结果 ：1 5 7 2 0 3 6 4
第 10 个结果 ：1 6 2 5 7 4 0 3
第 11 个结果 ：1 6 4 7 0 3 5 2
第 12 个结果 ：1 7 5 0 2 4 6 3
第 13 个结果 ：2 0 6 4 7 1 3 5
第 14 个结果 ：2 4 1 7 0 6 3 5
第 15 个结果 ：2 4 1 7 5 3 6 0
第 16 个结果 ：2 4 6 0 3 1 7 5
第 17 个结果 ：2 4 7 3 0 6 1 5
第 18 个结果 ：2 5 1 4 7 0 6 3
第 19 个结果 ：2 5 1 6 0 3 7 4
第 20 个结果 ：2 5 1 6 4 0 7 3
第 21 个结果 ：2 5 3 0 7 4 6 1
第 22 个结果 ：2 5 3 1 7 4 6 0
第 23 个结果 ：2 5 7 0 3 6 4 1
第 24 个结果 ：2 5 7 0 4 6 1 3
第 25 个结果 ：2 5 7 1 3 0 6 4
第 26 个结果 ：2 6 1 7 4 0 3 5
第 27 个结果 ：2 6 1 7 5 3 0 4
第 28 个结果 ：2 7 3 6 0 5 1 4
第 29 个结果 ：3 0 4 7 1 6 2 5
第 30 个结果 ：3 0 4 7 5 2 6 1
第 31 个结果 ：3 1 4 7 5 0 2 6
第 32 个结果 ：3 1 6 2 5 7 0 4
第 33 个结果 ：3 1 6 2 5 7 4 0
第 34 个结果 ：3 1 6 4 0 7 5 2
第 35 个结果 ：3 1 7 4 6 0 2 5
第 36 个结果 ：3 1 7 5 0 2 4 6
第 37 个结果 ：3 5 0 4 1 7 2 6
第 38 个结果 ：3 5 7 1 6 0 2 4
第 39 个结果 ：3 5 7 2 0 6 4 1
第 40 个结果 ：3 6 0 7 4 1 5 2
第 41 个结果 ：3 6 2 7 1 4 0 5
第 42 个结果 ：3 6 4 1 5 0 2 7
第 43 个结果 ：3 6 4 2 0 5 7 1
第 44 个结果 ：3 7 0 2 5 1 6 4
第 45 个结果 ：3 7 0 4 6 1 5 2
第 46 个结果 ：3 7 4 2 0 6 1 5
第 47 个结果 ：4 0 3 5 7 1 6 2
第 48 个结果 ：4 0 7 3 1 6 2 5
第 49 个结果 ：4 0 7 5 2 6 1 3
第 50 个结果 ：4 1 3 5 7 2 0 6
第 51 个结果 ：4 1 3 6 2 7 5 0
第 52 个结果 ：4 1 5 0 6 3 7 2
第 53 个结果 ：4 1 7 0 3 6 2 5
第 54 个结果 ：4 2 0 5 7 1 3 6
第 55 个结果 ：4 2 0 6 1 7 5 3
第 56 个结果 ：4 2 7 3 6 0 5 1
第 57 个结果 ：4 6 0 2 7 5 3 1
第 58 个结果 ：4 6 0 3 1 7 5 2
第 59 个结果 ：4 6 1 3 7 0 2 5
第 60 个结果 ：4 6 1 5 2 0 3 7
第 61 个结果 ：4 6 1 5 2 0 7 3
第 62 个结果 ：4 6 3 0 2 7 5 1
第 63 个结果 ：4 7 3 0 2 5 1 6
第 64 个结果 ：4 7 3 0 6 1 5 2
第 65 个结果 ：5 0 4 1 7 2 6 3
第 66 个结果 ：5 1 6 0 2 4 7 3
第 67 个结果 ：5 1 6 0 3 7 4 2
第 68 个结果 ：5 2 0 6 4 7 1 3
第 69 个结果 ：5 2 0 7 3 1 6 4
第 70 个结果 ：5 2 0 7 4 1 3 6
第 71 个结果 ：5 2 4 6 0 3 1 7
第 72 个结果 ：5 2 4 7 0 3 1 6
第 73 个结果 ：5 2 6 1 3 7 0 4
第 74 个结果 ：5 2 6 1 7 4 0 3
第 75 个结果 ：5 2 6 3 0 7 1 4
第 76 个结果 ：5 3 0 4 7 1 6 2
第 77 个结果 ：5 3 1 7 4 6 0 2
第 78 个结果 ：5 3 6 0 2 4 1 7
第 79 个结果 ：5 3 6 0 7 1 4 2
第 80 个结果 ：5 7 1 3 0 6 4 2
第 81 个结果 ：6 0 2 7 5 3 1 4
第 82 个结果 ：6 1 3 0 7 4 2 5
第 83 个结果 ：6 1 5 2 0 3 7 4
第 84 个结果 ：6 2 0 5 7 4 1 3
第 85 个结果 ：6 2 7 1 4 0 5 3
第 86 个结果 ：6 3 1 4 7 0 2 5
第 87 个结果 ：6 3 1 7 5 0 2 4
第 88 个结果 ：6 4 2 0 5 7 1 3
第 89 个结果 ：7 1 3 0 6 4 2 5
第 90 个结果 ：7 1 4 2 0 6 3 5
第 91 个结果 ：7 2 0 5 1 4 6 3
第 92 个结果 ：7 3 0 2 5 1 6 4
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
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
一定要理解它这个 回溯 机制，比如拿其中这两个来分析
第 06 个结果 ：1 4 6 0 2 7 5 3
第 07 个结果 ：1 4 6 3 0 7 5 2
1
2
2
- 从第 1 行，到最后的第 8 行，这时 n+1 进入到第 9 行，发现已经放完 8 个皇后了，拿到一个完整的结果，
- 就返回到第 8 行的那个方法中，因为第 8 行放置结果是 3，那么回到这里来的时候，就会尝试第 4 列的结果
- 从结果来看，肯定不满足，就一直会尝试直到，第 8 行的 3 变成 7，这个 check 方法尝试完了，都没有出一个结果，就自动退出这个方法
- 回到了第 7 行的第 5 列这个结果上，又继续尝试
- 从结果上来看，回到了第 4 行上，将 0 变成了 3，才发现这个位置与之前的不冲突，然后往下，进入到第 5 个皇后的放置上
- 依次类推
其实这里递归的原理就是穷举法一样的思想，挨个的尝试，直到把所有的可能都尝试完。
有一个 细节需要知道，这里的 不同行、不同列、不同斜列，不要求非连续的，也就是说，即使不是连续的斜列也算
x . . . . . . .
. . . . . . . .
. . x . . . . .
这样不连续的斜列，也算是在一条斜线上。一定要明白这个规则，才能使用那个判定斜列的算法
1
2
3
4
2
3
4
# 小节
重点 1 ：判定是否在棋盘是符合规则：是否是同一列、同一行、同一斜列
这里使用一维数组，来保存二维数组中的点的位置，使用如下的算法，来检验这个规则
/* 如果他们的摆放位置一样，说明是在同一列 x .... x .... */ array[i] == array[n] /* 检测是否是同一斜列 下标: 代表的是第几行 值：代表的是第几列 . x . . . n = 1,value = 1 x . . . . i = 0,value = 0 Math.abs(n - i) = 1 Math.abs(array[n] - array[i]) = 1 . . x . . n = 1,value = 2 . x . . . i = 0,value = 1 Math.abs(n - i) = 1 Math.abs(array[n] - array[i]) = 1 */ || Math.abs(n - i) == Math.abs(array[n] - array[i])1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21重点 2：递归的回溯流程，一定要明白是怎么回溯的