N Queens Problem

N*N 크기의 체스보드에 서로의 퀸이 공격하지 못하게 배치하는 방법을 찾는 문제이다.

이 문제를 해결하기 위해선 Backtracking 이라는 기법을 사용할 예정이다.

 

백 트래킹 기법은 각 스탭에서 조건을 충족시키는 경우의 수만 다음 스탭을 진행시킨다는 점에서 그리디 기법과 유사하다.

하지만, 그와 다르게 백 트래킹은 조건을 충족하지 않는 경우 이전의 선택지로 돌아갈 수 있다는 특징이 있다.

따라서 기본적으로 백 트래킹 기법은 Depth-first search를 진행하여 트리를 탐색한다.

 

N Queens Problem

우선 문제에 대한 접근은 한 행에는 하나의 퀸만 배치한다.

이렇게 되면 퀸이 공격 가능한지 검사할 때, 대각선과 열에 대해서만 검사하면 된다.

 

이 문제를 해결하기 위해 여기서도 promising이란 개념을 도입한다.

1행 2열에 퀸 배치시 <1, 2>로 표현한다.

 

- NonPromising Node

앞으로 계속 진행했을 때 절대로 해를 구해낼 수 없는 노드.

즉, 이미 두 개 이상의 퀸이 서로 공격할 수 있는 포지션에 배치된 경우를 의미한다.

 

- Promising Node

NonPromising Node가 아닌 모든 노드를 지칭한다. (소거법)

 

결론은 이 문제를 해결하기 위해서 Promising Node에 대해 Depth-first search를 진행하면 된다.

 

이제 의사코드로 구현해볼건데, 그 전에 하나의 규칙을 정하자.

col[i]: <i, col[i]>의 뜻으로 i행에 배치된 퀸의 열을 나타낸다.

 

public static void queens(index i) {
    // promising 하지 않는 노드에 대해서는 진행하지 않는다.
    if (!promising(i)) return;
    
    // 끝까지 탐색된 경우 결과 출력.
    if (i==n) {
        system.out.print(col[1]..col[n]);
        return;
    }
    
    // 다음 행(i+1)의 각각의 열(j)에 대해 시도.
    for (index j=1; j<=n; j++) {
        col[i+1] = j;
        queens(i+1);
    }
}

public static boolean promising(index i) {
    boolean switch = true;
    index k = 1;
    
    // 입력으로 들어온 행에 대한 검사이니
    // 이전 행들에 대해서만(k<i) 비교한다.
    while (k<i && switch) {
        // queen's attack condition (같은 열 || 대각선)
        if (col[i] == col[k] || abs(col[i]-col[k]) == abs(i-k)) {
            switch = false;
        }
        k++;
    }
    
    return switch;
}

 

정확한 시간 복잡도를 계산하기는 어렵지만,

worst case로 각 행마다 1개의 NonPromising Node가 발생한다고 가정하면,

$$ 1 + n + n(n-1) + ... + n! $$

Θ(n!)의 시간 복잡도를 갖는다.

 

상당히 비 효율적인거 같지만, 트리를 전체 탐색하는 것 보다는 훨씬 효율적이다.

$$ 1 + n + n^2 + ... + n^n $$

전체 탐색은 Θ(n^n)의 시간 복잡도를 갖기 때문이다.