N 皇后问题:
- #include <iostream>
- #include <cmath>
- using namespace std;
- int N;
- int queenPos[100];// 用来存放算好的皇后位置. 最左上角是 (0,0)
- void NQueen(int k);
- int main()
- {
- cin>> N;
- NQueen(0); // 从第 0 行开始摆皇后
- return 0;
- }
- void NQueen(int k) // 在 0~k-1 行皇后已经摆好的情况下, 摆第 k 行及其后的皇后
- {
- int i;
- if (k == N) // N 个皇后已经摆好
- {
- for (i = 0; i <N; i++)
- cout << queenPos[i] + 1 << " ";
- cout << endl;
- return;
- }
- for (i = 0; i < N; i++)// 逐一尝试第 k 个皇后所在的列 i.
- {
- int j;
- for (j = 0; j < k; j++)
- {
- // 和已经摆好的 k 个皇后的位置比较, 看是否冲突
- //queenPos[j] == i 表示第 j 个皇后所在的列 queenPos[j] 与第 k 个皇后所在的列 i 相等
- //abs(queenPos[j] - i) == abs(k-j) 表示第 k 个皇后和第 j 个皇后在同一个斜线 (行之差与列之差绝对值相等)
- if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))
- {
- break; // 冲突, 则试下一个位置
- }
- }
- if (j == k) // 当前选的位置 i 不冲突
- {
- queenPos[k] = i; // 将第 k 个皇后摆放在第 i 列
- NQueen(k + 1);
- }
- } //for( i = 0;i < N;i ++ )
- }
2N 皇后:
- #include<iostream>
- #include<math.h>
- using namespace std;
- #define N 100
- int wq[N]; //whitequeen, 黑皇后位置
- int bq[N]; //blackqueen, 白皇后位置
- int cb[N][N]; //chessboard, 棋盘
- int num; // 皇后数目
- int count = 0; // 不同放置情况计数
- int bqueen(int pos) // 黑色皇后放置
- {
- int i;
- for (i = 0; i <pos - 1; i++)
- {
- int judge = bq[i] - bq[pos - 1];
- if (0 == judge || abs(judge) == abs(pos - 1 - i))
- return 0;
- }
- if (pos == num)
- {
- ::count++;
- return 0;
- }
- for (int i = 0; i < num; i++)
- {
- if (i != wq[pos] && cb[pos][i])
- {
- bq[pos] = i;
- bqueen(pos + 1);
- }
- }
- }
- int wqueen(int pos) // 白色皇后放置
- {
- int i;
- for (i = 0; i < pos - 1; i++)// 处理之前置入的皇后, 判断是否冲突, 冲突就返回, 同时貌似放在这边还能使递归能返回, 很巧妙, 博主我只是搬运
- {
- int judge = wq[i] - wq[pos - 1];
- if (0 == judge || abs(judge) == abs(pos - 1 - i ))
- return 0;
- }
- // 当前的 pos 意为已经有 pos 个放好了, 这次函数在处理 pos+1 的调用
- if (pos == num)// 放满了才会调用
- {
- bqueen(0);
- return 0;
- }
- for (int i = 0; i < num; i++)
- {
- if (cb[pos][i])// 该位置是否能放, 能放的话, 每一个都试一下, 如果不行, 会返回 0---- 当前不判断的是否能放, 由 N+1
- // 来查看 N 次是否能放, 不能放就会返回 0
- {
- wq[pos] = i;
- wqueen(pos + 1);
- }
- }
- }
- int main()
- {
- cin>> num;
- for (int i = 0; i <num; i++)
- for (int j = 0; j < num; j++)
- cin>> cb[i][j];
- wqueen(0);// 先白后黑
- cout << ::count;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2997341.html