LeetCode面试题 08.12. 八皇后---回溯算法解决N皇后问题(C++实现）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode面试题 08.12. 八皇后---回溯算法解决N皇后问题(C++实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2171字，纯文字阅读大概需要4分钟。
内容图文
N皇后问题源于著名的八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法！
将8x8扩展为NxN即为N皇后问题，要解决此问题，最简单的方法就是暴力枚举，此时的时间复杂度为N^2，回溯算法与简单暴力枚举类似，不同点在于当判定某种状态不符合答案时，便不再继续枚举此状态的后续状态，而是回溯到该状态之前，继续遍历其他的可能值。
1 #include <iostream>
2 #include <vector>
3 #include <string>
4usingnamespace std;
5 6bool check(const vector<vector<int>> &vec, int row, int col, int n)
7{
8// 检查列冲突 9for (int i = 0; i < n; i++)
10 {
11if (vec[i][col] == 1)
12returnfalse;
13 }
1415// 检查左上对角线16for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
17 {
18if (vec[i][j] == 1)
19returnfalse;
20 }
21for (int i = row + 1, j = col + 1; i < n &&j < n; i++, j++)
22 {
23if (vec[i][j] == 1)
24returnfalse;
25 }
2627// 检查左下对角线28for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
29 {
30if (vec[i][j] == 1)
31returnfalse;
32 }
33for (int i = row + 1, j = col - 1; i < n&&j >= 0; i++, j--)
34 {
35if (vec[i][j] == 1)
36returnfalse;
37 }
3839returntrue;
40}
4142void findQueen(vector<vector<int>> &vec, int row, int n, vector<vector<string>> &res)
43{
44if (row == n)
45 {
46 vector<string> queenResult;
47for (auto &i : vec)
48 {
49string str;
50for (auto j : i)
51 {
52if (j == 1)
53 str += ‘O‘;
54else55 str += ‘+‘;
56 }
57 queenResult.push_back(str);
58 }
59 res.push_back(queenResult);
60 }
6162for (int col = 0; col < n; col++)
63 {
64// 回溯65if (check(vec, row, col, n))
66 {
67 vec[row][col] = 1;
68 findQueen(vec, row + 1, n, res);
69 vec[row][col] = 0; // 遍历下一列时，将当前列重置70 }
71 }
72}
7374// N皇后75 vector<vector<string>> NQueen(int n)
76{
77 vector<vector<int>> vec(n, vector<int>(n, 0));
78 vector<vector<string>> res;
79 findQueen(vec, 0, n, res);
80return res;
81}
8283int main()
84{
85 auto res = NQueen(8);
86for (int i = 0; i < res.size(); i++)
87 {
88 cout << "result " << i << ":" << endl;
89for (auto &s : res[i])
90 cout << s << endl;
91 }
92return0;
93 }
原文：https://www.cnblogs.com/hl249853856/p/15171963.html
内容总结
以上是互联网集市为您收集整理的LeetCode面试题 08.12. 八皇后---回溯算法解决N皇后问题(C++实现）全部内容，希望文章能够帮你解决LeetCode面试题 08.12. 八皇后---回溯算法解决N皇后问题(C++实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。