백트랙킹과 n-Queens 문제

  • backtracking

    • 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는 데 적합함
    • 트리 자료구조의 변형된 깊이우선탐색
    • 모든 문제 사례에 대해서 효율적이지 않지만 많은 문제 사례에 대해 효율적

  • 미로찾기 문제를 트리 탐색 문제로 해석 (DFS를 통한 preorder 방식)

  • 상태공간트리 (State Space Tree)

  • 백트래킹 기법

    • 상태공간트리를 깊이우선탐색으로 탐색
    • 방문중인 노드에서 더 하위 노드로 가면 해답이 없을 경우엔 해당 노드의 하위 트리를 방문하지 않고 부모 노드로 되돌아감

  • 유망함 (promising)

    • 방문중인 노드에서 하위 노드가 해답을 발견할 가능성이 있으면 유망
    • 하위 노드에서 해답을 발견할 가능성이 없으면 유망하지 않음

  • 백트래킹과 가지치기

    1. 상태공간트리를 DFS로 탐색
    2. 방문 중인 노드가 유망한지 체크
    3. 만약 유망하지 않으면 부모 노드로 돌아감
    4. 그리고 유망하지 않는 하위 트리를 가지치기함

슈도 코드

1
2
3
4
5
6
7
8
def checknode (node v): 
    node u;
    if (promising(v)):
        if (v에 해답이 있다면)
            해답을 출력
        else
            for (v의 모든 자식 노드)
                checknode(u);

  • 백트래킹 알고리즘의 구현

    • 상태공간트리를 실제로 구현할 필요는 없음
    • 현재 조사중인 가지의 값에 대해만 추적
    • 상태공간트리는 암묵적으로 존재한다고 가정

  • n-Queens 문제

    • 8-Queens의 일반화 문제
    • n x n 체스보드에 n개의 퀸을 배치하는 문제
      → 어떤 퀸도 다른 퀸에게 잡아먹지 않도록 배치할 것

  • n-Queens를 backtracking approach로 해결하기

    • 임의의 집합에서 기준에 따라 원소의 순서를 선택
    • 임의의 집합: 체스보드에 있는 n^2^개의 가능한 위치
    • 기준: 새로 놓을 퀸이 다른 퀸을 위협할 수 없음
    • 원소의 순서: 퀸을 놓을 수 있는 n개의 위치

  • 4-Queens 문제 (n = 4)

    • 일단 같은 행에는 놓을 수 없다고 가정하면 후보 해답은 4(가로 4칸) x 4(가로 4칸) x 4(가로 4칸) x 4(가로 4칸) = 256 가지의 탐색 공간이 있음

  • n-Queen 문제의 해결

    • 같은 행에는 퀸을 놓지 않는다(기본 가정)
    • 같은 열이나 같은 대각선에 놓이는지를 확인
    • 같은 열을 체크하기
      → col[i]: i번째 행에서 퀸이 놓여있는 열의 위치
      → col[k]: k번째 행에서 퀸이 놓여있는 열의 위치
      → 따라서, col[i] == col[k] 이라면 유망하지 않다
    • 대각선 체크하기
      → 왼쪽에서 위협하는 퀸과 오른쪽에서 위협하는 퀸은 |i - k|값으로 판단할 수 있다

파이썬으로 n-Queens 문제를 위한 백트래킹 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def n_queens (i, col):
    n = len(col) - 1
    if (promising(i, col)):
        if (i == n): 
            print(col[1: n+1])
        else:
            for j in range(1, n+1):
                col[i+1] = j
                n_queens(i+1, col)

def promising (i, col):
    k = 1
    flag = True
    while (k < i and flag):
        if (col[i] == col[k] or abs(col[i] - col[k]) == (i - k)):
            flag = False
        k += 1
    return flag