N-여왕말 문제... N-Queen Problem

 어쩌면 이번 학기 이 과목의 마지막 과제가 될지도 모르는 과제가 나왔다. 되추적(Backtracking) 방법을 얘기 할 때 가장 많이 거론 되는 듯한 N-여왕말(N-Queen) 문제이다. 어떤 문제인가하면 서양 장기(Chess:이후 체스)의 여왕말(Queen:이후 퀸)을 서로가 서로의 이동경로가 아닌 위치에 있도록 최대한 많은 퀸을 체스판 위에 놓는 문제이다.

  원래 체스판은 8ⅹ8이지만 간단히 4ⅹ4일 경우에 좌측의 결과와 같이 되는 경우를 찾는 것이 바로 N-Queen 문제 이다.
 4ⅹ4일 경우에는 좌측과 같은 2가지의 경우만 나오지만 체스판이 커지면 커질수록 다양한 경우의 수가 나온다. 우선 정해진 것은 NⅹN의 체스판에 올라갈 수 있는 퀸의 최대 갯수는 언제나 N이 된다는 점이다.

 그렇다면 어째서 이것이 되추적(Backtracking) 방법이 되느냐 하는 것은
첫번째 퀸(1, 1) 위치에 오게 될 경우
두번째 퀸은 (2, 3) 과 (2, 4) 위치에 올 수 있다. 우선 (2, 3) 위치에 퀸을 놓는다면
세번째 퀸을 놓을 수 있는 자리는 없어진다. 그러면 다시 로 돌아가서 두번째 퀸(2, 4) 위치에 놓게 되면
세번째 퀸(3, 2) 위치에 놓을 수 있지만 이렇게 되면 네번째 퀸을 놓을 수가 없어진다. 그렇게 되면 이번엔 다시 로 돌아가서 첫번째 퀸(1, 2)에 놓고 다시 시작한다.

 위의 과정과 같이 결과값을 찾아가다가 그 방법이 아니라는 것을 알았을 때 이전 단계로 돌아가는 것이 바로 되추적 방법이다.

 N-Queen의 문제의 경우 참고 자료에 있는 책을 본다면 좀 더 쉽게 알 수 있을 것이다. 언제나와 같이 나는 참고자료에 있는 'Foundations of Algorithms.....' 책을 참고로 해서 프로그램을 작성하였다.
 N값을 입력 받아서 결과를 보여주는 N-여왕말 문제 알고리즘
#include <stdio.h>
#include <malloc.h>
#include <math.h>

void queens(int i, int n, int col[]); // n개 여왕말 알고리즘
void printqueen(int n, int col[]); // n개 여왕말의 위치 출력
int promising(int i, int col[]); // 유망한지 검사하는 함수

int main()
{
int i;
int n;
int* col;

printf("How many Columns or Rows?\n> ");
scanf("%d", &n);
getchar();

// 여왕말이 해당행의 몇번째 열에 있는지 저장
col = (int*) malloc(sizeof(int)*n);

// 뿌리 노드(0)부터 탐색을 시작
queens(0, n, col);

free(col);

return 0;
}

void queens(int i, int n, int col[])
{
int j;

if (promising(i, col)) // 유망한가?
if (i == n) // n개의 여왕말 위치를 찾았나?
printqueen(n, col); // 여왕말 위치 출력
else
for(j = 1; j <= n; j++) { // (i+1)번째 행에 있는 여왕말을
col[i+1] = j; // n개의 열에 놓을 수 있는지 각각
queens(i+1, n, col); // 검사한다.
}
}

