N-Queens Problem
- N×N의 체스판에 N개의 퀸이 서로 위협하지 않도록(Path가 겹치지 않도록) 위치시키는 문제
4-Queens Problem의 상태공간트리
깊이우선검색(DFS)
- 깊이우선검색(Depth First Search)을 사용하면 해답을 찾을 수 있다. 그러나 이 방법을 사용하면 해답이 될 가능성이 전혀 없는 노드의 후손(descendant) 노드까지 검색하기 때문에 비요율적이다. 위 그림에서 보면, 첫 번째 퀸이 (1, 1)에 놓일 경우 두 번째 퀸은 (2, 1)에 놓일 수 없으므로 (2, 1)의 후손노드는 검색할 필요가 없다.
노드의 유망성(Promising)
- 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다(non-promising)고 하고, 그렇지 않으면 유망하다(promising)고 한다.
- 위의 DFS에서 (2, 1)의 후손 노드는 non-promising하다.
되추적(Backtracking)
- 어떤 노드의 유망성을 검사하여 유망하지 않다고 판정되면 후손 노드(서브트리)들에 대한 검색을 중지하고(Pruning), 그 노드의 부모노드로 돌아가서 다른 후손 노드에 대해 검색을 수행한다.
가지치기(Pruning)
- 유망하지 않은 노드에 대에 진행을 하지 않는 것을 말한다.
4-Queens Problem의 되추적 상태공간트리
DFS VS Backtracking
- 검색하는 노드 개수
- DFS = 155 개 (전체 (1+4+16+64+256)개 중 155번째에서 솔루션을 찾게 됨)
- Backtracking = 27 개
되추적 알고리즘의 개선
- 유망성 여부에 대한 확인을 노드 방문 전에 실시
Java 소스코드
분석은 나중에...
public class NQueens {
private static final int N = 4;
private static int[] b = new int[N];
private static int s = 0;
static boolean unsafe(int y) {
int x = b[y];
for (int i = 1; i <= y; i++) {
int t = b[y - i];
if (t == x ||
t == x - i ||
t == x + i) {
return true;
}
}
return false;
}
public static void putboard() {
System.out.println("\n\nSolution " + (++s));
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
System.out.print((b[y] == x) ? "|Q" : "|_");
}
System.out.println("|");
}
}
public static void main(String[] args) {
int y = 0;
b[0] = -1;
while (y >= 0) {
do {
b[y]++;
} while ((b[y] < N) && unsafe(y));
if (b[y] < N) {
if (y < N - 1) {
b[++y] = -1;
} else {
putboard();
}
} else {
y--;
}
}
}
}