八皇后问题。
思路:
这是个经典的递归问题。八皇后问题不允许任意两个皇后在同一行、同一列以及同一对角线。因为不允许同一列,我们只需要一个一维数组保存第i行皇后所在的列即可,例如c[r]表示第r行皇后所在的列。设任意两行r1, r2,不满足的条件的情况有:c[r1] == c[r2],c[r1] - c[r2] == r1 - r2,c[r1] - c[r2] == r2 - r1。从第0行开始放置皇后,依次递归,终止条件为r == 8。这个思想可以直接扩展到n皇后问题。
#include <iostream> #include <vector> using namespace std; bool Check(vector<int>& ivec, int r) { for (int i = 0; i < r; ++i) { if ((ivec[i] - ivec[r] == i - r) || (ivec[i] - ivec[r] == r - i) || ivec[i] == ivec[r]) return false; } return true; } void Queen(vector<int>& ivec, int r, int n) { if (r == n) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (ivec[i] == j) cout << "1 "; else cout << "0 "; } cout << endl; } return; } for (int i = 0; i < n; ++i) { ivec[r] = i; if (Check(ivec, r)) Queen(ivec, r + 1, n); } } void main() { int n = 8; vector<int> ivec(n); Queen(ivec, 0, n); }