/*
	これはできるだけ多くのポーンを一直線上に3つ以上並ばないようにするプログラムです。
	gcc chess2.c としてコンパイルし。./a.outとすることで実行できます。
	実行すると条件を満たす盤面が、ポーンがある位置を1、空マスを0として表示します。
	
	プログラムの説明。

	レポートで証明した、条件を満たすとき一行につきポーンが2コマあるという事実を用いてプログラムを作りました。

	盤面の状態は64bit unsigned long int型のデータに記録します。
	下からiビット目が1のとき、その盤面のi/8行i%8列にポーンが存在すると考えます。
	
	まず始めにまだ条件を満たす盤面の半分、条件を満たす盤面全体ともに一つも見つかっていないので 、
	関数initでグローバル変数n4とn_findedを0に初期化します。

	次にmake_one_rowで条件を満たす盤面の1行だけを作ります。
	つまり、一行にポーンが2つあるときの置き方（28通り）を全て探します。
	そして、見つかったものは配列one_row[]に記録します。

	次に関数make_two_row()で条件を満たす盤面の連続する2行を作ります。
	つまり、make_one_row()で作った置き方を2つつなげた盤面を全て探します。
	そして、見つかったものは配列two_row[]に記録します。

	次に関数make_four_row()で条件を満たす盤面の連続する4行を作ります。
	つまり、make_two_row()で作った置き方を2つつなげます。
	そしてそれらの盤面の中でその4行の中で3つが直線上に並ばないかどうかチェックします。
	そのチェックする関数がcheck()です。

	次にchange_four_row()で、作成した盤面の4行分の配列four_row[]の操作します。
	配列four_row[]に記録されている盤面は半分だけなので、残りの半分にすでにある半分
	の盤面によってポーンをおいてはいけないことが分かる位置を1とします。
	つまり、元からある半分での1とはポーンがあることを示しますが、
	後から加えた半分での1とはポーンをおいてはいけないことを示します。

	次に関数make_eight_row()で盤面全体を作成します。
	four_row[]に含まれている盤面のうち一つをとって関数reverse()で点対称な盤面をつくります。
	そしてその盤面と他の盤面の同じところが1になっていないか調べます。
	同じところが1になっていた場合はその盤面は条件を満たさないので、条件を満たすものを探します。
	条件を満たす盤面が見つかったら、関数yet_finded()で対称な盤面が既に見つかっていないか調べます。
	見つかっていない場合は関数save_status()で配列findedに記録します。

	最後に条件を満たす盤面全て（対称なものは一つだけ）を表示します。
*/

#include <stdio.h>

unsigned long int one_row[28];//可能な一行を記録します。
unsigned long int two_row[28 * 28];// 可能な連続する二行を記録します。
unsigned long int four_row[784 * 784];// 可能な連続する4行を記録します。
unsigned long int finded[100];//発見した条件を満たす盤面を記憶します。
int n4;// 配列four_rowに含まれる盤面の数
int n_finded;// 配列findedに含まれる盤面の数

//グローバル変数を初期化します。
void init()
{
	n4 = 0;
	n_finded = 0;
}

// 盤面を表示する関数です。
void print_status(unsigned long int status)
{
	int i;
	printf("\n---------------------\n");
	for(i = 0; i < 64; i++)
	{
		if(i && i % 8 == 0) puts("");
		printf("%d ", ((int) (status & ((unsigned long int)1))));
		status = status >> 1;
	}
	printf("\n---------------------\n");
}

// 1行に2コマある1行だけの盤面を全てつくります。
void make_one_row()
{
  	int i, j, n = 0;
	for(i = 0; i < 7; i++)
	{
		for(j = i + 1; j < 8; j++)
		{
			one_row[n] = (((unsigned long int )1) << i) | (((unsigned long int )1) << j);
			n++;
		}
	}
}

