[알고리즘] N-Queens problem : backtracking algorithm

(2021.11.30) 

알고리즘 수업 들으면서 정리하기 22탄

 

w13-2 녹강 

N-Queens problem에 관한 내용이다

지금까지 배운 것 중에서 개념은 정말 쉬운 것 같은데 구현하는게 어려울 것 같다..

시간나면 구현해봐야지..

 

---

 

 

N-Queens problem

: backtracking 기본형 problem이다

n x n의 체스보드에서 n개의 서로다른 queen들이 서로 공격하지 않는 자리에 어떻게 둘 수 있는지를 물어본다.

 

예를 들어 n=4 라고 했을 때, 

4개의 Queen들이 위치할 수 있는 전체 경우의 수는 16 x 15 x 14 x 13 = 43680 가지이다.

그러나 우리는 이를 더욱 간단하게 알아 볼 수 있다.  --> search space를 줄여나가면서!!

 

 

 

기본적인 sketch idea는 아래와 같다.

1. 첫번째 Queen을 임의로 둔다.

2. 그 다음 Queen을 safe places에 둔다.

3. 이 과정을 반복한다.

  > 위치에 둬야 할 Queen이 더이상 없을 경우 (모든 Queen이 자리잡을 때까지)

  > no safe place is left (safe plce가 더 이상 없을 경우)

4. 이때, 3번의 과정에서 no safe place is left 일 경우, 그 이전의 자리를 둔 Queen의 자리를 다시 바꾼다.

---> 4번의 과정이 바로 backtracking이다. 

 

+) 조건 추가 : 첫번째 Queen은 1열에, 두번째 Queen은 2열에, ... n번째 Queen은 n열에

n=4 일때, 가능한 총 경우의 수는 4 x 3 x 2 x 1 = 256가지가 된다.

 

 

 

recurstion tree를 통해서 backtracking algorithm의 실행을 확인해 볼 수 있다.

 

이렇게 하나의 경우를 찾게 된다!

 

 

이러한 과정을 거쳐 recursion tree를 완성해보면 아래와 같다.

 

 

 

 

 

우리는 Queen을 놓을 수 있는 safe place인지 체크하기 위해서 place(i,j)를 0과 1로 둔다

0->safe place

1->unsafe place

 

코드를 짤 때에는 Queen을 놓을 열의 윗 열들만 확인해주면 된다.

 

is_attack(i,j,board,N):

// Queen 위쪽 직선
 for k in range (1,j):
  if board[k][j]==1:
   return TRUE  // TRUE로 리턴하는 것은 attack이 가능하다는 것을 의미
   
// Queen 왼쪽 위 대각선
 k=i-1
 l=j-1
 while k>=1 and l>=1:
  if board[k][l]==1:
   return TRUE
  k=k-1
  l=l-1
  
// Queen 오른쪽 위 대각선
 k=i-1
 l=j+1
 while k>=1 and l>=1:
  if board[k][l]==1:
   return TRUE
  k=k-1
  l=l+1

N-Queen(row,n,N,board):
 if n==0:
  return TRUE
 for j in range(1,N+!):
  if not is_attack(row,j,board,N):
   board[row][j]=1
   
   if N-Queen(row+1,n-1,N,board):
    return TRUE
    
   board[row][j]=1  // backtracking
   
 return FALUSE

 

 

 

 

 

 

performance of N-Queen

N은 고정되어있고(Queen의 수) n은 문제의 size이다.(남아있는 Queen의 수)

 

N-Queen의 for loop는 1~N 까지 run

 > is_attack( ): O(N) (최대 N번 실행)    

 > recursive call: T(n-1)

-->N*O(N) + N*T(n-1)

T(N)=O(N^2)+N*T(n-1)=O(n!)