[알고리즘] n-Queens Problem | 설계 및 분석

  n-Queens 문제란, nxn의 체스판에 n개의 퀸을 서로 충돌하지 않게 놓는 방법을 구하는 문제이다. 즉 서로 상대방을 위협하지 않도록 같은 행이나 같은 열, 또는 같은 대각선 상에 위치하지 않아야한다. 모든 경우를 따져가며 방법을 찾기에는 n이 커질수록 매우 다양한 경우를 따져야하므로 우리는 n-Queens문제에 backtracking 알고리즘을 적용하여 상태공간트리를 만들고, 유망한 노드들의 자식만 검사함으로써 검사해야 할 경우를 줄일 수 있다. n-Queens문제에 backtracking 알고리즘을 어떻게 적용하여 문제를 해결할 수 있는지 알아보자.

 

  이전 글에서도 설명했다시피, backtracking 문제를 풀기위해 결정되어야 할 사항은 다음과 같다.

 

<backtracking 문제를 풀기 위해 결정되어야 할 사항>

① 상태공간트리의 구조를 결정

② 유망한지 유망하지 않은지를 따질 조건을 결정. 즉, 유망함의 기준을 설정 (promising function)

 

  n-Queens문제에서는 위 사항들을 어떻게 결정할까? 먼저 상태공간트리의 경우 1행~n행까지 각 행을 level로 나누어 총 n개의 level로 이루어진 트리를 구성하고 각 level에서 1열~n열까지 각 열을 노드로 두어 총 n개의 노드들이 있다고 가정하자. 물론 이는 전체적으로 보았을 때의 구성이며, 부모노드에서부터 순서대로 노드를 추가해나갈 것이다. 이 때 유망하지 않은 노드의 자식은 방문하지 않을 것이기 때문에 각 level에 n개의 노드가 모두 존재한다는 법은 없다.

  다음으로, 유망성을 따질 promising function을 설정해보자. 말은 어려워보이지만 사실 간단하며, 우리가 이미 알고있는 내용에 관한 것이다. 우리는 퀸을 서로 충돌하지 않게 두기 위해 퀸을 놓을 때 주변을 살필 것이다. 대각선에서는 충돌하는 퀸이 없는지, 또 같은 열에 있는 퀸은 없는지 모두 검사할 것이다. (퀸을 1행부터 n행까지 순서대로 두기때문에 행이 겹칠일은 없다.) 즉 대각선과 열 이 두 가지를 검사해야 한다. 이 과정을 담은 것이 n-Queens문제의 promising funciton이며, 이를 코드로 표현하면 다음과 같다.

 

코드로 설명하기 전 col[i]이라는 배열 요소안에 i 번째 행에 있는 퀸의 컬럼 값이 들어있다고 가정하자. (실제로 그렇게 구현된다.)

 

"i 번째 행의 퀸과 k 번째 행의 퀸이 서로 같은 열에 있는가?" 

이는 단순히 col 배열에 담긴 값만 비교하면 된다.

if(col[i]==col[k])
  nonpromising;

 

"i 번째 행의 퀸과 k 번째 행의 퀸이 서로 같은 대각선에 있는가?"

두 퀸이 서로 같은 대각선 상에 있는지 알기 위해서는 두 행의 차와 두 열의 차를 비교하면 된다. 여기서 abs는 절댓값 함수이다.

if(abs(col[i]-col[k]) == abs(i - k))
  nonpromising;

 

  지금까지 n-Queens문제에 되추적 알고리즘을 적용하기 위한 모든 준비가 끝났다. 이제 아래 n-queens 문제를 해결하기위한 코드를 보자. 우리가 앞서 구상한 promising 함수가 사용되고있다. promising 함수를 통해 해당 노드가 유망하다고 판정나면 해당노드의 자식을 재귀적으로 탐색한다.

 

void queens (index i) {
  index j;
    if(promising(i)) { //유망한 경우
      if(i==n) //해답을 찾은 경우(n-Queens는 문제특성상 leaf노드까지 도달해야 답을 찾을 수 있음)
        cout << col[1] through col[n]; //모든 퀸의 위치 출력
      else
        for (j=1;j<=n;j++) {
          col[i+1] = j;
          queens(i+1); //자식을 탐색. 이때 자식은 i+1행
        }
    }
}


bool promising(index i) {
  index k;
  bool switch;
  
  k=1;
  switch = TRUE;
  while(k<1 && switch) {
    if(col[i]==col[k] || abs(col[i]-col[k]) == abs(i-k))//같은 열에 있거나 같은 대각선에 있는경우
      switch=FALSE;//유망하지 않으므로 FALSE 리턴
    k++;
  }
  return switch;
}

알고리즘 성능 분석

  n-Queens문제의 성능을 어떻게 분석할까? 상태공간트리의 전체 노드의 상한(upper bound) 개수를 구하거나 유망한 노드의 상한 개수를 구해볼 수 있다. 하지만 이는 '상한'일 뿐, 정확한 복잡도를 알 수 없다. 결국에는 이미 구축이 완료된 상태공간트리의 노드 개수를 실제로 세어보는 수 밖에 없다. 하지만 이 방법은 진정한 분석 방법이라고 할 수 없다. 분석은 알고리즘을 실제로 수행하지 않고 이루어져야하기 때문이다. 따라서 성능을 계산할 수 없으므로, '추정'해볼 수 있는데, 이처럼 알고리즘의 성능을 추정할 때 사용하는 알고리즘을 'Monte Carlo 기법'이라고 한다.

 

monte carlo 기법에 대한 설명은 아래 글을 참고하면 된다.

 

[알고리즘] Monte Carlo Algorithm, 몬테카를로 알고리즘

<Monte Carlo 알고리즘을 사용하기위해 만족해야할 조건 2가지>

① 상태공간트리에서 같은 수준(level)에 있는 모든 노드에서는 같은 유망함수를 사용해야 한다.

② 상태공간트리에서 같은 수준에 있는 모든 노드들은 같은 수의 자식노드들을 가지고 있어야 한다.

 

  n-Queens 문제의 상태공간트리는 위 조건을 모두 만족한다. nxn 크기의 체스판이므로 모든 노드들이 같은 수의 자식노드들을 가지고있고, 같은 유망함수를 사용한다. n-Queens 문제에 Monte Carlo 알고리즘을 사용하여 성능을 추정하는 알고리즘은 다음과 같다.

 

n-Queens 문제 - Monte Carlo 알고리즘 수도코드

int estimate_n_queens (int n) {
  index i, , col[1..n];
  int m, mprod, numnodes;
  set_of_index prom_children;
  
  i=0; numnodes=1; m=1; mprod=1;
  
  while (m!=0 && i!=n) {
    mprod = mprod*m;
    numnodes = numnodes + mprod*n;
    i++;
    m=0;
    prom_children = ∅;
    for(j=1; j<=n; j++) {
      col[i]=j;
      if(promising(i)) {
        m++;
        prom_children = prom_children ∪ {j};
      }
    }
    if(m!=0) {
      j = random selection from prom_children;
      col[i] = j;
    }
  }
  return numnodes;
}