[알고리즘] 8퀸 문제 (재귀)

8 * 8 크기의 체스판에 8개의 퀸을 배치하는 경우의 수를 생각해 보자.

각 행과 열, 대각선에서 퀸이 2개 있으면 안 된다.

 

ex)

□ □ ■ □ □ □ □ □ 
□ □ □ □ □ ■ □ □ 
□ □ □ □ □ □ □ ■ 
■ □ □ □ □ □ □ □ 
□ □ □ □ ■ □ □ □ 
□ □ □ □ □ □ ■ □ 
□ ■ □ □ □ □ □ □ 
□ □ □ ■ □ □ □ □ 

 

이 소스 코드에서 문제를 푸는 방식은 다음과 같다.

0열 ~ 7열까지 퀸을 순서대로 배치하되, 배치하려는 행과 대각선에 다른 퀸이 있는지를 확인한다.

 

# 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 = '') # pos의 원소를 하나씩 출력
    print()
    
def set(i: int) -> None:
    """i열의 알맞은 위치에 퀸을 배치"""
    for j in range(8):
        if (flag_a[j] == False # j행에 퀸이 배치되지 않았다면
            and flag_b[i + j] == False # 대각선 방향(/)으로 퀸이 배치되지 않았다면
            and flag_c[i - j + 7] == False): # 대각선 방향(\)으로 퀸이 배치되지 않았다면
            pos[i] = j # 퀸을 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) # 0열에 퀸을 배치