/*
	これは盤面に8つのクイーンがあるときにクイーンから攻撃されないマスが
	できるだけ多くなるようにするプログラムです。

	gcc chess3.cとすることでコンパイルし、./a.outで実行してください。
	実行すると空きマスが11個以上ある盤面が全て表示されます。
	まず、空きマスの数が"empty:N"のNに表示さます。
	次にその時のクイーンのマスを1、それ以外のマスを0とした盤面が表示されます。
	次にクイーンから攻撃されないマスを0、それ以外を1とした盤面が表示されます。
*/
#include <stdio.h>

int queens[8];// クイーンをどこに配置するか示す。
int queens_flag;  // クイーンの置き方をひと通り全て試したかを示す。
int rows[2];// クイーンが存在しない行
int rows_flag;// クイーンが存在しない行の選び方をひと通り試したか
int cols[4];//クイーンが存在しない列
int cols_flag;
int status[8][8];//今調べている配置でのクイーンの位置
int status2[8][8];// 今調べている配置でのクイーンが攻撃できる位置
unsigned long int finded[1000];// 今まで見つけた条件を満たす配置
int n_finded;// 配列findedに含まれている配置の数。

// グローバル変数n_findedを0に初期化し、findedに0をいれる
void init_finded()
{
	int i;
	n_finded = 0;
	for(i = 0; i < 1000; i++)
	{
		finded[i] = 0;
	}
}

// クイーンの配置を初期化する
void init_status()
{
	int i, j;
	for(i = 0; i < 8; i++)
	{
		for(j = 0; j < 8; j++)
		{
			status[i][j] = 0;
			status2[i][j] = 0;
		}
	}
}

// クイーンが存在しない行、列を抜かして、クイーンがどこに存在するか
// 例えば21であれば、5行目の1列目（0から数える）にクイーンがあることを示す。
void init_queens()
{
	int i;
	queens_flag = 1;
	for(i = 0; i < 8; i++)
	{
		queens[i] = 7 - i;
	}
}

//クイーンが存在しない行を初期化する
void init_rows()
{
	int i;
	rows_flag = 1;
	for(i = 0; i < 4; i ++)
	{
		rows[i] = i;
	}
}

// クイーンが存在しない列を初期化する
void init_cols()
{
	int i;
	cols_flag = 1;
	for(i = 0; i < 4; i ++)
	{
		cols[i] = 3 - i;
	}
}

// クイーンの位置を新しくする
void next_queens()
{
	int i = 0;
	while(i < 8)
	{
		if(queens[i] == 23 - i) i++;
		else break; 
	}

	if(i == 8){
		queens_flag = 0;
	}
	else
	{
		queens[i]++;
		for(;i >0;i--) 
		{
			queens[i - 1] = queens[i]+1;
		}
	}
}

//クイーンが存在しない行を新しくする
void next_rows()
{
	if(rows[0] == 3 && rows[1] == 4)
	{
		rows_flag = 0;
	}
	else if(rows[1] == 7 - rows[0])
	{
		rows[0]++;
		rows[1] = rows[0]+1;
	}
	else
	{
		rows[1] ++;
	}
}

// クイーンが存在しない列を新しくする。
void next_cols()
{
	
	int flag = 0;
	while(1)
	{
		int i = 0;
		while(i < 4)
		{
			if(cols[i] == 7 - i) i++;
			else break; 
		}

		if(i == 4){
			cols_flag = 0;
			break;
		}
		else
		{
			cols[i]++;
			for(;i >0;i--) 
			{
				cols[i - 1] = cols[i]+1;
			}
		}

		while(i < 4)
		{
			if(cols[i] <= 7 - cols[3-i]) break;
			i++;
		}

		if(cols[0] + cols[3] < 7  || (cols[0] + cols[3] == 7 && cols[1] + cols[2]<= 7)) break;
	}	
}

