수다닷컴

질문 제목 : n-queens 구현

밑에 내용을 c로 실행을 시켜야 하는데 읽어도 어떻게 해야할지 모르겠어요.

소스좀 짜주실수 있을까요 ㅜㅜ

미로퍼즐에서 출구를 찾아 나가려고 한다면, 막힌 곳이 나올 때까지 경로를 따라 가보는 수밖에 없을 것이다. 막힌 곳에 도달하게 되면, 갈래가 있는 곳까지 돌아가서, 다른 쪽으로 가보게 될 것이다. 만약 미로퍼즐에서 막힌 곳으로 가는 경로가 표시되어 있다면, 이 퍼즐을 해결하는 건 너무나 쉬운 일이 될 것이다. 그 이유는 표시가 된 경로 이후의 모든 경로들은 고려대상에서 제외될 것이기 때문이다. 이는 여러 번의 헛수고를 덜어준다는 의미가 된다. 물론 모든 미로퍼즐에는 그러한 표시가 없다. 그러나 이 장에서 공부할 되추적 알고리즘에서는 그러한 표시가 존재한다.

1. 되추적 기술

되추적은 어떤 집합(set)에서 어떤 기준(criterion)을 만족하면서 그 집합에 속한 대상의 순서(sequence)를 선택하는 문제를 푸는데 사용한다. 되추적의 전형적인 예로 서양장기(chess)의 n-여왕말 문제이다. 이 문제의 목표는 n×n 크기의 서양 장기판에 서로 잡아먹히지 않도록 n개의 여왕말을 위치시키는 것이다. 즉, 어떤 여왕말끼리도 같은 행, 열 또는 대각선상에 위치할 수 없다. 이 문제에서 순서는 여왕말을 두는 n개의 위치가 되고, 각 선택의 집합은 서양 장기판에서 말을 둘 수 있는 n^2개의 위치들이 되고, 기준은 어떤 두 여왕말도 서로 잡아먹히지 말아야 한다는 것이다. n-여왕말 문제는 표준 서양 장기판의 크기인n = 8인 경우를 일반화 한 것이다. 간결하게 하기 위해서 n=4인 경우의 사례를 가지고 되추적 방법을 설명한다.

되추적은 트리의 수정된 깊이우선탐색(depth- first search)이다. 깊이우선탐색을 이용하여 되추적을 설명할 때, 되추적이 트리의 검색에 국한되기 때문에 여기서는 단순히 트리의 검색만을 고려한다.

그림 1을 보면 트리의 깊이우선탐색을 수행하는 예가 나와 있다. 각 마디들은 방문하는 순서대로 번호가 매겨져 있으며, 방문경로는 더 이상 갈 수 없는 마디까지 깊이 내려간다. 마지막 마디에서 다시 방문하지 않은 자식마디가 있는 마디로 되돌아가고, 거기서 다시 가능한 깊이까지 내려간다.