// make_one_rowで作った盤面を組み合わせて連続する二行を作ります。
void make_two_row()
{
	int i, j;
	for(i = 0; i < 28 * 28 ; i++)
	{
		//作成した1行をずらして、もう一行とくっつけます。
		two_row[i] = (one_row[i / 28] << 8) | one_row[i % 28];
	}
}

// make_four_rowで作成する連続する4行が条件を満たすか調べます。
// 条件を満たす場合に1を、満たさない場合に0を返します。
int check(unsigned long int status)
{
	unsigned long int row[4], sub_row[4];
	int i, j;
	// 配列sub_rowにstatusを一行ごとに取り出します。
	// ですので、関数make_two_rowやmake_four_rowには無駄があります。
	for(i = 0; i < 4; i++)
	{
		sub_row[i] = (((status >> (8 * i)) & ((unsigned long int)0xFF)));
	}
	// 任意の3行をずらしてビット和を取ることで同一直線上に3コマ存在しないか調べます。
	for(i = -3; i <= 3; i++) 
	{
		for(j = 0; j < 4; j++)
		{
			row[j] = (sub_row[j] << (i * ((i >= 0)? j: j-3)));
		}
		if((row[0] & row[1] & row[2])) return 0;
		if((row[1] & row[2] & row[3])) return 0;
		if((row[0] & row[1] & row[3])) return 0;
		if((row[0] & row[2] & row[3])) return 0;
	}
	return 1;
}

//条件を満たす連続する4行をつくります。
void make_four_row()
{
	int i, j;
	for(i = 0; i < 784; i++)
	{
		for(j = 0; j < 784; j++)
		{
			// 作成した2行をずらして他の2行とくっつけます。
			unsigned long int tmp = (two_row[i] << 16) | two_row[j];
			// この連続する4行が条件を満たすか調べ、満たすなら記録します。
			if(check(tmp))
			{
				four_row[n4] = tmp;
				n4++;
			}
		}
	}
}

// 入力された盤面をプログラムの冒頭に書いたように変えます。
unsigned long int sub_change_four_row(unsigned long int status)
{
	int i, j, k, m, d;
	unsigned long int row[4], tmp1, tmp2;
	// 一行一行とりだします。
	for(i = 0; i < 4; i++)
	{
		row[i] = ((status >> (8 * i)) & ((unsigned long int)0xFF));
	}
	// j行目とj + k行目のにあるコマでできる直線を探します。
	// そしてその直線上で盤面の下半分である位置を1とします
	for(j = 0; j < 4; j++)	
	{
		for(k = 1; j + k < 4; k++)
		{
			tmp1 = (row[j] & row[j + k]);
			// 同じ列にふたコマある場合tmp1は0以外の数になります。
			// その列にはもう置けません。
			if(tmp1)
			{
				for(i = 4; i < 8; i++)
				{
					status = (status | (tmp1 << 8 * i));
				}
			}
			// 同じ直線上に2つコマがある場合その列にはもう置けません。
			for(m = 1; m <= ((k == 1)? 3: 6); m++) 
			{
				if(m != 5)
				{
					tmp1 = (row[j] & (row[j + k]) << m);
					for(i = 4; i < 8; i++)
					{
						if((m * (i - j)) % k == 0)
						{
							d = m * (i - j) / k;
							tmp2 = (tmp1 >> d);
							if(!tmp2) break;
							status = (status | (tmp2 << 8 * i));
						}
					}
					tmp2 = ((row[j] << m) & row[j + k]);
					for(i = 4; i < 8; i++)
					{
						if((m * (i - j - k)) % k == 0)
						{
							d = m * (i - j - k) / k;
							tmp1 = ((tmp2 << d) & ((unsigned long int)0xFF));
							if(!tmp1) break;
							status = (status | (tmp1 << 8 * i));
						}
					}
				}
			}
		}
	}
	return status;
}

// 作成した4行をプログラムの冒頭に書いた仕方で変形します。
void change_four_row()
{
	int i;
	for(i = 0; i < n4; i++)
	{
		four_row[i] = sub_change_four_row(four_row[i]);
	}
}

