// 8王妃問題 Eight Queen
 
 #include <iostream>
 #include <iomanip>
 
 using namespace std;
 
 #define N 8
 
 // 盤面
 int b[N][N];
 
 // 盤面表示
 void printBoard()
 {
 	static int kai=0;
 	
 	cout << "soved " << ++kai << endl;
 	for(int j=0; j<N; j++){
 		for(int i=0; i<N; i++){
 			cout << setw(2) << b[i][j];
 		}
 		cout << endl;
 	}
 } 
 
 // queenを置いていく
 void search(int n)
 {
 	// 8行目まで終わった場合、解が見つかった
 	if(n==N){
 		printBoard();
 		return;
 	}else{
 		//(i,n)に対して調べる
 		for(int i=0; i<N; i++){
 			//queenを数える
 			int sum=0;
 			for(int j=0; j<N; j++){
 				sum+=b[i][j]; // 縦方向
 				if(i+j<N && n+j<N){
 					sum+=b[i+j][n+j]; //右下
 				}
 				if(i-j>=0 && n-j>=0){
 					sum+=b[i-j][n-j]; //左上2
 				}
 				if(i-j>=0 && n+j<N){
 					sum+=b[i-j][n+j]; //左下
 				}
 				if(i+j<N && n-j>=0){
 					sum+=b[i+j][n-j]; //右上
 				}
 			}
 			if(sum==0){
 				b[i][n]=1;
 				search(n+1);
 			}
 			b[i][n]=0;
 		}
 	}
 }
 
 main()
 {
 	// 初期化
 	for(int j=0; j<N; j++){
 		for(int i=0; i<N; i++){
 			b[i][j]=0;
 		}
 	}
 	//探索
 	search(0);
 }