#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define frand()((double)rand()/(RAND_MAX+1))
#define NP 8
#define NUM 100
#define LOOP 10
#define miniFit 0.1  //最低適応度
#define Cross   0.3  //交叉率
#define Mutation 0.3 //#突然変異率(この問題の場合，大きめで良い)
#define SelectRate  1 - (Cross + Mutation)//選択率
#define MAXR   100
double Prob[3];
void setProb(){//■選択，交叉，突然変異を選ぶための累積度数作成
	Prob[0] = SelectRate;
	Prob[1] = Prob[0] + Cross;
	Prob[2] = 1;
}
void genUnit(int Unit[]) {//■染色体の生成
	Unit[0] = int(frand() * NP);
	for (int i = 1; i < NP; i++) {
		int flag = true;
		while (flag) {//同一遺伝子がないように生成
			Unit[i] = int(frand() * NP); flag = false;
			for (int k = 0; k < i; k++)
				if (Unit[i] == Unit[k]) { flag = true; break; }
		}
	}
}
void copyUnit(int Data[], int Unit[]) {//■遺伝子コピー
	for (int i = 0; i < NP; i++) Data[i] = Unit[i];
}
void genData(int Data[][NP]) {//■データの生成
	int Unit[NP];
	for (int i = 0; i < NUM; i++) {
		genUnit(Unit);copyUnit(Data[i], Unit);
	}
}
void printGINI(int Unit[]) {//■遺伝子の表示
	for (int i = 0; i < NP; i++) printf("%3d", Unit[i]);
}
int notAll(int DT[]) {//■N王妃が各行の各桁にあるかを検査
	int CH[NP]; for (int i = 0; i < NP; i++)CH[i] = 0;
	for (int i = 0; i < NP; i++) CH[DT[i]] = 1; 
	for (int i = 0; i < NP; i++)
		if (CH[i] == 0) return 1;
	return 0;
}
void chessBoard(int DT[], int CH[][NP]) {//■チェス盤の生成
	for (int i = 0; i < NP; i++)
		for (int j = 0; j < NP; j++)CH[i][j] = 0;
	for (int i = 0; i < NP; i++)CH[i][DT[i]] = 1;
}
void printBoard(int CH[][NP]) {//■チェス盤を表示
	printf("\n       ●がクイーンの位置\n");
	for (int i = 0; i < NP; i++) {
		printf("\n       ");
		for (int j = 0; j < NP; j++)
			if (CH[i][j] == 0) printf("□"); else printf("●");
	}
	printf("\n    ");
}
void printBoard(int DT[]) {//■位置指定によるチェス盤表示
	int CH[NP][NP]; chessBoard(DT, CH);
	printBoard(CH);
}
int eightQueen(int DT[]) {//■斜め方向のチェック
	int CH[NP][NP]; chessBoard(DT, CH);
	int j1, j2, k; int NN = NP - 1;
	for (int i = 0; i < NP; i++) {
		j1 = DT[i] - i; j2 = NP; k = 0; //右下がり斜めチェック
		if (j1 < 0) { k = -j1; j2 += j1; j1 = 0; }
		for (int j = j1; j < j2; j++, k++) {
			if (j != DT[i] && CH[k][j] != 0)return true;
		}
		j1 = DT[i] + i; j2 = -1; k = 0;//右上がり斜めチェック
		if (j1 > NN) { k = j1 - NN; j2 += k; j1 = NN; }
		for (int j = j1; j > j2; j--, k++) {
			if (j != DT[i] && CH[k][j] != 0)return true;
		}
	}
	return false;
}
double elmFit(int DT[]) {//#■適応度を求める(TSP問題)
	if (notAll(DT)) return miniFit;
	if (eightQueen(DT)) return 0.5;//斜め方向不可の場合，交叉, 突然変異
	return 1.0;                    //で最適解に移行する可能性あり。
}
void setFitness(int Data[NUM][NP], double Fitness[]) {//#■適応度計算
	for (int i = 0; i < NUM; i++) Fitness[i] = elmFit(Data[i]);
}
double totalFitness(double FitNess[]) {//#■全適応度合計
	double T = 0;
	for (int i = 0; i < NUM; i++) T += FitNess[i];
	return T;
}
void cumDisp(double Fitness[], double cDisp[]) {//■適応度の累積分布生成
	double D[NUM], T; T = totalFitness(Fitness);
	for (int i=0; i<NUM; i++)D[i]=Fitness[i]/T;
	cDisp[0] = D[0];
	for (int i=1; i<NUM; i++)cDisp[i]=cDisp[i-1]+D[i];
}
//-----------(遺伝子処理)-----------------
int selectUnit(double CDisp[]) {//■選択
	double R = frand();
	for (int i = 0; i < NUM; i++)
		if (R < CDisp[i])return i;
	return NUM-1;//ありえないが便宜上設定
}
void twoPointProc(int A[], int B[], int AA[], int BB[]) {//■2点交叉
	int S = int(frand() * NP), E = int(frand() * NP);
	for (int i = 0; i < NP; i++) {
		if (i >= S && i <= E) { AA[i] = B[i]; BB[i] = A[i]; }
		else { AA[i] = A[i]; BB[i] = B[i]; }
	}
}
void uniformCross(int A[], int B[], int AA[], int BB[]) {//■一様交叉
	for (int i = 0; i < NP; i++) {
		if (A[i] == B[i] || frand() < 0.5) {
			AA[i] = A[i]; BB[i] = B[i];
		}
		else { AA[i] = B[i]; BB[i] = A[i]; }
	}
}
void crossProc(int A[], int B[], int method, int AA[], int BB[]) {//■交叉処理選択
	if (method) return twoPointProc(A, B, AA, BB);
	return uniformCross(A, B, AA, BB);
}
void mutationProc(int A[], int AA[]) {//■突然変異
	int S1 = int(frand() * NP);
	int S2 = int(frand() * NP);
	for (int i = 0; i < NP; i++) {
		if (i == S1) AA[i] = A[S2];
		else if (i == S2) AA[i] = A[S1];
		else AA[i] = A[i];
	}
}
void printGene(int k, int DT[], double FT) {//■遺伝子表示
	printf("\n %4d:", k);
	for (int i = 0; i < NP; i++)printf("%3d", DT[i]);
	printf("  適応度 = %8.4f",FT);

}
void printDT(int Data[][NP]){//, double Fitness[]) {//■データ表示
	double Fitness[NUM];
	setFitness(Data, Fitness);
	for (int i = 0; i < NUM; i++)
		printGene(i, Data[i], Fitness[i]);
}
void printResult(double* MX, int* NUMDT, int numG[][NP], 
				 int Data[][NP], double Fitness[], 
				 int Debug) {//■結果表示
	int i, NL; setFitness(Data, Fitness); double MXD = Fitness[0];
	for (i = 1; i < NUM; i++)//最大適応度を求める
		if (Fitness[i] > MXD) MXD = Fitness[i];
	NL = 0;//最大適応度の染色体を取り出す
	for (i = 0; i < NUM; i++) {
		if (fabs(Fitness[i] - MXD) < 0.000001) {
			copyUnit(numG[NL], Data[i]);
			if (Debug)printGene(i, Data[i], Fitness[i]);
			NL++;
		}
	}
	*MX = MXD; *NUMDT = NL;
}
void GA(int nLOOP, double * MX,int* NUMDT,
	    int numG[NUM][NP],int Debug) {//■GAメイン
	int Data[2][NUM][NP]; double Fitness[NUM];
	double CDisp[NUM];int cID = 0; int nID = 1 - cID;
	genData(Data[nID]);
	if (Debug) {//初期値の表示
		printf("\n初期値"); printDT(Data[nID]);
		printf("\n適応度の高い遺伝子");
		printResult(MX, NUMDT, numG, Data[nID], Fitness, Debug);
	}
	for (int i = 0; i < nLOOP; i++) {//ループ回数繰返し
		cID = nID; nID = 1 - cID;
		for (int k = 0; k < NUM; k++)
			copyUnit(Data[nID][k], Data[cID][k]);
		setFitness(Data[cID], Fitness);//適応度を求める
		cumDisp(Fitness, CDisp);//適応度の累積度数
		int k = 0;
		while (k < NUM) {//
			double R = frand();
			int S1 = selectUnit(CDisp);
			if (R < Prob[0]) {//選択
				copyUnit(Data[nID][k], Data[cID][S1]);
				k += 1;
			}
			else if (R < Prob[1]) {
				if (k == NUM - 1) {//最後なら「選択」とみなす
					copyUnit(Data[nID][k], Data[cID][S1]);
					k++;
				}
				else {// #交差(組み換え)
					int S2 = selectUnit(CDisp);
					crossProc(Data[cID][S1], Data[cID][S2], true,
						Data[nID][k], Data[nID][k + 1]); //■交叉処理選択
					k += 2;
				}
			}
			else {//突然変異
				mutationProc(Data[cID][S1], Data[nID][S1]);
				k++;
			}
		}
	}
	cID = nID;
	if (Debug) {
		printf("\n結果"); 
		printDT(Data[cID]);
		printf("\n適応度の高い遺伝子");
	}
	printResult(MX, NUMDT, numG, Data[cID], Fitness, Debug);
}
int equalUnit(int A[], int B[]) {//染色体の遺伝子構成が等しいかを検査
	for (int i = 0; i < NP; i++)
		if (A[i] != B[i]) return false;
	return true;
}
int inList(int RX[][NP],int ptR,int numG[NP]) {//表に同一染色体があるかを検査
	for (int k = 0; k < ptR; k++) {
		if (equalUnit(RX[k], numG)) return false;
	}
	return true;
}
void loopGA(int ALOOP, int ULOOP) {//■再初期設定の繰返し
	double MX = -999, MXG; 
	int ptR = 0, RX[MAXR][NP], NUMDT, numG[NUM][NP];
	for (int i = 0; i < ALOOP; i++) {
		GA(ULOOP, &MXG, &NUMDT, numG, false);
		if (MXG == MX) {
			for (int j = 0; j < NUMDT; j++) {
				if (inList(RX,ptR,numG[j])) {
					if (ptR < MAXR) copyUnit(RX[ptR++], numG[j]);
				}
			}
		}
		else if (MXG > MX) {
			MX = MXG; ptR = 0;
			for (int j = 0; j < NUMDT; j++)
				if (inList(RX, ptR, numG[j])) 
					if (ptR < MAXR) copyUnit(RX[ptR++], numG[j]);
		}
	}
	for (int i = 0; i < ptR; i++) {//最終表示
		printGene(i, RX[i], MX);
		printBoard(RX[i]);
	}
}
//---------(全体メイン)--------------
int main() {
	setProb(); loopGA(100, 15);
	getchar(); return 0;
}