// 盤面を中心点について対称に移したものを返す関数です。
unsigned long int reverse(unsigned long int status)
{
	unsigned long int re_status = 0;
	int i;

	for(i = 0; i < 64; i++)
	{
		re_status = (re_status << 1) + (status & ((unsigned long int) 1));
		status = status >> 1;
	}

	return re_status;
}

int sub_yet_finded(unsigned long int status)
{
	int i = 0;
	while(i < n_finded && finded[i] != status) i++;
	return i < n_finded;
}

// 入力された盤面と対称な盤面がすでに見つかっているかどうかを調べる関数です。
int yet_finded(unsigned long int status)
{
	int i;
	unsigned long int sub_status[8];
	for(i = 0; i < 8; i++)
	{
		sub_status[i] = 0;
	}
	for(i = 0; i < 64; i++)
	{
		// 対称（もしくは同じ）8つの盤面を作成します。
		if(((status >> i) & ((unsigned long int) 1)))
		{
			sub_status[0] = (sub_status[0] | (((unsigned long int)1) << i));
			sub_status[1] = (sub_status[1] | (((unsigned long int)1) << ((i / 8) + (i % 8) * 8)));
			sub_status[2] = (sub_status[2] | (((unsigned long int)1) << ((7 - i / 8) * 8 + (i % 8))));
			sub_status[3] = (sub_status[3] | (((unsigned long int)1) << ((7 - i/ 8) + (i % 8) * 8)));
			sub_status[4] = (sub_status[4] | (((unsigned long int)1) << ((i / 8) * 8 + (7 - i % 8))));
			sub_status[5] = (sub_status[5] | (((unsigned long int)1) << ((i / 8) + (7 - i % 8) * 8)));
			sub_status[6] = (sub_status[6] | (((unsigned long int)1) << ((7 - i / 8) * 8 + (7 - i % 8))));
			sub_status[7] = (sub_status[7] | (((unsigned long int)1) << ((7 - i / 8) + (7 - i % 8) * 8)));			
		} 
	}
	// 既に見つかっていた場合1を返し、見つかっていなかった場合0を返します。
	for(i = 0; i < 8; i++)
	{
		if(sub_yet_finded(sub_status[i])) return 1;
	}
	return 0;
}

// 盤面を配列n_findedに記録します。
void save_status(unsigned long int status)
{
	finded[n_finded] = status;
	n_finded++;
}

// 条件を満たす盤面全体を作ります。
void make_eight_row()
{
	int i, j;
	unsigned long int tmp, status;
	for(i = 0; i < n4; i++)
	{
		tmp = reverse(four_row[i]);
		for(j = i; j < n4; j++)
		{
			// 同じ所にビットが立っていなければ条件を見たします。
			if(!(tmp & four_row[j]))
			{
				// 上半分と下半分をくっつけます。
				status = (tmp & ((unsigned long int)0xFFFFFFFF00000000)) | (four_row[j] & ((unsigned long int)0xFFFFFFFF));
				// 既に見つかっていない場合は記録します。
				if(!yet_finded(status)) 
				{
					save_status(status);
				}
			}
		}
	}
}

int main()
{
	int i;
	// グローバル変数を初期化します。
	init();
	// 一行つくります。
	make_one_row();
	// 連続する2行をつくります。
	make_two_row();
	// 連続する4行をつくる。
	make_four_row();
	// 作成した4行を冒頭に書いたように変えます。
	change_four_row();
	// 条件を満たす盤面全体をつくります。
	make_eight_row();
	// 見つかった条件を満たす盤面を表示します。
	for(i = 0; i < n_finded; i++)
	{	
		print_status(finded[i]);
	}
	// 条件を満たす盤面が全部でいくつ見つかったのか表示します。
	printf("number of finded status: %d\n", n_finded);
	return 0;
}