八皇后问题(N皇后问题)的回溯法求解
一、问题描述
在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互攻击,求出所有的布棋方法,并推广到N皇后情况。
二、参考资料
啥文字都不用看,B站上有个非常详细的动画视频解说,上链接!!!
三、源代码
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
|
#include<iostream> #include<vector> #include<string> using namespace std; void put_queen( int x, int y, vector<vector< int >>&attack) { //实现在(x,y)放置皇后,对attack数组更新,xy表示放置皇后的坐标,attack表示是否可以放置皇后 //方向数组,方便后面对8个方向进行标记 static const int dx[] = { -1,-1,-1,0,0,1,1,1 }; static const int dy[] = { -1,0,1,-1,1,-1,0,1 }; attack[x][y] = 1; //将皇后位置标记为1 //通过两层for循环,将该皇后可能攻击到的位置标记 for ( int i = 1; i < attack.size(); i++) //从皇后位置向1到n-1个距离延伸 { for ( int j = 0; j < 8; j++) //遍历8个方向 { int nx = x + i * dx[j]; //生成的新位置行 int ny = y + i * dy[j]; //生成的新位置列 //在棋盘范围内 if (nx >= 0 && nx < attack.size() && ny >= 0 && ny < attack.size()) attack[nx][ny] = 1; //标记为1 } } } //回溯算法 //k表示当前处理的行 //n表示n皇后问题 //queen存储皇后的位置 //attack标记皇后的攻击范围 //solve存储N皇后的全部解法 void backtrack( int k, int n, vector<string>& queen, vector<vector< int >>& attack, vector<vector<string>>& solve) { if (k == n) //找到一组解 { solve.push_back(queen); //将结果queen存储至solve return ; } //遍历0至n-1列,在循环中,回溯试探皇后可放置的位置 for ( int i = 0; i < n; i++) { if (attack[k][i] == 0) //判断当前k行第i列是否可以放置皇后 { vector<vector< int >> tmp = attack; //备份attack数组 queen[k][i] = 'Q' ; //标记该位置为Q put_queen(k, i, attack); //更新attack数组 backtrack(k + 1, n, queen, attack, solve); //递归试探k+1行的皇后的位置 attack = tmp; //恢复attack数组 queen[k][i] = '.' ; //恢复queen数组 } } } vector<vector<string>>solveNQueens( int n) { //string存储具体的摆放位置,<vector<string>>存放一种解法,二维vector存放全部解法 vector<vector<string>>solve; //存储最后结果 vector<vector< int >>attack; //标记皇后的攻击位 vector<string>queen; //保存皇后位置 //使用循环初始化attack和queen数组 for ( int i = 0; i < n; i++) { attack.push_back((vector< int >())); for ( int j = 0; j < n; j++) { attack[i].push_back(0); } queen.push_back( "" ); queen[i].append(n, '.' ); } backtrack(0, n, queen, attack, solve); return solve; //返回结果数组 } int main() { //int num; //cin >> num;//输入皇后数 初始化attack数组 //vector<vector<int>> attack(num,vector<int>(num, 0)); 初始化queen数组 //string s; //for (int i = 0; i < num; i++)s += '.'; //vector<string> queen(num, s); int n; cin >> n; vector<vector<string>>result; result = solveNQueens(n); cout << n << "皇后共有" << result.size() << "种解法" << endl; for ( int i = 0; i < result.size(); i++) { cout << "解法" << i + 1 << ":" << endl; for ( int j = 0; j < result[i].size(); j++) { cout << result[i][j] << endl; } cout << endl; } system ( "pause" ); return 0; } |
四、测试结果
四皇后
八皇后
到此这篇关于C语言回溯法解八皇后问题的文章就介绍到这了。希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/qq_51462776/article/details/122162381