N-Queens II

각 행에는 퀸이 정확히 하나 있어야 하므로, 배치는 cols 목록으로 나타내며 cols[r]는 r번째 행에 있는 퀸의 열입니다. 각 항목은 n개의 열 중 어느 것이든 될 수 있으므로 목록은 n^n개입니다. 주행 거리계가 세는 방식으로 모든 경우를 차례로 살펴봅니다. 마지막 항목을 1씩 늘리고, n-1을 넘으면 0으로 재설정한 뒤 그 앞 항목에 올림을 합니다.

각 목록에 대해 모든 행 쌍 i < j를 비교합니다. 두 퀸은 같은 열에 있거나(cols[i] == cols[j]) 대각선에 있을 때 서로 공격합니다. 대각선에서는 한 행 아래로 이동할 때 열이 왼쪽이나 오른쪽으로 하나 이동하므로, 두 퀸이 같은 대각선에 있는 조건은 열 차이가 행 차이와 같은 경우입니다. 즉, |cols[i] - cols[j]| == j - i입니다. 모든 쌍 검사에 통과한 목록은 유효한 보드 하나입니다. 모든 목록을 확인하므로 누락되거나 두 번 계산되는 경우는 없습니다.

이 방법은 일찍 멈추지 않기 때문에 느립니다. 처음 두 행의 퀸이 같은 대각선에 있으면 보드는 이미 실패한 것이지만, 주행 거리계는 나머지 행을 채우는 n^(n-2)가지 방법을 모두 시도합니다. n = 8이면 보드 92개를 찾기 위해 목록 16,777,216개를 검사합니다. n = 12이면 목록이 약 8.9 × 10^12개입니다. 목록 하나를 검사하는 데 1나노초가 걸린다고 해도 약 2.5시간이 걸립니다.

퀸을 맨 위에서부터 행마다 배치하고, 새 퀸을 놓는 즉시 확인합니다. 공격받는다면 아래 행을 어떻게 채워도 해결할 수 없으므로 그 칸은 바로 건너뜁니다. 안전하다면 다음 행으로 재귀 호출하고, 그 호출이 반환되면 퀸을 제거한 뒤 다음 열을 시도합니다. 행 n에 도달하는 호출은 안전한 퀸 n개를 배치한 것이므로 보드 하나로 셉니다. 이것이 백트래킹이며, 탐색 공간을 크게 가지치기합니다. n = 12일 때 전체 배치 8.9 × 10^12개 대신 부분 보드 856,189개를 방문합니다.

나머지 절반은 칸을 빠르게 검사하는 것입니다. 아래 행은 비어 있고 새 퀸이 놓인 행에도 다른 퀸이 없으므로, 칸 (row, c)를 공격할 수 있는 선은 세 개뿐입니다. 열, / 대각선, \ 대각선입니다. 하나의 / 대각선에 있는 모든 칸은 0부터 2n-2까지 같은 row + c 값을 가집니다. 하나의 \ 대각선에 있는 모든 칸은 -(n-1)부터 n-1까지 같은 row - c 값을 가지므로, n-1을 더해 0부터 2n-2까지의 인덱스를 얻습니다. 플래그 배열 세 개를 유지합니다. 크기가 n인 cols와 크기가 2n-1인 diag, anti입니다. 세 플래그가 모두 꺼져 있을 때만 해당 칸은 안전합니다. 조회 세 번으로 O(1)이며, 지금까지 배치한 퀸을 하나씩 모두 비교하면 O(n)이 듭니다.

한 선에는 퀸을 최대 하나만 둘 수 있으므로, 퀸을 놓을 때 세 플래그를 켜고 제거할 때 다시 끄면 배열은 원래 상태 그대로 유지됩니다. 4 × 4 보드에서 (0, 0)에 있는 퀸은 cols[0], diag[0], anti[3]을 설정합니다. 1행의 1열은 anti[3]에 놓이므로 퀸 자체를 확인하지 않고 건너뜁니다.

첫 번째 행에는 n개의 열을 시도할 수 있고, 두 번째 행에는 많아야 n-1개를 시도할 수 있으며, 이후에도 이와 같이 줄어듭니다. 따라서 탐색은 O(n!)으로 제한되며, 대각선 조건으로 실제 탐색량은 이보다 훨씬 줄어듭니다. n = 12일 때 반복문은 총 10,103,868개의 칸을 검사합니다. 재귀 깊이는 n번 호출이며 배열에는 약 5n개의 플래그가 들어가므로, 공간 복잡도는 O(n)입니다.

집합을 사용하는 탐색은 빠르지만, 각 행에서 여전히 n개의 열을 모두 검사하며, 그중 대부분은 공격받는 칸입니다. 비트마스크를 사용하면 비어 있는 칸으로 바로 이동할 수 있습니다. 정수의 비트 c가 채우려는 행의 열 c를 나타내도록 하고, 세 가지 마스크를 유지합니다. cols는 이미 차지한 열, left는 이 행에서 한 대각선 방향으로 공격받는 칸, right는 다른 대각선 방향으로 공격받는 칸입니다.

그러면 비어 있는 칸은 하나의 식으로 구할 수 있습니다. free = ~(cols | left | right) & full이며, 여기서 full은 하위 n개 비트를 1로 설정한 값입니다. free & -free는 가장 낮은 위치의 비어 있는 칸만 남기고, 이를 빼면 다음 칸으로 이동합니다. bit 위치에 퀸을 놓고 한 행 아래로 내려가면, 해당 열은 계속 차지된 상태이고 각 대각선 공격은 한 열 옆으로 이동합니다. 따라서 다음 행에는 cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1이 전달됩니다. 되돌릴 것은 없습니다. 각 호출은 자체적인 세 정수를 사용합니다. cols == full이면 n개의 퀸을 모두 놓은 것입니다.

n = 4이고 첫 번째 퀸을 열 1에 놓는다고 합시다. 열 0을 가장 오른쪽 비트로 표기하면 bit = 0010입니다. 그러면 행 1에는 cols = 0010, left = 0100, right = 0001이 전달되므로 free = 1000입니다. 열 3만 선택할 수 있으며, 열 0, 1, 2를 검사하지 않고도 찾을 수 있습니다.

탐색은 집합 버전과 동일한 부분 보드를 방문하지만, 이제 루프의 각 단계에서 퀸을 하나 놓습니다. n = 12일 때 정수 연산을 몇 번씩 수행하며 10,103,868번의 칸 검사 대신 856,188번의 단계만 거칩니다. 시간 복잡도는 여전히 O(n!)으로 제한되고, 재귀 깊이는 n번의 호출입니다. R 코드는 재귀 없이 동일한 마스크를 실행합니다. 한 행의 모든 부분 보드를 벡터에 보관하고 매번 한 행씩 모두 확장하므로, n번의 호출 대신 보드의 한 단계 전체를 메모리에 보관합니다.