#include<iostream> #include<vector> using namespace std; #define MAXNUM 10 int tot=0,row,line[MAXNUM],n=8; void search(int row) //递归搜索可行解 { int i,j; if(row==n) tot++; //当row=n时,说明每一行的皇后都不冲突,即为可行解 else for(i=0;i<n;i++) { int ok=1; line[row]=i; //尝试把第row行的皇后放在i列上 for(j=0;j<row;j++) //检验是否与前面已放好的皇后冲突 { if(line[row]==line[j] || line[row]-line[j] ==row - j || line[j]-line[row] == row -j) { ok=0; break; //如果冲突,停止搜索,返回上一级递归回溯。回溯法高效的关键。 } } if(ok) search(row+1); } } const int N = 8; //递归版 int cnt = 0; void dfs(int layer, int col, int left, int right) { if(N == layer) { cnt++; return; } int tmp = ~(col | left | right);//按位取反不是! for(int i = 0; i < N; i++) { if(tmp & (1 << i))//是&不是&& { int t1 = col|(1<<i), t2 = ( left|(1<<i) ) >> 1, t3 = ( right|(1<<i) ) << 1; //dfs(layer + 1, col&(1<<i), ( left&(1<<i) ) << 1, ( right&(1<<i) )>>1); dfs(layer + 1, t1, t2, t3); } } } int main() { tot = 0; n = 8; search(0); cout << tot << endl; dfs(0,0,0,0); cout << cnt << endl; system("pause"); return 0; }