여덟 개의 여왕 퍼즐

Eight queens puzzle
abcdefgh
8
Chessboard480.svg
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
8개의 퀸 퍼즐에 대한 유일한 대칭 솔루션(회전 및 반사까지)

8개의 퀸 퍼즐은 8×8개의 체스판에 8개의 체스 퀸을 배치하여 어떤 퀸도 서로를 위협하지 않도록 하는 문제입니다. 따라서, 어떤 퀸도 같은 행, 열 또는 대각선을 공유하지 않아야 합니다.92개의 솔루션이 있습니다.이 문제는 19세기 중반에 처음 제기되었다.현대에는 다양한 컴퓨터 프로그래밍 기법의 예시적인 문제로 자주 사용된다.

8개의 퀸 퍼즐은 n개의 공격하지 않는 퀸을 n개의 체스판에 배치하는 더 일반적인 n개의 퀸 문제의 특별한 경우이다.해는 n = 2 및 n = 3을 제외한 모든 자연수 n에 대해 존재한다.정확한 용액 수는 n ≤ 27에 대해서만 알려져 있지만, 용액 수의 점근 증가율은 (0.143 n)n이다.

역사

체스 작곡가 맥스 베젤은 1848년에 8개의 여왕 퍼즐을 발표했다.프란츠 나우크는 [1]1850년에 첫 번째 해결책을 발표했다.Nauck은 또한 n개의 정사각형의 체스판에 n개의 퀸이 있는 n개의 퀸 문제로 퍼즐을 확장했다.

그 이후로, 칼 프리드리히 가우스를 포함한 많은 수학자들은 8개의 여왕 퍼즐과 그것의 일반화된 n-queen 버전 모두에 대해 연구해왔다.1874년, S. Gunther는 해결책을 [1]찾기 위해 결정 인자를 사용하는 방법을 제안했다. J.W.L. Glaisher는 Gunther의 접근법을 개선했다.

1972년, Edsger Dijkstra는 그가 구조화 프로그래밍이라고 부르는 것의 힘을 설명하기 위해 이 문제를 사용했다.그는 깊이 우선 역추적 [2]알고리즘에 대한 매우 상세한 설명을 발표했다.

n = 8일 때 솔루션 구성 및 계수

8x8 [a]보드에 8개의 퀸을 배열할 수 있는 것은 4,426,165,368개이지만 92개의 솔루션밖에 없기 때문에 8개의 퀸 문제에 대한 모든 솔루션을 찾는 문제는 계산적으로 상당히 비쌀 수 있습니다.계산 요건을 줄이는 단축키 또는 무차별 계산 기술을 사용하지 않는 경험적 규칙을 사용할 수 있습니다.예를 들어, 각 열에서 하나의 여왕을 선택하는 간단한 규칙을 적용하면 가능한 조합의 수를 16,777,216(즉8, 8)으로 줄일 수 있습니다.순열을 생성하면 40,320(즉, 8!)으로 줄어들어 대각선 공격을 확인할 수 있습니다.

8개의 퀸 퍼즐은 92개의 다른 해답을 가지고 있다.기판의 회전과 반사의 대칭 연산에 의해서만 다른 해를 1로 계산하면 퍼즐은 12개의 해를 가진다.이러한 솔루션을 기본 솔루션이라고 합니다.각 솔루션의 대표자는 다음과 같습니다.

기본 솔루션에는 보통 90도, 180도 또는 270도를 회전시킨 다음 거울에 4개의 회전 변형을 각각 반영하여 얻은 8개의 변종(원형 포함)이 있습니다.그러나 12개의 기본 솔루션 중 하나(아래 솔루션 12)는 자체 180° 회전과 동일하므로 4개의 변형(본인과 반사, 90° 회전 및 반사)[b]만 있습니다.이러한 솔루션에는 두 가지 변종(그 자체와 그 반영)만 있습니다.따라서, 구별되는 솔루션의 총 수는 11×8 + 1×4 = 92이다.

모든 기본 솔루션은 다음과 같습니다.

솔루션 10에는 세 개의 퀸이 일직선에 있지 않다는 추가 특성이 있습니다.솔루션 1과 8의 행은 4퀸입니다.

솔루션의 존재

