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.0038 sec