void printqueen(int n, int col[]) // 보기 편하게 결과값을 출력
{
int j, k;
printf(" |"); // 상단 열의 갯수 출력 부분
for(j = 1; j <= n; j++)
printf("%3d |", j);
printf("\n");

for(j = 0; j <= n; j++) // 행을 나누는 선 출력
printf("----+");
printf("\n");

for(j = 1; j <= n; j++) {
printf("%3d |", j); // 행의 번호
for(k = 1; k < col[j]; k++) {
if( ((k+j)%2) )
printf("▩▩|"); // 여왕말이 없는 칸
else
printf(" |"); // 여왕말이 없는 칸
}
printf("QUEE|"); // 여왕말
for(k = col[j]; k <n; k++)
if( !((k+j)%2) )
printf("▩▩|"); // 여왕말이 없는 칸
else
printf(" |"); // 여왕말이 없는 칸
printf("\n");

for(k = 0; k <= n; k++) // 행을 나누는 선 출력
printf("----+");
printf("\n");
}
printf("\n");

printf("Press ENTER to continue");
getchar(); // 결과 값이 많으므로 하나의 결과값마다 멈추도록
}

int promising(int i, int col[]) // 유망한지 판단하는 함수
{
int k;
int bSwitch;

k = 1;
bSwitch = 1;
while( k < i && bSwitch) {
/* col[i] == col[k] 는 같은 열에 있는지 판별한다
* abs(col[i] - col[k]) == i - k의 경우는
* 2개의 여왕말간의 행의 차와 열의 차의 절대값이 같으면
* 같은 대각선상에 있다는 의미이다. */
if(col[i] == col[k] || abs(col[i] - col[k]) == i-k)
bSwitch = 0;
k++;
}
return bSwitch;
}

결과는 다음과 같다.

나름대로 보기 좋게 출력하려고 노력했다. 경우의 수가 몇가지인지 출력하는 부분은 살짝 귀찮아서 생략했다.
    참고자료
  • 알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역
  • 누워서 읽는 알고리즘 - 임백준 저

by sakuragi | 2007/06/03 01:41 | :: R space :: 과제 | 트랙백(1) | 덧글(9)

트랙백 주소 : http://sakuragis.egloos.com/tb/3468837
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from appleparan's.. at 2009/04/07 04:42

제목 : 하늘바라기의 생각
자야지! PPT도 다했고, LISP 알고리즘도 찾았다 대각선 어떻게 할지 고민이었는데 ㅋㅋ...more

Commented by 환상경 at 2007/06/03 13:00
흐 부러워요 ㅠ.ㅠ
저도 그렇게 하드 트레이닝 받아보고 싶은데 ㅠ.ㅠ
Commented by sakuragi at 2007/06/06 21:39
환상경, ^^;; 이제 이 하드 트레이닝(?)도 끝입니다. 이제는 기말고사 준비를 T_T
Commented by ㅠㅠㅠㅠ at 2007/07/30 14:06
이거 소스 분석 좀 해주실래요...
3시간째 고민 중인데 머리가 나빠서 어떻게 돌아가는지 감이 안 잡힘 OTL
Commented by sakuragi at 2007/07/30 15:26
ㅠㅠㅠㅠ, 참고자료에 있는 이 책을 보시면 이해가 갈 껍니다.
"알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역"
Commented by Fury at 2009/03/09 18:45
http://cafe.naver.com/nilv/892 게시글로 퍼갑니다~ ;)
Commented by kokorida at 2012/11/09 20:42
우왐 포퀸 찾을려다 들어왔는데
혼자 생각해서 짤라니까 머리가 터질꺼 같은데 ..
이렇게 단순하다니.. 소스가 완전 깔끔하네요 ㅎㅎ

저기 저 검은색화면에 형광색으로 출력하는건 마크업언어 같은 걸로 하는건가요?
Commented by sakuragi at 2012/12/08 23:59
vim에서 syntax highlight를 켠 후에 : TOhtml 입력으로 html로 export 한 결과물입니다.
Commented by simons9989 at 2016/10/13 02:55
k = 1;
bSwitch = 1;
while( k < i && bSwitch) {

이조건은 도대체 왜 있는겁니까??
이해가 안가네 이게 왜 필요한지...퀸을 먼저 한자리에 박고 다른 자리를 비교해봐야 되는거 아닌가?ㅠㅠ
Commented by haha at 2017/05/15 09:48
현재의 행에대해서 그 윗부분의 행들을 모두 만족하는 것을 찾도록 설계해서 그렇지요~

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: