八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。 该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。 1854年在柏林的象棋杂志上不同的作者发表了40种不同的解。 后来有人用图论的方法解出92种结果。 现在给出n皇后问题的代码 #include<iostream> using namespace std; int total = 0; int n; int* n_queens; void print() { for(int i=0;i<n;i++) { for(int j=0;j<n_queens[i];j++) { cout<<"0"; } cout<<"1"; for(int j=n_queens[i]+1;j<n;j++) { cout<<"0"; } cout<<endl; } cout<<"****************************"<<endl; } bool check(int queen_i, int pos_i)//第queen_i个皇后，在第pos_i列 { int i, pos; for(i=0;i<queen_i;i++)//只需要查看前面的皇后 { pos = n_queens[i];//在同一列 if(pos_i==pos) return false; if((queen_i+pos_i)==(i+pos))//在右下角 return false; if((queen_i-pos_i)==(i-pos))//在左下角 return false; } return true; } void my_queens(int i)//第i个皇后 { for(int pos=0;pos<n;pos++)//在第pos列 { if(check(i,pos)) { n_queens[i] = pos; if(i == n-1) { total++; print(); n_queens[i] = 0; return; } my_queens(i+1);//找下一个皇后的位置 n_queens[i] = 0;//回溯，这个皇后继续寻找新位置 } } } int main() { cout<<"Please enter the number of queens."<<endl; cin>>n; n_queens = new int[n]; my_queens(0); if(total==0) cout<<"There is no way."<<endl; else if(total==1) cout<<"There is only one way."<<endl; else cout<<"There are "<<total<<" ways."<<endl; return 0; } 运行后可以发现当n为1或大于3的时候才有解。