[알고리즘] 재귀 알고리즘을 활용한 8퀸 문제 풀이

8퀸 문제란?

- 재귀 알고리즘을 설명할 때 자주 나오는 예제로, 19세기 수학자인 '카를 F. 가우스'가 오답을 발표한 것으로 유명.

 

8퀸 문제의 조건

- 8개의 퀸이 서로 공격하여 잡을 수 없도록 8 x 8 체스판에 배치하라.

 

이 문제는 총 92가지 해결 방법을 얻을 수 있고, 아래 그림은 92가지 해결 방법 중 한가지이다.

이 문제를 해결하는 데 사용하는 문제 풀이 방법은 분기작업(branching, 차례대로 가지가 뻗어 나가듯이 배치 조합을 열거하는 방법)과 분할 정복법(분할 해결법, divide and conquer, 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법)을 이용하여 해결할 수 있다. 한 가지 주의할 점은 문제를 분할할 때 작은 풀이법에서 원래의 문제 풀이법을 쉽게 도출할 수 있도록 설계하는 것이 관건.

 

퀸을 배치하는 방법

체스판은 총 64칸(8 X 8) 크기이므로 

1) 첫 번째 퀸은 64칸 중 아무곳이나 선택이 가능

2) 두 번째 퀸은 나머지 63칸 중 임의로 선택이 가능

3) 이 방법으로 8번째까지 퀸을 배치할 곳을 생각하면 다음과 같은 조합의 수가 만들어짐

64 X 63 X 62 X 61 X 60 X 59 X 58 X 57 = 178,462,987,637,760

위와 같이 큰 수의 조합을 모두 나열한 후 문제의 조건을 만족하는 지 비교하는 것은 비현실적이므로 갖가지 규칙을 먼저 생각한다.

우리가 흔히 아는 체스판에서의 퀸은 가로, 세로, 대각선 어디든지 8개의 방향으로 직선 이동해서 상대를 잡을 수 있다는 점.

세울 수 있는 규칙은 다음과 같다.

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

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

규칙 3 대각선에 퀸을 배치하지 않는다.

 

문제를 정리하기 위해 규칙 1에 따라 조합을 나열하는 알고리즘부터 생각해보자.

각 열에 퀸을 1개만 배치하는 원래 문제

위 사진은 처음에 제시된 체스판에서 8개의 행을 1개로 병합하여 8개의 열만을 남겨둔 것이다.

이 8개의 열들에 물음표가 있는데 이 8개의 물음표 칸에 퀸을 1칸씩 먼저 채우면서 배치해보자. 

원래의 문제를 8개의 문제로 나누게 되면 위와 같이 나눌 수 있게 된다. 이렇게 8가지 방법으로 0열에 배치하는 것은 끝났으니 1열에 퀸을 배치하는 방법을 살펴보자.

 

이와 같이 0열과 1열에 퀸을 배치하는 방법은 8 X 8 = 64가지이다. 이제 남은 조합에 대한 과정은 총 16,777,216가지가 있다.

 

퀸의 배치를 나타내는 배열을 선언하기

1) 이번에 살펴볼 배열 pos는 퀸의 위치를 나타낸다. i열에 위치한 퀸의 위치가 j행에 있다면, pos[i]의 값을 j로 한다. 

예를 들면 pos[0]의 값이 0이라면 퀸은 0열 0행에 배치된 것이고, pos[1]의 값이 4라면 퀸은 1열 4행에 배치된 것이다.(=pos[i]열 j행)

 

2) 두번째로, set( )함수는 pos[i]에 0~7까지의 값을 차례로 대입해서 i열에 퀸을 1개만 배치하게끔 8가지 조합을 만드는 재귀함수이다.

set(0)을 호출하게 되면, 인수로 0을 전달받게 되고 0열 0행에 퀸을 배치한다. 이것을 for 반복문으로 반복을 수행해서 j값을 0~7까지 1씩 증가시키며 pos[i]에 j를 대입해서 퀸을 j행에 배치하게 한다. 이렇게 할때 0열에 퀸의 위치가 확정되기 때문에 다음 1열에 퀸을 위치시켜야 한다. 이것을 위해 set(i + 1)을 수행한다.

pos = [0] * 8

def put() -> None:
	for i in range(8):
    	print(f"{pos[i]:2}", end=" ")
    print()

def set(i: int) -> None:
	for j in range(8):
    	pos[i] = j # 퀸을 j행에 위치시킴
        if i == 7: # i가 7이라는 것은 모든 열에 퀸을 위치시킨 것(반복문이 끝날 수 있는 조건)을 의미한다.
     	    put()
     	else:
        	set(i + 1)
            
