[알고리즘] 8퀸 문제

8퀸 문제

체스판에 각 8개의 퀸이 서로 공격하여 잡을 수 없도록 8 * 8 체스판에 배치하는 문제

 

위 조건을 만족하기 위해서는 아래의 규칙들을 만족해야 한다.

 

규칙1: 각 열에 퀸을 1개만 배치한다.

규칙2: 각 행에 퀸을 1개만 배치한다.

 

그러나 이 규칙들만으로 답을 찾는 것은 쉽지 않다.

따라서 이 때 분기 작업으로 문제를 해결해야 한다.

분기 작업이란 가지가 뻗어 나가듯이 배치 조합을 열거하는 것을 의미한다.

 

이 때, 만약 i열의 j번째 행에 퀸이 놓여져 있다면, 배열 pos[i]를 j로 설정한다.

 

# 각 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열하기

pos = [0] * 8

def put() -> None:
    """각 열에 배치한 퀸의 위치를 출력"""
    for i in range(8):
        print(f'{pos[i]:2}', end='')
    print()

def set(i: int) -> None:
    """i열에 퀸을 배치"""
    for j in range(8):
        pos[i] = j      # 퀸을 j행에 배치
        if i == 7:      # 모든 열에 퀸 배치를 종료
            put()
        else:
            set(i + 1)  # 다음 열에 퀸을 배치

set(0)  # 0 열에 퀸을 배치

위 코드를 통해 각 열에 퀸을 하나씩 두는 배치를 열거할 수 있다.

 

그러나 분기 작업만으로는 문제를 해결할 수 없기 때문에 분기 한정법을 사용해야 한다.

# 행과 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열하기

pos = [0] * 8           # 각 열에서 퀸의 위치
flag = [False] * 8      # 각 행에 퀸을 배치했는지 체크

def put() -> None:
    """각 열에 배치한 퀸의 위치를 출력"""
    for i in range(8):
        print(f'{pos[i]:2}', end='')
    print()

def set(i: int) -> None:
    """i열의 알맞은 위치에 퀸을 배치"""
    for j in range(8):
        if not flag[j]:         # j행에 퀸을 배치하지 않았으면
            pos[i] = j          # 퀸을 j행에 배치
            if i == 7:
                put()
            else:
                flag[j] = True
                set(i + 1)      # 다음 열에 퀸을 배치
                flag[j] = False

set(0)

위 코드를 통해 각 행에 퀸을 1개씩만 배치할 수 있도록 한다.

필요하지 않은 분기를 없애서 불필요한 조합을 열거하지 않는 방법을 한정 작업이라고 한다.

분기 작업과 한정 작업을 조합하여 문제를 풀이하는 방법을 분기 한정법이라고 한다.

 

8퀸 문제 해결

# 8퀸 문제 알고리즘 구현하기

pos = [0] * 8           # 각 열에 배치한 퀸의 위치
flag_a = [False] * 8    # 각 행에 퀸을 배치했는지 체크
flag_b = [False] * 15   # 대각선 방향으로 퀸을 배치했는지 체크
flag_c = [False] * 15   # 대각선 방향으로 퀸을 배치했는지 체크

def put() -> None:
    """각 열에 배치한 퀸의 위치를 출력"""
    for i in range(8):
        print(f'{pos[i]:2}', end='')
    print()

def set(i: int) -> None:
    """i열의 알맞은 위치에 퀸을 배치"""
    for j in range(8):
        if (not flag_a[j] and not flag_b[j + j] and not flag_c[i - j + 7]):
            pos[i] = j
            if i == 7:
                put()
            else:
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
                set(i + 1)
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False

set(0)