// クイーンが存在しない行と列があることを考えて配列queensからクイーンの位置を定める 
void make_status()
{
	int i, j;
	int rows_hash[6], cols_hash[4];
	for(i = 0; i < 6; i++)
	{
		int n = 0;
		for(j = 0; j < 2; j++)
		{
			if(rows[j] <= i + n) n++;
		}
		rows_hash[i] = i + n;
	}
	

	for(i = 0; i < 4; i++)
	{
		int n = 0;
		for(j = 0; j < 4; j++)
		{
			if(cols[3 - j] <= i + n) n++;
		}
		cols_hash[i] = i + n;
	}
	int r, c;
	for(i = 0; i < 8; i++)
	{
		c = cols_hash[queens[i] % 4];
		r = rows_hash[queens[i] / 4];
		// 現在のクイーンの配置を定める。
		status2[c][r] = 1;
		// クイーンの位置とクイーンが攻撃できる位置。
		for(j = 0; j < 8; j++)
		{
			status[c][j] = 1;
			status[j][r] = 1;
		}
		int tmp_c, tmp_r;
		for(tmp_c = c, tmp_r = r; 0 <= tmp_c && 0 <= tmp_r; tmp_c--, tmp_r--)
		{
			status[tmp_c][tmp_r] = 1;			
		}
		for(tmp_c = c, tmp_r = r; 0 <= tmp_c && tmp_r < 8; tmp_c--, tmp_r++)
		{
			status[tmp_c][tmp_r] = 1;			
		}
		for(tmp_c = c, tmp_r = r; tmp_c < 8 && 0 <= tmp_r; tmp_c++, tmp_r--)
		{
			status[tmp_c][tmp_r] = 1;			
		}
		for(tmp_c = c, tmp_r = r; tmp_c < 8 && tmp_r < 8; tmp_c++, tmp_r++)
		{
			status[tmp_c][tmp_r] = 1;			
		}
	}
}

// 空きマスを探す
int empty_point()
{
	int n = 0;
	int i, j;
	for(i = 0; i < 8; i++)
	{
		for(j = 0; j < 8; j++)
		{
			if(!status[i][j]) n++;
		}
	}
	return n;
}

// 現在の盤面を表示する
void print_status()
{
	int i, j;
	for(i = 0; i < 8; i++)
	{
		for(j = 0; j < 8; j++)
		{
			printf("%d ", status2[i][j]);
		}
		puts("");
	}
	puts("");
	for(i = 0; i < 8; i++)
	{
		for(j = 0; j < 8; j++)
		{
			printf("%d ", status[i][j]);
		}
		puts("");
	}
	puts("");
}

// 現在の盤面を記録する
// 盤面はunsigned long int 型で記録し、同時に対称な盤面も記録する。
void save_status()
{
	int i, j;
	for(i = 0; i < 8; i++)
	{
		for(j = 0; j < 8; j++)
		{
			if(status2[i][j])
			  {
				finded[n_finded] = finded[n_finded] |  (((unsigned long int)1) << (8 * i + j)); 
				finded[n_finded + 1] = finded[n_finded + 1] |  (((unsigned long int)1) << (8 * i + (7 - j)));
				finded[n_finded + 2] = finded[n_finded + 2] |  (((unsigned long int)1) << (8 * (7 - i) + j)); 
				finded[n_finded + 3] = finded[n_finded + 3] |  (((unsigned long int)1) << (8 * (7 - i) + (7 - j))); 
				finded[n_finded + 4] = finded[n_finded + 4] |  (((unsigned long int)1) << (8 * j + i)); 
				finded[n_finded + 5] = finded[n_finded + 5] |  (((unsigned long int)1) << (8 * j + (7 - i)));
				finded[n_finded + 6] = finded[n_finded + 6] |  (((unsigned long int)1) << (8 * (7 - j) + i)); 
				finded[n_finded + 7] = finded[n_finded + 7] |  (((unsigned long int)1) << (8 * (7 - j) + (7 - i))); 
			}
		}
	}
	n_finded = n_finded + 8;
}

// 今の盤面が今までに記録されているか調べる。
int check()
{
	int i ,j;
	unsigned long int int_status = 0;
	for(i = 0; i < 8; i++)
	{
		for(j = 0; j < 8; j++)
		{
			if(status2[i][j]) {
				int_status = int_status |  ((unsigned long int)1 << (8 * i + j)); 
			}
		}
	}
	i = 0;
	for(; i < n_finded; i++)
	{
		if(finded[i] == int_status) break;
	}
	return i == n_finded;
}

void solve()
{
	int n = 0, m;
	int n_queen = 0, n_cols, n_rows;
	init_queens();
	init_finded();
	while(queens_flag)
	{
		n_cols = 0;
		init_cols();
		while(cols_flag)
		{
			n_rows = 0;
			init_rows();
			while(rows_flag)
			{
				init_status();
				make_status();
				m = empty_point();
				if(m > 10 && check())
				{
					save_status();
					printf("empty:%d\n",m);
					print_status();
				}
				n++;
				next_rows();
				n_rows++;
			}
			next_cols();
			n_cols++;
		}
		next_queens();
		n_queen++;
	}
}

int main()
{
	solve();
	return 0;
}