솔루션 수를 계산하기 위한 브루트포스 알고리즘은 n = 8의 경우 계산적으로 관리할 수 있지만, 20! = 2.433 × 10의18 경우 n † 20의 문제에 대해서는 다루기 어렵다.하나의 솔루션을 찾는 것이 목적이라면 검색 [3][4]없이 모든 n/4에 대해 솔루션이 존재함을 나타낼 수 있습니다.이러한 솔루션은 n = 8, 9, 10에 대한 다음 예시와 같이 계단식 패턴을 보인다.

위의 예는 다음 [3]공식으로 얻을 수 있습니다.(i, j)를 n × n 체스판의 i열과 j행의 정사각형, k는 정수라고 하자.

한[3] 가지 방법은

  1. n을 6으로 나눈 나머지가 2 또는 3이 아닐 경우 목록은 단순히 모든 짝수 뒤에 모든 홀수가 n보다 크지 않습니다.
  2. 그렇지 않은 경우 짝수 및 홀수(2, 4, 6, 8 – 1, 3, 5, 7) 목록을 별도로 작성합니다.
  3. 나머지가 2인 경우는, 홀수 리스트의 1과 3을 스왑 해, 5를 끝(3, 1, 7, 5)으로 이동합니다.
  4. 나머지가 3인 경우는, 짝수 리스트의 마지막에 2, 홀수 리스트의 마지막에 1,3 을 이동합니다(4, 6, 8, 2 – 5, 7, 1, 3).
  5. 짝수 목록에 홀수 목록을 추가하고 이 숫자에 의해 주어진 행(a2, b4, c6, d8, e3, f1, g7, h5)에 퀸을 배치합니다.

n = 8의 경우 위의 기본 솔루션 1이 됩니다.다음은 몇 가지 예를 제시하겠습니다.

  • 여왕 14명(2명): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
  • 여왕 15명(3명): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
  • 여왕 20명(2명): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

기타 사이즈에 대한 솔루션 카운트 n

정확한 열거

n x n의 보드에 n개의 퀸을 배치하기 위한 정확한 솔루션 수에 대한 공식은 알려져 있지 않다. 즉, n x n의 퀸 그래프에서 크기 n의 독립 집합의 수.27×27 보드는 완전히 [5]열거된 가장 높은 순서의 보드입니다.다음 표는 기본(OEIS의 시퀀스 A002562)과 모든(OEIS의 시퀀스 A000170) 모두 알려진 모든 경우에 대한 n개의 퀸 문제에 대한 해결책의 수를 나타낸다.

n 근본적인 모든.
1 1 1
2 0 0
3 0 0
4 1 2
5 2 10
6 1 4
7 6 40
8 12 92
9 46 352
10 92 724
11 341 2,680
12 1,787 14,200
13 9,233 73,712
14 45,752 365,596
15 285,053 2,279,184
16 1,846,955 14,772,512
17 11,977,939 95,815,104
18 83,263,591 666,090,624
19 621,012,754 4,968,057,848
20 4,878,666,808 39,029,188,884
21 39,333,324,973 314,666,222,712
22 336,376,244,042 2,691,008,701,644
23 3,029,242,658,210 24,233,937,684,440
24 28,439,272,956,934 227,514,171,973,736
25 275,986,683,743,434 2,207,893,435,808,352
26 2,789,712,466,510,289 22,317,699,616,364,044
27 29,363,495,934,315,694 234,907,967,154,122,528

점근 열거

2021년 Michael Simkin은 큰 수 n에 대해 n개의 퀸즈 문제의 해답 가약 . n[6]이라는 것을 증명했다. 보다 정확히는 Q( \} (n \} (n)}의 이 점근적으로 증가한다는 것을 증명했다.

