[[분류:체스]][[분류:퍼즐]][[분류:알고리즘]]
[목차]
== 개요 ==
여덟 퀸 문제는 1848년 막스 베첼이 처음으로 제안한 퍼즐 문제로, [[수학]]과 [[컴퓨터 과학]]에서 [[알고리즘]] 문제로 많이 거론된다.

8×8 [[체스]]판에 8개의 [[퀸(체스)|퀸]]을 배치하는데, 이 때 어떤 퀸도 다른 퀸을 위협해서는 안된다는 조건이 있다. 체스를 모르는 사람들을 위해 퀸에 대해 간단히 설명하자면, 퀸은 상하좌우, 대각선 4방향으로 거리 제한 없이 이동할 수 있는 기물이다. 결국 서로의 퀸이 움직이는 경로에 다른 퀸이 있어서는 안 된다는 뜻이다.

=== 해답 ===
[[파일:8퀸 문제 해법.png]]
위와 같이 12개의 기본 형태가 있으며, 이를 근본해라고 한다. 대칭인 마지막 패턴(4개, 180도 회전과 상하대칭이 겹침)을 제외하고 각 8개를 회전(4개) 및 대칭이동(4개) 으로 만들 수 있으므로, 여덟 퀸의 경우 총 92개의 해가 있다.
== n-Queens 문제 ==
n-Queens 문제는 n개의 여왕말을 n×n 체스판에 서로 위협하지 않도록 배치하는 문제로서, 여덟 퀸 문제를 일반화한 알고리즘 문제다. 일반화된 n-Queens 문제에 대한 해법으로는, n이 2, 3인 경우를 제외하고 모든 자연수에서 해를 찾을 수 있다.

=== n-Queens 문제의 해 ===
n개의 퀸을 n×n 체스판에 나타내는 해의 수는 n에 따라 달라진다. 고유한 해(대칭인 해를 제외한 해)는 온라인 정수열 사전([[http://oeisf.org/|OEIS]])에서 수열 [[https://oeis.org/A002562|A002562]]로 등록되어 있다. 일반적인 해(대칭을 구별하는 해)는 OEIS의 수열 [[https://oeis.org/A000170|A000170]]으로 등록되어 있다.

=== 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 문제를 백트래킹으로 푸는 방법은 [[https://youtu.be/HRwFgtiqHH0|이 영상]][* [[https://youtu.be/HRwFgtiqHH0|백트래킹과 n-Queens 문제]]]에 자세히 나오고, 위 소스 코드 구현에 대한 설명은 [[https://youtu.be/z4wKvYdd6wM|이 영상]][* [[https://youtu.be/z4wKvYdd6wM|n-Queens 문제의 구현]]]에 나와 있다.