EightQueenProblem/임인택

n-Queen 모델에도 적용 가능합니다~

초기 구상

8bit == 1byte 라는 생각을 하고 비트연산만으로 할 수 있을것 같다는 생각을 하였다. 하지만 이 경우는 n-Queen 으로까지 확장하기까지 힘들고 간단한 index 로 값을 참조할수 있는 배열에 비해 비능률적인 방법이다. 단지 속도가 조금 빠를 것으로 믿었는데.. 빨라봤자 얼마나 빠르겠어.--;

나중에는..

recursive-call 을 이용하겠다는 생각이 퍼뜩 들었다. 역시 가장 문제가 되는 부분은 backtrack 하는 부분이었다.

구린점

처음에 시작 call 을 좀 이상하게 한다. loop 을 돌면서 첫번째 라인의 원소에 대한 get_Queen()함수를 호출한다. 생각에는 get_Queen(0,0); 처럼 호출하는게 가장 이상적이라고 생각하는데..--;

source code

#include <iostream.h>
#define QUEEN 8

int Queen[QUEEN][QUEEN]={0};
int total=0;
void print_result();
void reset(int fromline=0);
void get_Queen(int x, int y);
int check(int i, int j);


int main()
{
	for(int i=0; i<QUEEN; i++)
	{
		reset();
		get_Queen(i,0);
	}
	return 0;
}

void get_Queen(int x, int y)
{
	reset(y+1);
	Queen[x][y]=1;

	if(y==QUEEN-1) print_result();

	for(int i=0; i<QUEEN; i++)
		if(check(i,y+1))
			get_Queen(i,y+1);
	
	Queen[x][y]=0;
}


void print_result()
{
	int i,j;

	for(i=0; i<QUEEN; i++)
	{
		for(j=0; j<QUEEN; j++)
			cout << Queen[j][i] << "  ";
		cout << endl;
	}
	cin.get();
}

void reset(int fromline)
{
	int i,j;

	for(i=0; i<QUEEN; i++)
		for(j=fromline; j<QUEEN; j++)
			Queen[i][j]=0;
}

int check(int i, int j)
{
	if(i<0 || j<0 || i>=QUEEN || j>=QUEEN)
		return 0;

	int x, y, sum=0;

	for(y=j-1; y>=0 && sum==0; y--)	/* 위로 */
		sum+=Queen[i][y];
	for(x=i-1; x>=0 && sum==0; x--) /* 왼쪽으로 */
		sum+=Queen[x][j];
	for(x=i-1, y=j-1; x>=0 && y>=0 && sum==0; x--, y--) /* 대각선 */
		sum+=Queen[x][y];
	for(x=i+1, y=j-1; x<QUEEN && y>=0 && sum==0; x++, y--) /* 대각선 */
		sum+=Queen[x][y];

	return (int)(sum==0);
}