7-3 N皇后问题 (20 分)
在N * N的方格棋盘上,放置N个皇后,要求每个皇后不同行,不同列,不同左右对角线。 其中N不超过10。 要求:输出所有的解。 算法提示:用栈求解皇后问题。
输入N
逐行输出每一种解,用每个皇后的位置坐标表示,每个位置坐标之后均有一个空格符,输出最后一行为空行。
在这里给出一组输入。例如:
6
在这里给出相应的输出。例如:
1: (1,2) (2,4) (3,6) (4,1) (5,3) (6,5)
2: (1,3) (2,6) (3,2) (4,5) (5,1) (6,4)
3: (1,4) (2,1) (3,5) (4,2) (5,6) (6,3)
4: (1,5) (2,3) (3,1) (4,6) (5,4) (6,2)
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<cmath> using namespace std; int a[12][12] = { 0 }, n, b[12][12] = { 0 }; void dfs(int x, int y) { int c[12][12] = { 0 }; b[x][y] = 1; if (x <= n && y <= n) { if (x == n && !a[x][y]) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (b[i][j] == 1) cout << i << " " << j << " "; cout << endl; } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if ((i == x || j == y || (abs(y - j) == abs(x - i)))&&(!a[i][j])) { a[i][j] = 1; c[i][j] = 1; } } for (int i = 1; i <= n; i++) if (!a[x + 1][i]) dfs(x + 1, i); } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (c[i][j]==1) a[i][j] = 0; } b[x][y] = 0; } int main() { cin >> n; for (int i = 1; i <= n; i++) { dfs(1, i); memset(a, 0, sizeof a); } }
思路:一开始去网上搜了一下如何判断斜角的方法,当前斜边的点等于当前的点竖边减去横边相等。然后在bfs和暴力枚举就可以算出
原文:https://www.cnblogs.com/pppyyyzzz/p/11644841.html