#include "stdafx.h"
#include "queen.h"

int step[64];//64是最大的棋盤大小，step儲存了每一列上皇后的行號
int current;
int count;


void displayQueen(int n){
	count++;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==step[j])
				printf("%c ",char(1));
			else
				printf("%c ",char(2));
		}
		printf("\n");
	}
	printf("\n");
}

//皇后位置合法判定
bool putQueenOK(int l){
	int up,down;
	up = down = l;
	for(int i=current-1;i>=0;i--){
		up--;
		down++;
		int cur = step[i];//當前列皇后位置
		if(cur==l||cur==up||cur==down)
			return false;
	}
	return true;

}
//主遞歸算法
void mainQueen(int _n){
	//遞歸結束條件
	if (current>_n)
		return;

	int i;
	for(i=0;i<_n;i++){
		if(putQueenOK(i)){
			step[current] = i;
			if(current==_n-1){
				displayQueen(_n);
				current--;
				return;
			}
			current++;
			mainQueen(_n);
		}
	}
	current--;
}



//主程序，事實上用來接收n，n表示皇后問題的規模
void queen(int n){
	current=0;
	count =0;
	mainQueen(n);
	printf("共有%d種布局\n",count);
	printf("按任意鍵結束");
	getchar();
}