[c][알고리즘] n-Queen

n-Queen 알고리즘은

n by n의 체스판에 Queen을 n개 놓을 때, 각 Queen이 서로를 위협하지 않는 자리에 있을 수 있는 경우의 수를 구하는 알고리즘이다.

 

		Q				Q
Q				Q
			Q				Q
	Q				Q

위의 표는 4 by 4의 체스판에 Queen이 4개 놓일 수 있는 경우의 수로

왼쪽과 오른쪽 두 가지를 제외하면 없다.

따라서 n-Queen 알고리즘에서 4에 해당하는 값은 2이다.

n	결과 값
0	1 (n이 0이기 때문에 Queen이 놓여지지 않아도 답으로 취급)
1	1
2	0
3	0
4	2

0~4에 해당하는 값으로, 어렵지 않게 생각할 수 있다.

 

n-Queen Algorithm 실습

코드 부터 보자

#include<stdio.h>
#include<conio.h>

int Queen(int n, int t, int *board);
int check(int *board, int t);

int n;
int board[4] = {0, 0, 0, 0};

int main() {
	printf("n-Queen Algorithm\n");
    printf("Input the N : ");
    scanf("%d", &n);
    int k = Queen(n, 0, board);
    printf("%d is detected.", k);
}

int Queen(int n, int t, int *board) {
    static int k = 0;
	if (n == t) {
    	printf("[ ");
    	for (int i = 0; i < n; i++) {
        	printf("%d ", board[i]);
        }
        printf("]");
        k++;
        return 0;
    }
    for (int i = 0; i < n; i++) {
    	board[t] = i;
        if (check(board, t)) {
            Queen(n, t+1, board);
        }
    }
    return k;
}

int check(int *board, int t) {
	for (int i = 0; i < t; i++) {
    	if (board[t] == board[i] || board[t] - board[i] == t-i || board[t] - board[i] == i-t) {
        	return 0;
        }
    }
    return 1;
}

천천히 분석하면 어렵지 않을 것이다.

조금 나누어서 분석해보자.

#include<stdio.h>
#include<conio.h>

int Queen(int n, int t, int *board);
int check(int *board, int t);

int n;
int board[4] = {0, 0, 0, 0};

int main() {
	printf("n-Queen Algorithm\n");
    printf("Input the N : ");
    scanf("%d", &n);
    int k = Queen(n, 0, board);
    printf("%d is detected.", k);
}

Global과 Main 지역이다.

지금 Main 첫줄의 들여쓰기가 약간 잘못되어 있는데 실행하는데는 문제 없다.

변수	의미
n	체스보드의 크기 (n X n)
k	n by n에서 구할 수 있는 경우의 수
board	1차원 배열로 체스판을 표현한 것

이 때, 체스판은 2차원 배열이나, board 변수는 1차원 배열이다.

이것이 가능한 이유는 Queen이 같은 열에서 하나만 배치되기 때문에

board[y] = x는

(x, y) 좌표에 존재하는 Queen을 뜻한다.

 

그 외에는 간단한 입출력들이다.

int Queen(int n, int t, int *board) {
    static int k = 0;
	if (n == t) {
    	printf("[ ");
    	for (int i = 0; i < n; i++) {
        	printf("%d ", board[i]);
        }
        printf("]");
        k++;
        return 0;
    }
    for (int i = 0; i < n; i++) {
    	board[t] = i;
        if (check(board, t)) {
            Queen(n, t+1, board);
        }
    }
    return k;
}

핵심이 되는 함수이다.

변수의 의미를 살펴보면

변수	의미
n	체스보드의 크기
t	보드에서 Queen이 설치되어야 할 Index
board	현재 체스보드 상황
k	정적 지역 변수, 경우의 수를 뜻함.

static int k가 정확히 뭔지는 후에 포스팅으로 다루겠다.

간단하게 값이 보존되는 변수라고 생각하면 된다.

 

처음 if문은 n과 t가 같을 때, 즉 board에 Queen 설치가 끝났을 때

현재 보드 상황을 출력하고 k를 증가시킨다.

 

for문은 이번 열(t)에 Queen을 하나씩 넣어보고 되는 경우(check 함수)

다음 열로 Queen함수를 호출하여

재귀함수를 구현하였다.

 

결과적으로 Backtracking 방식의 알고리즘을 구현하였다.

int check(int *board, int t) {
	for (int i = 0; i < t; i++) {
    	if (board[t] == board[i] || board[t] - board[i] == t-i || board[t] - board[i] == i-t) {
        	return 0;
        }
    }
    return 1;
}

check는 간단하다.

board와 t를 얻어서

현재 설치된 Queen(board[t])과 t 이전의 Queen 들을 비교한다.

 

Queen은 행, 열, 대각선으로 움직일 수 있으므로, 같은 행, 열, 대각선에 존재할 수 없다.

또한 이미 board를 설정할 때 열의 중복을 피했으므로

board[t] == board[i]로 행의 중복을 검사하고

board[t] - board[i] == t-i || board[t] - board[i] == i-t로 대각선을 검사했다.

(이게 이해가 안된다면 머릿속에 예시를 그려보자)

 

결과적으로 검사에 걸리면 return 0을 해서 안된다고 알려주고

검사에 걸리지 않으면 return 1을 해서 된다고 알려주는 함수이다.

 

부분부분별로 나누어서 생각하면 꽤 간단한 프로그램이다.

그러나, 이차원 배열을 일차원 배열로 표현하는 점과 대각선 검사, 재귀함수 구현 등의 부분은

좋은 경험이라 생각한다.

특히, 스스로 이 알고리즘을 구현해보았다면 매우 값진 경험일 것이다.