1. 개요
여덟 퀸 문제는 1848년 막스 베첼이 처음으로 제안한 퍼즐 문제로, 수학과 컴퓨터 과학에서 알고리즘 문제로 많이 거론된다.8×8 체스판에 8개의 퀸을 배치하는데, 이 때 어떤 퀸도 다른 퀸을 위협해서는 안된다는 조건이 있다. 체스를 모르는 사람들을 위해 퀸에 대해 간단히 설명하자면, 퀸은 상하좌우, 대각선 4방향으로 거리 제한 없이 이동할 수 있는 기물이다. 결국 서로의 퀸이 움직이는 경로에 다른 퀸이 있어서는 안 된다는 뜻이다.
1.1. 해답
위와 같이 12개의 기본 형태가 있으며, 이를 근본해라고 한다. 대칭인 마지막 패턴(4개, 180도 회전과 상하대칭이 겹침)을 제외하고 각 8개를 회전(4개) 및 대칭이동(4개) 으로 만들 수 있으므로, 여덟 퀸의 경우 총 92개의 해가 있다.
2. n-Queens 문제
n-Queens 문제는 n개의 여왕말을 n×n 체스판에 서로 위협하지 않도록 배치하는 문제로서, 여덟 퀸 문제를 일반화한 알고리즘 문제다. 일반화된 n-Queens 문제에 대한 해법으로는, n이 2, 3인 경우를 제외하고 모든 자연수에서 해를 찾을 수 있다.2.1. n-Queens 문제의 해
n개의 퀸을 n×n 체스판에 나타내는 해의 수는 n에 따라 달라진다. 고유한 해(대칭인 해를 제외한 해)는 온라인 정수열 사전(OEIS)에서 수열 A002562로 등록되어 있다. 일반적인 해(대칭을 구별하는 해)는 OEIS의 수열 A000170으로 등록되어 있다.2.2. n-Queens 문제와 백트래킹 방법
n-Queens 문제는 알고리즘 설계 기법 중 하나인 백트래킹 방법으로 해결한다. 아래는 백트래킹으로 n-Queens 문제를 해결하는 파이썬 구현 소스 코드이다.#!syntax python
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
n-Queens 문제를 백트래킹으로 푸는 방법은 이 영상[1]에 자세히 나오고, 위 소스 코드 구현에 대한 설명은 이 영상[2]에 나와 있다.