여왕말 문제(N queens problem)

문제

Eight Queens Problem : 8 x 8 의 판에 퀸 8개를 배치할 때 서로를 공격할 수 없게 배치하는 모든 경우의 판을 출력하시오.

아이디어

간단하게 생각해보면 퀸이 놓였을 경우, 또 다른 퀸을 놓을 수 없는 위치를 고려해보자.

하나의 퀸이 이동할 수 있는 경로는 퀸의 가로, 세로, 대각선, 역대각선 방향으로만 움직일 수 있다.

이를 그림을 통해 살펴보자. 

▣ : 퀸의 위치

▩ : 퀸이 이동할 수 있는 경로

□ : 퀸이 이동할 수 없는 경로

위에는 총 9개의 예시를 보이고 있다.

각각의 예시는 한개의 퀸 배치 때 퀸이 이동할 수 있는 경로와 이동할 수 없는 경로를 표현한다.

그렇다면 다음과 같이 생각하면 문제를 간단하게 해결할 수 있다.

다음과 같이 총 9 x 9  

81개의 배치가능 공간을 9개의 라인으로 나눈다.

1번 라인에 하나를 배치하게 된다면

이제 1번 라인에는 배치할 수 없고 다음 라인에 배치해야한다. (퀸은 세로로 이동가능하기 때문이다.)

1번 라인에 배치한 후, 다음 배치공간인 2번 라인에 배치하는데,

만약 2번의 첫번 째 라인에 배치한다면

1번라인의 퀸이 이동할 수있는 경로이기 때문에 2번라인에서 다음과 같은 배치가 불가능하다.

이와 같은 논리로 생각해보면

1번라인에서 첫번째 배치후 

2번라인에서 첫번째 배치가 된 경우는 

다음라인(3~9) 배치에 어떠한 퀸을 배치한다 해도 불가능한 경우가 되는 것이다.

그렇다면 위와 같이 배치된 경우는 다음라인에 어떠한 퀸을 배치한다 해도 불가능하기 때문에 

n queen문제의 적합하지 않은 경우이다.

이를 가능성없는 패라고 하는 데

유망성(Promising)이라고 부르겠다.

그렇다면 이렇게 유망성 없는 패는 더이상 체크할 가치가 없으며 체크하게 된다하면 이는 불필요한 연산일 것이다.

다음과 같이 X표시가 된곳은 더이상 다음 라인의 배치할 경우를 고려하지 않아도 되는 것이다.

이를 기반으로 생각해보면 재귀함수를 정의함으로써 다음과 같은 문제를 해결할 수 있다.

총 8개의 배치를 할경우 지속적으로 다음줄에 배치를 해가며, 

유망성없는 패일 경우는 고려하지않고 다음 배치를 생각하면서 체크하는 코드를 작성하면 된다.

이와 같은 알고리즘을 백트래킹(backtraking)이라고 한다.

그렇다면 다음 문제에서의 탈출조건을 고려해보자.

만약 8개의 배치중 총8개의 배치가 성립된 경우는 완전한 해이기 때문에 재귀 함수의 탈출 조건이된다.

소스코드

#include <stdio.h> #include <stdlib.h> #include <time.h> int cnt=0; int arr[8][8]={0,}; void showtable(void) { for(int i=0; i<8 ;i++) { for(int j=0; j<8; j++) { if(arr[i][j]==1) { printf("▩"); } else { printf("□"); } } printf("\n"); } } //특정 좌표에 퀸이 놓였을 경우, 퀸을 놓을 수 없는 위치를 표시하는 함수 void IsAble(int x, int y) { int data_arr[8][8] ={0,}; for(int i=0; i<8; i++) { data_arr[i][y] = 1; } for(int j=0; j<8; j++) { data_arr[x][j] = 1; } if(x>=y) { for(int i=0; i<8; i++) { for(int j=0; j<8; j++) { if(i-j == x-y) { data_arr[i][j] = 1; } } } } else { for(int i=0; i<8; i++) { for(int j=0; j<8; j++) { if(j-i == y-x) { data_arr[i][j] = 1; } } } } for(int i=0; i<8; i++) { for(int j=0; j<8; j++) { if(i+j == x+y) { data_arr[i][j] = 1; } } } printf("\n"); for(int i=0; i<8; i++) { printf(" "); for(int j=0; j<8; j++) { /* printf("%d ", data_arr[i][j]); */ if(data_arr[i][j] == 1) { if(i==x && j==y) { printf("▣"); } else{ printf("▩"); } } else { printf("□"); } } printf("\n"); } } int able(int x, int y) { //printf("\n\n호출:able(%d, %d) \n", x, y); //arr[n][depth] = 1; int i,j; int ret_num=1; // 행체크 (사실 행체크는 필요도 없음 로직이 행당 하나씩들어가게짬 허나 직관성을 위해서) for(i=0; i<8; i++) { if(arr[i][y]==1) { //사실은 여기서 return 0; 해버리면 더빠르나 디버깅을 위해서 //printf("행 체크에서 문제"); ret_num=0; } } // 열체크 for(j=0; j<8; j++) { if(arr[x][j]==1) { //사실은 여기서 return 0; 해버리면 더빠르나 디버깅을 위해서 //printf("열 체크에서 문제"); ret_num=0; } } // 대각선 체크(1) if(x>=y) { for(int i=0; i<8; i++) { for(int j=0; j<8; j++) { if(i-j == x-y) { if(arr[i][j] == 1) { //사실은 여기서 return 0; 해버리면 더빠르나 디버깅을 위해서 //printf("대각선 체크에서 문제"); ret_num=0; } } } } } else { for(int i=0; i<8; i++) { for(int j=0; j<8; j++) { if(j-i == y-x) { if(arr[i][j] == 1) { //사실은 여기서 return 0; 해버리면 더빠르나 디버깅을 위해서 //printf("대각선 체크에서 문제"); ret_num=0; } } } } } // 대각선 체크(2) for(int i=0; i<8; i++) { for(int j=0; j<8; j++) { if(i+j == x+y) { if(arr[i][j] == 1) { //사실은 여기서 return 0; 해버리면 더빠르나 디버깅을 위해서 //printf("역 대각선 체크에서 문제"); ret_num=0; } } } } //getchar(); if(ret_num == 0) { //printf("[%d,%d]에는 돌을 놓을 수 없습니다.\n\n", x, y); //showtable(); } else { //arr[x][y] = 1; //printf("[%d,%d]에는 돌을 놓을 수 있습니다.\n\n", x, y); //showtable(); } //arr[x][y] = 0; return ret_num; } int check(int depth) { if(depth == 8) { cnt++; //가능한 판의 개수 한개 추가 printf("\n----성립(%02d)----\n", cnt); showtable(); printf("\n"); getchar(); //입력 대기 return 1; } for(int i=0; i<8;i++) { if(able(i, depth) == 1) { arr[i][depth] = 1; check(depth+1); //재귀적 호출 } arr[i][depth] = 0; } return 0; } int main(void) { srand((unsigned int)time(NULL)); /* while(1) { IsAble(rand()%8,rand()%8); getchar(); } */ check(0); printf("가능한 배열의 개수 : %d개\n", cnt); return 0; }