서α {\는 1.939 ~1.945 [7]범위의 상수입니다(여기서 o(1)는 작은 o 표기법을 나타냅니다).

대신 트로이덜 체스보드(대각선이 상단 모서리에서 하단, 왼쪽 모서리에서 오른쪽 모서리로 "감겨져" 있는 경우)를 고려할 경우 n개의 퀸을 ×n(\nn) 위에 배치할 수 있는 은 n 1, 5 뿐입니다 이 경우, 점근적 숫자입니다ons는[8][9]

관련 문제

고차원
크기 n의 d차원 체스에 배치할 수 있는 공격하지 않는 퀸의 수를 구한다.n개 이상의 퀸을 더 높은 차원에 배치할 수 있으며(3×3×3 체스 공간에서 공격하지 않는 퀸 4개가 가장 작은 예) 실제로 k에 대해 n개의 [10][11]퀸이 모든 공간을 공격하기에 충분하지 않은 더 높은 차원이 있는 것으로k 알려져 있다.
퀸 이외의 피스 사용
8×8 보드에는 32명의 기사, 14명의 비숍, 16명의 킹 또는 8명의 루크를 배치할 수 있어 두 조각이 서로 공격하지 않습니다.요정 체스 조각은 여왕을 대신하기도 했다.기사들의 경우, 그들은 오직 반대 색상으로만 이동하기 때문에, 각각의 사각형에 하나씩 배치하는 것이 쉬운 해결책이다.그 해결책은 또한 루크와 왕들에게도 쉽다.8개의 룩을 긴 대각선을 따라 배치할 수 있으며(다른 수천 개의 솔루션 중), 16개의 킹을 2x2 정사각형으로 나누고 킹을 각 정사각형의 동등한 포인트에 배치하여 보드 위에 배치할 수 있습니다.
체스의 변형
장기 등 체스의 변형에 대해서도 관련 문제를 제기할 수 있다.예를 들어, n+k 용왕 문제는 k 장기 폰과 n+k 상호 공격하지 않는 용왕을 n×[12]n 장기판에 배치하도록 요구한다.
치환 행렬
수학에서 치환행렬은 각 행 또는 열이 하나의 점만을 포함하도록 n개의 점의 집합으로 기하학적으로 간주할 수 있다.따라서, 순서-n 치환 행렬은 n-rooks 퍼즐의 해답입니다.
비표준 보드
폴랴는 트로이덜("도넛 모양") 보드의 n개의 여왕 문제를 연구하여 n이 2 또는 [13]3으로 나누어지지 않는 경우에만 n×n 보드에 해답이 있음을 보여주었다.2009년 Pearson과 Pearson은 알고리즘에 3차원 보드(n×n×n)를2 n개의 퀸으로 채웠고,[14][better source needed] 이들 중 배수가 퍼즐의 4차원 버전에 대한 해답을 산출할 수 있다고 제안했다.
지배
n×n 보드를 지정하면 지배 숫자는 각 정사각형을 공격하거나 점유하는 데 필요한 최소 퀸(또는 다른 조각) 수입니다.n = 8인 경우 여왕의 지배 번호는 [15][16]5이다.
퀸스 기타 피스
변형에는 다른 조각과 퀸을 혼합하는 것이 포함됩니다. 예를 들어, n×n 보드 위에 m개의 퀸과 m의 기사를 배치하여 다른 조각이 공격받지[17] 않도록 하거나, 두 개의 퀸이 서로 [18][better source needed]공격하지 않도록 퀸과 폰을 배치하는 것입니다.
매직 스퀘어
1992년, 데미르뢰르스, 라프라프, 타닉은 일부 매직 스퀘어를 n-queens 솔루션으로 변환하는 방법을 발표했고,[19] 그 반대의 경우도 마찬가지였다.
라틴 사각형
n×n 행렬에서 각 자리수 1~n을 행렬 내의 n개 위치에 배치하여 같은 자리수의 두 인스턴스가 같은 행 또는 열에 없도록 합니다.
정확한 커버
보드의 각 n개 등급에 대해 1개의 프라이머리 컬럼, 각 n개 파일에 대해 1개의 프라이머리 컬럼 및 보드의 4n~6개의 중요하지 않은 대각선 각각에 대해 1개의 세컨더리 컬럼이 있는 매트릭스를 검토합니다.행렬에는 가능한 각 여왕 배치에 대해 하나씩 n개의 행이 있으며2 각 행은 해당 사각형의 순위, 파일 및 대각선에 해당하는 열에 1이 있고 다른 모든 열에 0이 있습니다.다음으로 n개의 퀸즈 문제는 이 행렬의 행의 서브셋을 선택하는 것과 같습니다.즉, 모든 프라이머리 컬럼이 정확히 선택된 행 중 하나에 1을 가지며, 모든 세컨더리 컬럼이 최대 1개의 행에 1을 가지도록 합니다.이것은 스도쿠와 같은 일반화된 정확한 커버 문제의 예입니다.
n-Queens 완료
2017년[20] 한 논문은 "일부 여왕이 이미 배치된 n×n 체스판이 주어졌을 때, 두 여왕이 서로 공격하지 않도록 나머지 모든 줄에 여왕을 배치할 수 있는가?"와 관련된 몇 가지 문제를 조사했다.저자들은 이러한 문제들이 NP-완전[21] 및 #P-완전이라고 주장했다.

알고리즘 설계 연습

8개의 퀸 퍼즐에 대한 모든 해답을 찾는 것은 간단하지만 사소한 문제의 좋은 예이다.이러한 이유로, 제약 조건 프로그래밍, 논리 프로그래밍 또는 유전 알고리즘과 같은 비전통적 접근법을 포함한 다양한 프로그래밍 기술에 대한 예제 문제로 종종 사용됩니다.n×n 체스판에 n-1의 퀸을 배치하는 문제에 대한 해답에 단일 퀸을 추가하는 관점에서 n의 퀸 문제를 유도적으로 표현함으로써 재귀 알고리즘으로 해결할 수 있는 문제의 예로서 가장 많이 사용된다.이 인덕션은 0개의 여왕을 체스판에 놓는 문제, 즉 빈 체스판에 놓는 문제에 대한 해결책으로 끝을 맺는다.

이 기법은 훨씬 더 모두 648년=248=8퀸의 281,474,976,710,656 가능한 맹목적인 위치에 배치하고, 그 다음 같은 광장(만 64를 타거나 두 여왕들 모두 배치를 제거하기!/56 이 걸러 낸다!=178,462,987,637,760 possib고 고민하는 순진한 억지 검색 알고리즘보다 보다 효율적인 방법으로 사용될 수 있다.르배치) 또는 상호 공격 위치에 있어야 합니다.이 매우 빈약한 알고리즘은 특히 8개의 퀸이 할당한 모든 다른 배열에서 동일한 결과를 반복적으로 생성할 뿐만 아니라 각 솔루션의 서로 다른 하위 집합에 대해 동일한 계산을 반복할 수 있습니다.더 나은 브루트포스 알고리즘은 각 행에 단일 퀸을 배치하여 8 = 224 = 16,126,216개의 블라인드 배치만 가능하게8 합니다.

이것보다 훨씬 더 잘할 수 있다.한 알고리즘은 숫자 1~8(그 중 8! = 40,320)의 순열을 생성하여 8개의 룩 퍼즐을 풀고 각 순열의 요소를 지수로 사용하여 각 행에 여왕을 배치합니다.그런 다음 대각선 공격 위치를 가진 보드를 거부합니다.

이 애니메이션은 문제를 해결하기 위한 역추적을 보여 줍니다.여왕은 충돌을 일으키지 않는 것으로 알려진 기둥에 배치되어 있다.열을 찾을 수 없는 경우 프로그램은 마지막 정상 상태로 돌아가 다른 열을 시도합니다.

순열 방법을 약간 개선한 백트랙 깊이 우선 검색 프로그램은 보드의 한 행을 한 번에 하나씩 고려하여 검색 트리를 구성하며, 구축 초기 단계에서 대부분의 비해결 보드 위치를 제거합니다.불완전한 보드에서도 루크와 대각선 공격을 거부하기 때문에 1만5720개의 퀸 배치만 조사한다.또한 5,508개의 가능한 퀸 배치만 검사하는 추가 개선사항은 치환 기반 방법과 초기 가지치기 방법을 결합하는 것이다. 즉, 치열이 깊이 우선으로 생성되고 부분 치환에 의해 대각선 공격이 발생할 경우 서치 공간이 가지치기된다.제약 조건 프로그래밍도 이 문제에 매우 효과적일 수 있습니다.

최소 8개 퀸 솔루션

전체 검색의 대안으로 '반복 수리' 알고리즘이 있습니다. 이 알고리즘은 일반적으로 보드의 모든 퀸(예: [22]열당 퀸 하나)으로 시작합니다.그런 다음 충돌(공격) 수를 카운트하고 경험적 접근법을 사용하여 여왕의 배치를 개선하는 방법을 결정합니다.충돌 수가 가장 많은 작품을 충돌 수가 가장 적은 같은 열의 정사각형으로 이동시키는 '최소 충돌' 휴리스틱은 특히 효과적입니다. 평균 50단계 [citation needed]미만으로 1,000,000 퀸 문제에 대한 해결책을 찾습니다.이는 초기 구성이 '합리적으로 양호한 상태'라고 가정합니다. 백만 퀸이 모두 같은 행에서 시작할 경우 이를 수정하려면 최소 999,999개의 단계가 필요합니다.예를 들어 '합리적으로 양호한' 출발점은 각 퀸을 자체 행과 열에 배치하여 보드에 이미 있는 최소 퀸 수와 충돌하도록 함으로써 찾을 수 있습니다.

위에서 설명한 역추적 검색과 달리 반복적인 복구는 해결책을 보장하지 않습니다. 모든 까다로운 절차와 마찬가지로 로컬 최적화에 고착될 수 있습니다.(이 경우, 다른 초기 설정으로 알고리즘을 재기동할 수 있습니다).한편, 깊이 우선 검색 범위를 벗어나는 몇 가지 크기의 문제를 해결할 수 있습니다.

백트래킹의 대안으로 유효한 부분 솔루션을 한 번에 한 줄씩 반복적으로 열거하여 솔루션을 계산할 수 있습니다.전체 보드 위치를 구성하는 대신 차단된 대각선과 열을 비트 연산으로 추적합니다.따라서 개별 솔루션을 [23][24]복구할 수 없습니다.

샘플 프로그램

다음 프로그램은 Niklaus Worth의 솔루션을 Python 프로그래밍 언어로 번역한 것이지만 원본에서 찾을 수 있는 인덱스 산술 없이 대신 목록을 사용하여 프로그램 코드를 최대한 단순하게 유지합니다.생성기 함수의 형태로 코루틴을 사용함으로써 원본의 두 버전을 통일하여 하나의 솔루션 또는 모든 솔루션을 계산할 수 있다.15,720개의 가능한 퀸 배치만 [25][26]검사됩니다. 

방어하다 퀸즈(n, i, a, b, c):     한다면 i < > n:         위해서 j 에 범위(n):             한다면 j 것은 아니다. 에 a 그리고. i+j 것은 아니다. 에 b 그리고. i-j 것은 아니다. 에 c:                 에서 산출하다. 퀸즈(n, i+1, a+[j], b+[i+j], c+[i-j])     또 다른:         산출하다 a  위해서 해결 방법 에 퀸즈(8, 0, [], [], []):     인쇄물(해결 방법)

대중문화에서

  • 게임 The 7th Guest에서 Stauf 저택 게임실에 있는 8번째 퍼즐: "The Queen's Delema"는 사실상의 8번째 퀸 [27]: 48–49, 289–290 퍼즐이다.
  • 레이튼 교수와 호기심 마을에서 130번째 퍼즐: "너무 많은 여왕 5"는 8개의 여왕 [28]퍼즐이다.

「 」를 참조해 주세요.

메모들

  1. ^ 64에서 8제곱의 조합 수는 이항8 계수 C입니다.
  2. ^ 다른 대칭은 n의 다른 값에 대해서도 가능합니다.예를 들어, 자체 90° 회전과 동일한 5×5 보드 위에 공격하지 않는 5개의 퀸을 배치한다.n > 1일 경우 두 개의 퀸이 서로 마주보고 있어야 하기 때문에 용액이 자체 반사와 동일할 수 없습니다.

레퍼런스

  1. ^ a b W. W. Rouse Ball(1960) "8명의 여왕 문제", 뉴욕 맥밀런 수학 레크리에이션 및 에세이, 165–171페이지.
  2. ^ O.-J. Dahl, E. W. Dijkstra, C. A. R. HoareStructured Programming, 런던, 학술 프레스, 1972 ISBN0-12-200550-3, 페이지 72-82.
  3. ^ a b c Bo Bernhardsson (1991). "Explicit Solutions to the N-Queens Problem for All N". SIGART Bull. 2 (2): 7. doi:10.1145/122319.122322. S2CID 10644706.
  4. ^ E. J. Hoffman et al., "M Queens 문제의 해법을 위한 구성"수학잡지 제X권(1969), 66~72페이지.[1]
  5. ^ Q27 프로젝트
  6. ^ Sloman, Leila (21 September 2021). "Mathematician Answers Chess Problem About Attacking Queens". Quanta Magazine. Retrieved 22 September 2021.
  7. ^ Simkin, Michael (28 July 2021). "The number of $n$-queens configurations". arXiv:2107.13460v2 [math.CO].
  8. ^ Luria, Zur (15 May 2017). "New bounds on the number of n-queens configurations". arXiv:1705.05225v2 [math.CO].
  9. ^ Bowtell, Candida; Keevash, Peter (16 September 2021). "The $n$-queens problem". arXiv:2109.08083v1 [math.CO].
  10. ^ J. Bar와 S.Rao (2006년),고차원의 n-Queens 문제, Elemente der Mathik, vol 61(4), 페이지 133–137.
  11. ^ Martin S. Pearson. "Queens On A Chessboard – Beyond The 2nd Dimension" (php). Retrieved 27 January 2020.
  12. ^ Chatham, Doug (1 December 2018). "Reflections on the n +k dragon kings problem". Recreational Mathematics Magazine. 5 (10): 39–55. doi:10.2478/rmm-2018-0007.
  13. ^ G. Pollya, Uber die "dopelt-periodischen" Losungen des n-Damen-Problems, George Pollya: 논문 수집량 Vol.IV, G-C. Rota, ed., MIT Press, 케임브리지, 런던, 1984, 페이지 237–247
  14. ^ "Queens on a Chessboard - Beyond the 2nd Dimension".
  15. ^ Burger, A. P.; Cockayne, E. J.; Mynhardt, C. M. (1997), "Domination and irredundance in the queens' graph", Discrete Mathematics, 163 (1–3): 47–66, doi:10.1016/0012-365X(95)00327-S, hdl:1828/2670, MR 1428557
  16. ^ Weakley, William D. (2018), "Queens around the world in twenty-five years", in Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Graph Theory: Favorite Conjectures and Open Problems – 2, Problem Books in Mathematics, Cham: Springer, pp. 43–54, doi:10.1007/978-3-319-97686-0_5, MR 3889146
  17. ^ "Queens and knights problem". Archived from the original on 16 October 2005. Retrieved 20 September 2005.
  18. ^ 9퀸 문제
  19. ^ O. 데미뢰르스, N. 라프라프, M.M. 타니크.마법 사각형에서 n-queen 솔루션을 얻고 n-queen 솔루션에서 마법 사각형 구성.레크리에이션 수학 저널, 1992년 24:272 ~ 280
  20. ^ Gent, Ian P.; Jefferson, Christopher; Nightingale, Peter (August 2017). "Complexity of n-Queens Completion". Journal of Artificial Intelligence Research. 59: 815–848. doi:10.1613/jair.5512. ISSN 1076-9757. Retrieved 7 September 2017.
  21. ^ "The 8-Queens Puzzle". www.claymath.org. Clay Mathematics Institute. 2 September 2017.
  22. ^ Rock Sosic과 Jun Gu의 N-Queen 문제에 대한 다항식 시간 알고리즘, 1990년메모리 제약으로 인해 실행할 수 있는 최대치인 최대 500,000 Queen 실행 시간을 설명합니다.
  23. ^ Qiu, Zongyan (February 2002). "Bit-vector encoding of n-queen problem". ACM SIGPLAN Notices. 37 (2): 68–70. doi:10.1145/568600.568613.
  24. ^ Richards, Martin (1997). Backtracking Algorithms in MCPL using Bit Patterns and Recursion (PDF) (Technical report). University of Cambridge Computer Laboratory. UCAM-CL-TR-433.
  25. ^ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall Series in Automatic Computation. Prentice-Hall. Bibcode:1976adsp.book.....W. ISBN 978-0-13-022418-7. 페이지 145
  26. ^ Wirth, Niklaus (2012) [orig. 2004]. "The Eight Queens Problem". Algorithms and Data Structures (PDF). Oberon version with corrections and authorized modifications. pp. 114–118.
  27. ^ DeMaria, Rusel (15 November 1993). The 7th Guest: The Official Strategy Guide (PDF). Prima Games. ISBN 978-1-5595-8468-5. Retrieved 22 April 2021.
  28. ^ "ナゾ130 クイーンの問題5". ゲームの匠 (in Japanese). Retrieved 17 September 2021.

추가 정보

외부 링크

Wikibook Algorithm Implementation에는 N-queens 문제에 관한 페이지가 있습니다.