#include <iostream> using namespace std; const int N=8; int x[9]; int num = 0; //统计解的个数 //输出一种布局 void print(int *p,int n){ int i,j; cout << num <<":\n"; for(i=1; i<=n; i++){ for(j=1; j<p[i]; j++) cout <<" - "; cout <<" Q "; for(j=p[i]+1; j<=n; j++) cout <<" - "; cout <<endl; } } //求解n皇后布局 void nQueens(int n){ int k=1; int j=1, flag=1; x[1]=0; while( k>0 ){ x[k]+=1; //转到下一行 while( x[k]<=n ){ //判断第k个皇后可否放在第x[k]列 j=flag=1; while( j<k && flag ){ if( x[j]==x[k] || (abs(x[j]-x[k])==abs(j-k)) ) flag=0; j++; } if( flag==1 ) //可放 break; //如果无解,最后一个皇后就会安排到格子外面去 x[k]+=1; } if( x[k]<=n ){ //第k个皇后仍被放置在格子内,有解 if( k==n ){ num++; print(x,N); //输出这种布局 }else{ k++; x[k]=0; //转到下一行 } }else //第k个皇后已经被放置到格子外了,没解,回溯 k--; //回溯 } } int main(){ nQueens(N); cout <<"共有" <<num <<"种布局方法。\n"; return 0; }
Standard input is empty
1: Q - - - - - - - - - - - Q - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - Q - - - - 2: Q - - - - - - - - - - - - Q - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - Q - - - 3: Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - - Q - - - - - Q - - - - - 4: Q - - - - - - - - - - - - - Q - - - - - Q - - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - - - 5: - Q - - - - - - - - - Q - - - - - - - - - Q - - - - - - - - - Q - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - 6: - Q - - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - 7: - Q - - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - - Q - - - - - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - 8: - Q - - - - - - - - - - - Q - - Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - Q - - - 9: - Q - - - - - - - - - - - Q - - - - - - - - - Q - - Q - - - - - Q - - - - - - - - - - Q - - - - - - - - - - Q - - - - - Q - - - 10: - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - Q - - - - - - - - - - Q - - - - 11: - Q - - - - - - - - - - - - Q - - - - - Q - - - - - - - - - - Q Q - - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - - - 12: - Q - - - - - - - - - - - - - Q - - - - - Q - - Q - - - - - - - - - Q - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - - 13: - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - Q - - 14: - - Q - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - Q Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - Q - - 15: - - Q - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - Q - Q - - - - - - - 16: - - Q - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - 17: - - Q - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - Q - - - - - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - 18: - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - - - - - - - - - Q Q - - - - - - - - - - - - - Q - - - - Q - - - - 19: - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - Q - - - - - - - - - - Q - - - - - - - - - - - Q - - - - Q - - - 20: - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - - - - - Q - - - Q - - - - - - - - - - - - - - Q - - - Q - - - - 21: - - Q - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - Q - - Q - - - - - - 22: - - Q - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - Q - Q - - - - - - - 23: - - Q - - - - - - - - - - Q - - - - - - - - - Q Q - - - - - - - - - - Q - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - - 24: - - Q - - - - - - - - - - Q - - - - - - - - - Q Q - - - - - - - - - - - Q - - - - - - - - - Q - - Q - - - - - - - - - Q - - - - 25: - - Q - - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - 26: - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - - - - - Q - - - - Q - - - Q - - - - - - - - - - Q - - - - - - - - - Q - - 27: - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - Q - - - - - - - - - - - Q - - - 28: - - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - - 29: - - - Q - - - - Q - - - - - - - - - - - Q - - - - - - - - - - Q - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - 30: - - - Q - - - - Q - - - - - - - - - - - Q - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - - 31: - - - Q - - - - - Q - - - - - - - - - - Q - - - - - - - - - - Q - - - - - Q - - Q - - - - - - - - - Q - - - - - - - - - - - Q - 32: - - - Q - - - - - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - - - - - - - - Q Q - - - - - - - - - - - Q - - - 33: - - - Q - - - - - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - Q - - - - - - - 34: - - - Q - - - - - Q - - - - - - - - - - - - Q - - - - - Q - - - Q - - - - - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - 35: - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - - Q - - 36: - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - Q - - - - - - - - - Q - - - - - - - - - Q - - - - - - - - - Q - 37: - - - Q - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - Q - - Q - - - - - - - - - - - Q - 38: - - - Q - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - Q - - - 39: - - - Q - - - - - - - - - Q - - - - - - - - - Q - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - - 40: - - - Q - - - - - - - - - - Q - Q - - - - - - - - - - - - - - Q - - - - Q - - - - Q - - - - - - - - - - - Q - - - - Q - - - - - 41: - - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - - 42: - - - Q - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - Q - - - - - - - - - - - - Q 43: - - - Q - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - 44: - - - Q - - - - - - - - - - - Q Q - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - - - - - Q - - - 45: - - - Q - - - - - - - - - - - Q Q - - - - - - - - - - - Q - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - - 46: - - - Q - - - - - - - - - - - Q - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - 47: - - - - Q - - - Q - - - - - - - - - - Q - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - - - - Q - - - Q - - - - - 48: - - - - Q - - - Q - - - - - - - - - - - - - - Q - - - Q - - - - - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - 49: - - - - Q - - - Q - - - - - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - Q - - - - 50: - - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - Q - - - - - - - - - Q - - Q - - - - - Q - - - - - - - - - - - - - Q - 51: - - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - - - - - Q - - Q - - - - - - - 52: - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - 53: - - - - Q - - - - Q - - - - - - - - - - - - - Q Q - - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - 54: - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - - Q - 55: - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - 56: - - - - Q - - - - - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - Q - - - - - - - - - - - - Q - - - Q - - - - - - 57: - - - - Q - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - Q - - - - - - 58: - - - - Q - - - - - - - - - Q - Q - - - - - - - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - Q - - - - - 59: - - - - Q - - - - - - - - - Q - - Q - - - - - - - - - Q - - - - - - - - - - - Q Q - - - - - - - - - Q - - - - - - - - - - Q - - 60: - - - - Q - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - Q - - - - - - - - - - - Q 61: - - - - Q - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - - - - - Q - - - Q - - - - 62: - - - - Q - - - - - - - - - Q - - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - - - - Q - - - - - Q - - - Q - - - - - - 63: - - - - Q - - - - - - - - - - Q - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - 64: - - - - Q - - - - - - - - - - Q - - - Q - - - - Q - - - - - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - - 65: - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - 66: - - - - - Q - - - Q - - - - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - 67: - - - - - Q - - - Q - - - - - - - - - - - - Q - Q - - - - - - - - - - Q - - - - - - - - - - - Q - - - - Q - - - - - Q - - - - - 68: - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - - - - - - - Q - Q - - - - - - - - - Q - - - - 69: - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - - - - - Q - - - Q - - - - - Q - - - - - - - - - - - - Q - - - - - Q - - - 70: - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - - - - - Q - - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - - Q - 71: - - - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - - Q - - - - - Q - - - - - - - - - - - - - Q 72: - - - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - - Q Q - - - - - - - - - - Q - - - - - Q - - - - - - - - - - - - Q - 73: - - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - Q - - - - - - - - - - - Q Q - - - - - - - - - - - Q - - - 74: - - - - - Q - - - - Q - - - - - - - - - - - Q - - Q - - - - - - - - - - - - - Q - - - - Q - - - Q - - - - - - - - - - Q - - - - 75: - - - - - Q - - - - Q - - - - - - - - - - - Q - - - - Q - - - - Q - - - - - - - - - - - - - - Q - Q - - - - - - - - - - Q - - - 76: - - - - - Q - - - - - Q - - - - Q - - - - - - - - - - - Q - - - - - - - - - - Q - Q - - - - - - - - - - - - Q - - - Q - - - - - 77: - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - 78: - - - - - Q - - - - - Q - - - - - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - Q 79: - - - - - Q - - - - - Q - - - - - - - - - - Q - Q - - - - - - - - - - - - - - Q - Q - - - - - - - - - - Q - - - - - Q - - - - - 80: - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - 81: - - - - - - Q - Q - - - - - - - - - Q - - - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - Q - - - 82: - - - - - - Q - - Q - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - Q - - 83: - - - - - - Q - - Q - - - - - - - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - Q - - - - - - - - - - - Q - - - - Q - - - 84: - - - - - - Q - - - Q - - - - - Q - - - - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - - Q - - - - - - - - - Q - - - - 85: - - - - - - Q - - - Q - - - - - - - - - - - - Q - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - - - - - Q - - - - 86: - - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - Q - - - - - - - - - - Q Q - - - - - - - - - Q - - - - - - - - - - Q - - 87: - - - - - - Q - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - Q - - - - - - - - - Q - - - - - - - - - Q - - - 88: - - - - - - Q - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - Q - - - - - - - - - Q - Q - - - - - - - - - Q - - - - 89: - - - - - - - Q - Q - - - - - - - - - Q - - - - Q - - - - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - Q - - 90: - - - - - - - Q - Q - - - - - - - - - - Q - - - - - Q - - - - - Q - - - - - - - - - - - - - Q - - - - Q - - - - - - - - - Q - - 91: - - - - - - - Q - - Q - - - - - Q - - - - - - - - - - - - Q - - - Q - - - - - - - - - - Q - - - - - - - - - Q - - - - Q - - - - 92: - - - - - - - Q - - - Q - - - - Q - - - - - - - - - Q - - - - - - - - - - Q - - - Q - - - - - - - - - - - - Q - - - - - Q - - - 共有92种布局方法。