데이터 구조 와 알고리즘 노트 lesson 16 8 황후 문제

8 황후 문제
있다×8 칸 짜 리 체스 에 8 개의 황 후 를 배치 하여 서로 공격 할 수 없 게 한다. 즉, 임의의 두 황 후 는 같은 줄, 같은 열 또는 같은 사선 에 있 을 수 없 으 며 몇 가지 방법 이 있 는 지 물 어 본다.
 
#include
int count = 0;

int notDanger(int row, int j, int(*chess)[8])
{
	int i ,k,flag1=0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
	//             ,         1
	for (i = 0; i < 8; i++)
	{
		if (*(*(chess + i) + j) != 0)
		{
			flag1 = 1;
			break;
		}

	}
	//     
	for (i = row, k = j; i >= 0 && k >= 0; i--, k--)
	{
		if (*(*(chess + i) + k) != 0)
		{
			flag2 = 1;
			break;
		}
	}
	//     
	for (i = row, k = j; i <8 && k<8; i++, k++)
	{
		if (*(*(chess + i) + k) != 0)
		{
			flag3 = 1;
			break;
		}
	}
	//     
	for (i = row, k = j; i >=0&& k<8; i--, k++)
	{
		if (*(*(chess + i) + k) != 0)
		{
			flag4 = 1;
			break;
		}
	}
	//     
	for (i = row, k = j; i <8 && k>=0; i++, k--)
	{
		if (*(*(chess + i) + k) != 0)
		{
			flag5 = 1;
			break;
		}
	}
	if (flag1 || flag2 || flag3 || flag4 || flag5)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//row :       n:       (*chess)[8]:               
void EightQueen(int row, int n, int(*chess)[8])
{
	int chess2[8][8], i, j;
	for (i = 0; i < 0; i++)
	{
		for (j = 0; j < 8; j++)
		{
			chess2[i][j] = chess[i][j];
		}
	}

	if (8 == row)
	{
		printf(" %d 
", count + 1); for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { printf("%d", *(*(chess2 + i) + j));//chess[i][j] } printf("
"); } printf("
"); count++; } else { for (j = 0; j < n; j++) { if (notDanger(row,j,chess)) // { // , for (i = 0; i < 8; i++) { *(*(chess2 + row) + i) = 0; } *(*(chess2 + row) + j) = 1; EightQueen(row+1 , n, chess2); } } } } int main() { int chess[8][8], i, j; for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { chess[i][j] = 0; } } EightQueen(0,8,chess); printf(" %d
", count); return 0; }

좋은 웹페이지 즐겨찾기