백트래킹 -(1) N queens problem

백트래킹

모든 경우를 보다가 해가 아닐 것 같으면 가지치기(prune)하며 되돌아간다.

 

 

 

N queens problem

: N*N 체스판에 n개의 퀸을 어느 두개의 퀸이 서로를 위협하지 않도록 배치하는 문제

 

sequence: queens을 놓을 n개의 자리

set: 체스판의 총 자리 -> n^2

criterion: 어느 두개의 퀸이 서로 위협하지 않도록

-> 같은 줄이나 같은 대각선에 있으면 안됨 (퀸은 대각선, 앞,뒤,옆으로 칸갯수 제한 없이 이동 가능 )

 

예) 4 queens problem

골라야 하는 경우의 수: C(16,4)=1820

같은 행에 두면 안되므로 -> 4* 4* 4* 4=256가지 경우의 수가 줄어듦

 

<i,j> : 퀸이 i번째 row, j번째 column에 뒀다는 걸 표현

 

 

 

백트래킹을 이용해 N-queens problem 해결하기

1. dfs 알고리즘으로 트리 탐색

2. 각 노드가 promising 한지 체크

-> 같은 column에 두면 안됨: Col(i) == Col(k)한지 체크

   같은 대각선에 두면 안됨: |Col(i) –Col(k)| == i-k ( i >k일 때) 한지 체크

    -> 행의 차와 열의 차가 같다면 같은 대각선임.

3. nonpromising하다면 노드의 부모로 되돌아가서 다른 경로를 탐색

 

public static void queens( index i) {
    index j;
    
    if (promising(i))
        if (i==n)
            system.out.print ( col[1] .. col[n] )
    else
        for (j=1; j<=n; j++) {
            col[i+1] = j; 
            queens(i+1);
		}
}

public static boolean promising(index i)
{
    index k; boolean switch;
    k= 1;
    switch= true ;
    
    while (k<i&& switch) {
        if (col[i]==col[k]) || abs(col[i]-col[k]) == i-k)
            switch = false ;
        k++;
        }
        
    return switch;
}

* 실제로 컴퓨터에서 실행해봐야 걸리는 시간을 알 수 있다.