그림 1 깊이우선탐색 순서에 따라 마디에 번호가 매겨진 트리 n= 4 일 때, n-여왕말 문제를 되추적 기술로 푸는 방법을 알아보자. 4×4 서양 장기판에 4개의 여왕말을 서로 잡아먹히지 않게 두어야 한다. 같은 행에 두 말을 놓을 수 없다는 사실을 가지고 바로 문제를 간단하게 만들 수 있다. 각 여왕말을 다른 행에 놓고 각 여왕말이 어떤 열에 놓이면 해답이 되는지 검사해 보면 된다. 각 여왕말은 4개의 열중에서 한 곳에 놓을 수 있기 때문에, 해답후보는 4×4×4×4=256개가 존재한다.
첫 번째 여왕말(행 1에 있는 여왕말)에 해당하는 열은 트리의 수준(level) 1에 있는 마디에 저장(root의 level은 0이다.)하고, 두 번째 여왕말(행 2에 있는 여왕말)에 해당하는 열은 트리의 level 2에 있는 마디에 저장하는 식으로 트리를 구축하여 해답후보를 만들 수 있다. root마디에서 최하위마디(더 이상 자식이 없는 마디)까지 경로는 해답후보가 된다. 이 트리를 상태공간트리(state space tree)라고 한다. 그림 2를 보면 상태공간트리의 일부분이 나와 있다. 전체 트리는 최하위마디의 개수가 256개이고, 각 최하위마디는 해답후보를 나타낸다. 튜플i,j가 각 마디에 저장되어 있고 이 튜플은 i번째 행에 있는 여왕말이 j열에 있음을 의미한다.
그림 2 n=4일 때 n-여왕말 문제에 대한 상태공간트리의 일부분 해답을 구하기 위해서, 각 해답후보를 깊이우선탐색의 방식으로 검사한다. 상태공간트리의 단순 깊이우선탐색은 중간에 있을지도 모르는 어떤 표시를 이용하지 않고 막힌 곳에 도달할 때까지 미로의 모든 경로를 가보는 것과 같다. 그러한 표시를 찾아봄으로써 검색을 더 효율적으로 수행할 수 있다. 예를 들어, 그림 3(a)에서 보는바와 같이 어떤 두 여왕말도 같은 열에 놓을 수 없다. 그러므로 그림 2에서 튜플2,1이 들어있는 마디에서 뻗어가는 모든 경로는 이미 여왕말 1을 첫 번째 열에 놓았기 때문에 검사할 이유가 없다.
그림 3 첫 번째 여왕말이 1열에 있을 때, 두 번째 여왕말을 1(a)열이나 2(b)열에 둘 수 없음을 보여주는 그림 되추적은 막힌 곳으로 이르는 마디라는 사실을 알면, 그 마디의 검색을 중단하고 그 마디의 부모마디로 돌아가서(“되추적”) 다음 자식마디의 검색을 계속하는 프로시저이다. 마디를 방문할 때 그 마디가 해답이 될 가능성이 없는 것으로 결정되면, 그 마디를 유망하지 않다(non-promising)라고 한다. 그렇지 않으면 유망하다(promising)라고 한다. 이렇게 유망하지 않은 마디의 검색을 중단하고 부모마디로 되추적 하는 절차를 트리의 가지치기라고 하고, 유망한 마디만으로 구성된 부분트리를 가지친 상태공간트리(pruned state space tree)라고 한다.
되추적 알고리즘은 마디가 유망하고 그 마디에 해답이 없는 경우에만 그 마디의 자식마디를 방문하는 것을 제외하고는 깊이우선탐색과 같다. 이와 같은 방식으로 n-여왕말 문제의 해답을 구해보면 다음과 같은 과정을 갖는다.step )------------------------------------------------------------------1. 1,1은 유망하다.{여왕말 1이 놓는 첫 번째 말이기 때문}
2. 2,1은 유망하지 않다.{여왕말 1이 열 1에 있기 때문}
2,2는 유망하지 않다.{여왕말 1이 왼?1이 왼쪽 대각선에 있기 때문}
2,3은 유망하다.
3. 3,1은 유망하지 않다.{여왕말 1이 열 1에 있기 때문}
3,2는 유망하지 않다. {여왕말 2가 오른쪽 대각선에 있기 때문}
3,3은 유망하지 않다.{여왕말 2가 열 3에 있기 때문}
3,4는 유망하지 않다.{여왕말 2가 왼쪽 대각선에 있기 때문}
4. 1,1로 되추적
2,4는 유망하다.
5. 3,1은 유망하지 않다.{여왕말 1이 열 1에 있기 때문}
3,2는 유망하다{3,2를 두 번째 검사함}
6. 4,1은 유망하지 않다.{여왕말 1이 열 1에 있기 때문}
4,2는 유망하지 않다. {여왕말 3이 열 2에 있기 때문}
4,3은 유망하지 않다.{여왕말 3이 왼쪽 대각선에 있기 때문}
4,4는 유망하지 않다.{여왕말 2가 열 4에 있기 때문}
7. 2,4로 되추적
3,3은 유망하지 않다.{여왕말 2가 오른쪽 대각선이 있기 때문}
3,4는 유망하지 않다.{여왕말 2가 열 4에 있기 때문}
8. root로 되추적
1,2는 유망하다.{여왕말 1이 놓는 첫 번째 말이기 때문}
9. 2,1은 유망하지 않다.{여왕말 1이 오른쪽 대각선에 있기 때문}
2,2는 유망하지 않다.{여왕말 1이 열 2에 있기 때문}
2,3은 유망하지 않다.{여왕말 1이 왼쪽 대각선에 있기 때문}
2,4는 유망하다.
10. 3,1은 유망하다.{3,1을 세 번째 검사함}
11. 4,1은 유망하지 않다.{여왕말 3이 열 1에 있기 때문}
4,2는 유망하지 않다.{여왕말 1이 열 2에 있기 때문}
4,3은 유망하다.
- 되추적을 이용하여 첫 번째 해답을 구하였다.
------------------------------------------------------------------------2. n-여왕말 문제 n-여왕말 문제의 알고리즘 작성을 위해 우선 유망함수는 두 여왕말이 같은 열이나 대각선에 있는지 검사해야 한다. 먼저 같은 열에 있는지를 확인하기 위해서 i번째의 행에서 여왕말과 k번째의 행의 여왕말의 검사라고 가정하면 다음과 같은 등식이 성립하는지 검사한다.
col(i) = col(k)
대각선을 검사하는 방법은 다음과 같다. 다음 그림 4를 보면n = 8인 경우의 예가 그려져 있다. 이 그림에서 행 6에 있는 여왕말은 행 3에 놓여있는 여왕말에 의해서 왼쪽 대각선으로 위협받고 있고, 행 2에 놓여 있는 여왕말에 의해서 오른쪽 대각선으로 위협받고 있다. 즉, 오른쪽에서 위협하는 여왕말에 대해서, 열에서 차이는 행에서 차이의 음(negative)과 같다. 행 k에 있는 여왕말은 행 i에 놓여 있는 여왕말에 의해서 어느 한쪽 대각선으로 위협받고 있으면, 다음과 같은 일반 등식이 성립한다.
col(i) - col(k) =i - k또는 col(i) - col(k) = k - i그림 4 행 6에 있는 여왕말이 행 2,3의 여왕말에게 위협받고 있다. 이제 알고리즘을 제시한다.
알고리즘1 n-여왕말 문제를 푸는 되추적 알고리즘)-----------------------------------문제 : 서양장기판의 어떤 두 여왕말도 같은 행, 열, 대각선에 있지않도록 n개 여왕말을 위치
입력 : 양의 정수 n
출력 : n × n 서양장기판에 개 여왕말을 서로 위협받지 않고 놓을 수 있는 가능한 모든 결과
여기서 col[i]는 i번째 행에 위치하는 여왕말의 열이다.void queens( keyword number )
{
keyword i ,j; if ( promissing(i) )
{
if( number == n )
for( i = 0; i n; i++ )
printf(%d,col[i]);
else
for( j = 0; j n; j++ ) {
col[i +1] = j;
queens(i +1);
}
}
}
bool promissing( keyword number )
{
keyword k;
bool b; k = 1;
b = true; while ( k number && b )
{
if( col[number] == col[k] || abs(col[i] - col[k]) == I - k )
b = false;
k++;
}

return b;
}
------------------------------------------------------------------------

신청하기