set(0) # 가장 처음에 0열에 퀸을 배치함

위 코드를 실행하게 되면 정말 많은 가짓수의 조합이 나오고 반복문이 끝나지 않게 된다. 그러나 이와 같은 비교적 짧은 코드를 작성하게 된다면, 사용자가 설정한 조건에 맞는 조합을 추출해낼 수 있게 된다.

하지만, 아직 위 코드는 규칙 2(각 행에 퀸을 1개만 배치)를 적용하지 않은 코드이다.

각 행에 퀸을 1개만 배치할 수 있도록 체크하는 방법을 적용해서 코드를 작성해보자.

pos = [0] * 8 # 각 열에서의 퀸의 위치
flag = [False] * 8 # 각 행에 퀸을 배치했는지 체크하는 변수 flag(모두 False로 초기화)

def put() -> None:
	for i in range(8):
    	print(f"{pos[i]:2}", end=" ")
    print()

def set(i: int) -> None:
    for j in range(8):
    	if not flag[j]: # j행에 퀸을 배치하지 않았으면
            pos[i] = j # 퀸을 j행에 위치시킴
    	    if i == 7: # i가 7이라는 것은 모든 열에 퀸을 위치시킨 것(반복문이 끝날 수 있는 조건)을 의미한다.
                put()
            else:
                flag[j] = True
                set(i + 1) # 다음 열에 퀸을 배치함
                flag[j] = False
            
set(0) # 가장 처음에 0열에 퀸을 배치함

코드를 보면 flag라는 새로운 list형 배열을 사용하는데, 이 배열은 같은 행에 중복하여 퀸을 배치하지 않기 위한 표시, 즉 규칙2를 만족할 수 있게 하는 방법이 적용된 것이다. j행에 퀸을 배치하면 flag[j]를 True로, 배치하지 않으면 flag[j]를 False로 한다.

 

위 코드의 실행 순서를 자세히 살펴보면 다음과 같다.

1) 0열에 퀸을 배치하기 위해 호출된 set( ) 함수는 for문의 동작으로 j를 0~7까지 1씩 증가시킨다.

2) 처음에는 flag[0]이 False이므로 0행에 퀸을 배치한다.

3) 이후 flag[0]에 True를 대입하고 set( ) 함수를 재귀적으로 호출한다.

4) 호출된 set( ) 함수에서는 다음열인 1열에 퀸을 배치한다.

 

그리고 재귀 호출한 set(i + 1) 함수가 끝나면 퀸을 j행에서 제거해야 하기때문에 flag[j]에 아직 배치하지 않았다는 것을 체크해주는 False를 대입한다. set( ) 함수에서는 퀸을 아직 배치하지 않은 행(flag[j]가 False인 행)에만 퀸을 배치할 수 있다. 

이처럼 필요하지 않은 분기를 없애서 불필요한 조합을 열거하지 않는 방법을 한정(bounding)작업이라고 함. 그리고 분기 작업과 한정 작업을 조합해서 문제를 풀이하는 방법을 분기 한정법(branching and bounding method)이라고 한다.

 

8퀸 문제 해결 프로그램

마지막으로 아래 코드는 퀸이 행과 열 방향으로 겹치지 않는 조합을 나열하는 프로그램이다. 8퀸 문제를 해결할 수 있으며 대각선 배치의 문제도 해결한 코드이다.

# 행과 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열하기
pos = [0] * 8 # 각 열에서 퀸의 위치
flag_a = [False] * 8 # 각 행에 퀸을 배치했는지 체크
flag_b = [False] * 15 # 대각선 방향(↗↙)으로 퀸을 배치했는지 체크
flag_c = [False] * 15 # 대각선 방향(↘↖)으로 퀸을 배치했는지 체크

def put() -> None: # 각 열에 배치한 퀸의 위치를 출력
    for j in range(8):
        for i in range(8):
            print("■" if pos[i] == j else "□", end=" ")
        print()
    print()

def set(i: int) -> None: # i열의 알맞은 위치에 퀸을 배치
    for j in range(8):
        if(     not flag_a[j] # j행에 퀸을 배치하지 않았으면
            and not flag_b[i + j]
            and not flag_c[i - j + 7]):
            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열에 퀸을 배치

flag_b와 flag_c 배열을 추가하여 대각선 방향에 퀸을 배치했는지 검토하도록 작성했다. 코드 실행 과정 중 대각선 방향에 퀸이 배치되었다면, 다른 칸에는 더 이상 배치할 수 없도록 set 함수 내부의 조건문은 실행되지 않게된다.

 

8퀸 문제는 다른 재귀 알고리즘을 몇가지 풀어보고 나중에 다시 풀어보는 편이 좋을 듯 하다.