U E D R , A S I H C RSS

Eight Queen Problem/이창섭

알고리즘

  • 임의의 한 점에 퀸을 놓고 그곳을 시발점으로 하여 공격할 대상이 없는 곳에 퀸을 놓아 퀸이 총 8개가 되면 출력하고 끝난다. 퀸이 8개가 되지 않으면 다시 임의의 점을 수정한다. 이 임의의 점은 모든 좌표를 돌며 정해진다.
    • 공격할 대상이 있는 가는 퀸의 놓을 위치에서 가로세로 대각선 방향으로 7칸씩 다른 퀸의 존재여부를 검사하는 것이다.
    • 배열의 넘어가서 검사하는 것을 막기위해 20 by 20 을 쓴다.

소스 원본

~cpp 
#include <iostream>
using namespace std;

int array[20][20] = {0,};

bool exam(int r, int c);
void output();
bool count();

int main()
{
	for (int r = 7; r <= 14; r++)
	{
		for (int c = 7; c <= 14; c++)
		{
			array[r][c] = 1;
			for (int i = 7; i <= 14; i++)
			{
				for (int j = 7; j <= 14; j++)
				{
					if (exam(i, j))
						array[i][j] = 1;
				}
			}
			if (count())
			{
				output();
				return 0;
			}
			else
			{
				for (int a = 0; a <= 19; a++)
					for (int b = 0; b <= 19; b++)
						array[a][b] = 0;
			}
		}
	}
	output();
	return 0;
}

bool exam(int r, int c)
{
	for (int i = 0; i <= 7; i++)
	{
		if (array[i+7][c] == 1 || array[r][i+7] == 1 || array[r+i][c+i] == 1 || array[r-i][c-i] == 1 || array[r-i][c+i] == 1 || array[r+i][c-i] == 1)
			return false;
	}
	return true;
}

void output()
{
	for (int i = 0; i <= 7; i++)
	{
		for (int j = 0; j <= 7; j++)
		{
			cout << array[i+7][j+7] << " ";
		}
		cout << "\n";
	}
}

bool count()
{
	int counter = 0;
	for (int i = 7; i <= 14; i++)
	{
		for (int j = 7; j <= 14; j++)
		{
			if (array[i][j] == 1)
				counter++;
		}
	}
	if (counter == 8)
		return true;
	else
		return false;
}

  • 지금 보니 무시무시한 소스다... 5중 루프... -_-;; --창섭

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:12
Processing time 0.0230 sec