nqueen hint

4 x 4 nqueen 문제를 생각해 보자.

위 그림은 가능한 한 가지 경우의 예이다.

col[ ] 배열에 2 4 1 3 으로 나타낸다. i 는 행 col[i] 는 열을 나타낸다.

방법 1

col[1] 1 을 놓은 후 , col[2] 에 1 은 같은 열이므로 안되고 , 2 는 대각선에 있으므로 안되고 , ....

팩토리얼 형태를 발생시키면서 가능하지 않는 경우에는 확장을 하지 않는다.

1 2 3 4
1 2 4 3
....

세가지 경우를 검사한다.

• 행 검사 : col[] 배열에는 수 하나만 들어가므로 같은행에 두개의 퀸이 올수는 없다.
• 열 검사 :col[i] = col[j]
• 대각 선 : i - j = 절대치(col[i]-col[j])
  • 북서쪽 대각선 체크

    

    이 대각선 성분은 행과 열이 동시에 1 씩 감소하는 하므로 j 는 i - k 이고 col[j] 는 col[i] - k 이다.

  • 북동쪽 대각선 체크

    

    이 쪽 대각선은 행은 하나씩 감소하고 , 열을 하나씩 증가하므로 j 는 i - k 이고 col[j] 는 col[i] + k 이다.

두 가지 경우를 모두 만족 시키기 위해서 i - j = abs( col[i] - col[j])

nqueen 소스▼

//col[i] 는 i 행의 열의 위치
//  
#include <stdio.h>
		
int n=4;
int col[100];

int promising(int m)
{
   int k;

   for(k=1;k < m;k++)
      if (col[k]==col[m] || abs(col[k]-col[m])== m-k)return 0;
   return 1;
}

void nqueen(int i)
{
   int j;

   if (promising(i)) 
      if (i==n) {
         for(j=1;j <= n;j++)
            printf("%d",col[j]); 
         printf("\n");
      }
      else
         for(j=1;j <= n;j++){
            col[i+1]=j;
            nqueen(i+1); 
         }
}

int main()
{
    nqueen(0);
    return 0;
}

방법 2 (조금 더 개선된 방법)

세 개의 배열을 이용한다.

• 열 체크 -- check[i] 수 i 가 사용하고 있으면 1 아니면 0
• 왼쪽 대각선 체크 -- 행,열을 빼면 같은수가 나오는 성질을 이용하
• 오른쪽 대각선 체크 -- 행,열을 더하면 같은 수가 나오는 성질을 이용함.

주의할 것은 왼쪽 대각선 체크시에 행과열을 빼는 경우 음수가 나올수 있으므로 뺀수에 일정한 수를 더해서 음수가 나오지 않도록 해야 함.(n * n nqueen 문제이면 n 을 더하면 아무리 작은 수가 나오더라도 음수가 나오지 않음)

nqueen 소스 ▼

/* 4 x 4  nqueen 구하는 프로그램 */
#include <stdio.h>
int col[5];
int check[5];
int ldia[20],rdia[20];

void  nqueen(int r)
{
	int i;

	if (r > 4){
		for(i=1;i<=4;i++){
			printf("%d ",col[i]);
		}
		printf("\n");
		return;
	}

	for(i=1;i <= 4;i++){
		if (check[i]==1 || ldia[i-r+4]==1 || rdia[i+r]==1) continue;
		check[i]=1;
		ldia[i-r+4]=1;
		rdia[i+r]=1;

		col[r]=i;
		nqueen(r+1);
		
		check[i]=0;
		ldia[i-r+4]=0;
		rdia[i+r]=0;
	}
}

int main()
{
	nqueen(1);
}

---

[홈으로]  [뒤 로]