8queen.cpp

// 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);
}