算法与分析课程_回溯算法_拼题网_习题2_N皇后_C++

2 八皇后问题
在国际象棋中，皇后是最厉害的棋子，可以横走、直走，还可以斜走。棋手马克斯·贝瑟尔 1848 年提出著名的八皇后问题：即在 8 × 8 的棋盘上摆放八个皇后，使其不能互相攻击 —— 即任意两个皇后都不能处于同一行、同一列或同一条斜线上。例如：

现在我们把棋盘扩展到 n×n 的棋盘上摆放 n 个皇后，请问该怎么摆？

请编写程序，输入正整数 n，输出全部摆法（棋盘格子空白处显示句点“.”，皇后处显示字母“Q”，每两个字符之间空一格）。

输入格式
正整数 n(n>0)

输出格式
若问题有解，则输出全部摆法（每两种摆法之间空一行）。
若问题无解，则输出 None。

要求：试探的顺序按从上到下逐行进行，其中每一行按从左到右的逐格进行，请参看输出样例2。

输入样例1

3

输出样例1

None

输入样例2

6

输出样例2

. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .. . Q . . .
. . . . . Q
. Q . . . .
. . . . Q .
Q . . . . .
. . . Q . .. . . Q . .
Q . . . . .
. . . . Q .
. Q . . . .
. . . . . Q
. . Q . . .. . . . Q .
. . Q . . .
Q . . . . .
. . . . . Q
. . . Q . .
. Q . . . .

代码:

#include
#include
#include
using namespace std;
class Solution {
public:vector<vector<string>> solveNQueens(int n) {auto solutions = vector<vector<string>>();//方案数组auto queens = vector<int>(n, -1);auto columns = unordered_set<int>();//用于行重复判断//用于斜线重复判断auto diagonals1 = unordered_set<int>();auto diagonals2 = unordered_set<int>();backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);toString(solutions);return solutions;}void backtrack(vector<vector<string>>& solutions, vector<int>& queens, int n, int row, unordered_set<int>& columns, unordered_set<int>& diagonals1, unordered_set<int>& diagonals2) {if (row == n) {vector<string> board = generateBoard(queens, n);solutions.push_back(board);}else {for (int i = 0; i < n; i++) {if (columns.find(i) != columns.end()) {continue;}int diagonal1 = row - i;if (diagonals1.find(diagonal1) != diagonals1.end()) {continue;}int diagonal2 = row + i;if (diagonals2.find(diagonal2) != diagonals2.end()) {continue;}queens[row] = i;columns.insert(i);diagonals1.insert(diagonal1);diagonals2.insert(diagonal2);backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);queens[row] = -1;columns.erase(i);diagonals1.erase(diagonal1);diagonals2.erase(diagonal2);}}}vector<string> generateBoard(vector<int>& queens, int n) {auto board = vector<string>();for (int i = 0; i < n; i++) {string row = string(n, '.');row[queens[i]] = 'Q';board.push_back(row);}return board;}void toString(vector<vector<string>>& solutions) {if (solutions.empty())cout << "None" << endl;else {for (vector<string> tmp: solutions) {for (string str : tmp) {for (int i=0;i<str.size();i++){cout << str.at(i);if (i != str.size()-1)cout << " ";}cout << endl;}if(tmp!= solutions.back())cout << endl;}}}
};
int main() {int n;cin >> n;Solution A;A.solveNQueens(n);system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！