6. 순환(Recursion)의 응용: N-Queens

6. 순환(Recursion)의 응용: N-Queens

 

N-Queens

가로세로 크기가 N인 체스보드에서 N개의 퀸들이 서로를 공격할 수 없게 놓는 문제.

동일한 행, 열, 대각선에 2개 이상의 말이 놓이지 않아야 한다.

​

ex) N = 4

	O
			O
O
		O

상태공간 트리란,

찾는 해를 포함하는 트리.

즉, 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함.

따라서, 이 트리를 체계적으로 탐색하면 해를 구할 수 있음.

하지만, 상태공간 트리의 모든 노드를 탐색해야하는 것은 아님.

​

되추적 기법(Backtracking)

상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘

​

자바 예제)

매개변수는 내가 현재 트리의 어떤 노드에 있는지를 지정해야한다.

cols[i] = j 는 i번 말이 (i행, j열)에 놓였음을 의미한다.

int [] cols = new int [N+1];

boolean queens (int level) {
   if (!promising(level))
      return false;
   else if (level == N) {
      for (int i = 1; i <= N; i++)
         system.out.println("(" + i + "," + cols[i] + ")");
      return true;
   }
   for (int i = 1; i <= N; i++) {
      cols[level +1] = i;
      if(queens(level+1))
      return true;
   }
   return false;
}

//Promising test
boolean promising (int level) { //마지막 값이 이전 값들과 같은 열, 대각선인지만 검사
   for (int i = 1; i<level; i++) {
      if (cols[i] ==cols[level]) //같은 열에 놓였는지 검사
         return false;
      else if (level-i == Math.abs(cols[level]-cols[i]))//대각선에 놓였는지 검사
         return false;
   }
}