맨위로가기

여덟 퀸 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

여덟 퀸 문제는 8개의 퀸을 8x8 체스판에 배치하여 서로 공격할 수 없도록 하는 문제이다. 1848년 막스 베첼이 처음 제시했으며, 프란츠 나우크가 일반화하여 n x n 체스판에 n개의 퀸을 놓는 n 퀸 문제로 확장되었다. 이 문제는 백트래킹, 깊이 우선 탐색, 제약 프로그래밍 등 다양한 알고리즘을 활용하여 해결할 수 있으며, 92개의 해가 존재한다. 여덟 퀸 문제와 관련된 문제로는 다른 체스 기물을 사용하거나, 다른 모양의 체스판을 사용하는 문제, 지배 수 문제 등이 있다. 또한, 이 문제는 제약 프로그래밍, 논리 프로그래밍, 유전 알고리즘 등 다양한 프로그래밍 기법의 예시로 활용되며, 대중문화에서도 찾아볼 수 있다.

더 읽어볼만한 페이지

  • 수학적 체스 문제 - 맨해튼 거리
    맨해튼 거리는 좌표축에 평행하게 측정한 거리 차이의 절댓값 합으로, 택시 기하학이라고도 불리며, 체스 룩의 이동이나 격자 도시 이동 거리 측정에 활용된다.
  • 수학적 체스 문제 - 체비쇼프 거리
    체비쇼프 거리는 두 벡터 또는 점 사이의 거리 측정 방식으로, 각 좌표 성분 차이의 절댓값 중 최댓값으로 정의되며 L∞ 거리라고도 불린다.
  • 열거조합론 - 카탈랑 수
    카탈랑 수는 조합론에서 여러 개수 세기 문제의 해답으로 나타나는 수열로, 괄호 구조, 이진 트리, 다각형 분할 등 다양한 조합론적 대상의 개수를 나타내며 여러 분야에 응용된다.
  • 열거조합론 - 오일러 수 (조합론)
    오일러 수는 조합론에서 집합의 순열 중 특정 조건을 만족하는 순열의 개수를 나타내는 수로, 주로 집합 \{1,2,\ldots,n\}의 순열에서 a_i>a_{i+1}인 i가 정확히 m개 있는 순열의 개수를 나타내며, 오일러 다항식 및 관련 성질과 함께 1755년 레온하르트 오일러에 의해 소개되었다.
  • 퍼즐 - 다른 그림 찾기
    다른 그림 찾기는 거의 동일한 두 그림에서 시각적 비교 등을 통해 서로 다른 부분을 찾아내는 퍼즐이다.
  • 퍼즐 - 몬티 홀 문제
    몬티 홀 문제는 세 개의 문 중 하나를 선택한 후 진행자가 상품이 없는 문을 열어 보여줄 때, 선택을 바꾸는 것이 유리한지를 묻는 확률 문제로, 직관과 달리 선택을 바꾸는 것이 당첨 확률을 높이는 전략임을 보여주는 확률 역설이며, 의사 결정 방식에 대한 통찰을 제공한다.
여덟 퀸 문제
체스 문제
이름
한국어여덟 퀸 문제
영어Eight queens puzzle
일본어エイト・クイーン
성격
종류조합론적 퍼즐
목표체스판 위에 8개의 퀸을 서로 공격할 수 없도록 놓는 문제
역사
창시자막스 베첼
최초 발표1848년
풀이1850년, 프란츠 나우크
해법
해의 총 개수92개
기본해12개
대칭성을 고려한 해1개 (대칭 해)
변형
n-퀸 문제일반화된 문제 (n x n 체스판)
기타
여덟 퀸 문제의 대칭 해
유일한 대칭 해 (회전 및 반사 대칭)
여덟 퀸 문제의 해 중 하나
해 중 하나

2. 역사

체스 작곡가 막스 베첼은 1848년에 여덟 퀸 문제를 발표했다. 프란츠 나우크는 1850년에 최초의 해법을 발표했으며,[1] 이 문제를 ''n''×''n'' 크기의 체스판에 ''n''개의 퀸을 놓는 ''n'' 퀸 문제로 확장했다.

이후 카를 프리드리히 가우스를 포함한 많은 수학자들이 여덟 퀸 문제와 일반화된 ''n'' 퀸 버전에 대해 연구했다. 1874년, S. 귄터는 행렬식을 사용하여 해법을 찾는 방법을 제안했고,[1] J.W.L. 글레이셔는 귄터의 접근 방식을 개선했다.

1972년, 에츠허르 데이크스트라는 이 문제를 사용하여 그가 구조적 프로그래밍이라고 부르는 것의 강력함을 설명했다. 그는 매우 상세한 깊이 우선 탐색 백트래킹 알고리즘에 대한 설명을 발표했다.[2]

3. 규칙

체스판 위에 8개의 퀸을 배치한다. 이때, 어떤 퀸도 다른 퀸에게 공격받는 위치에 놓여서는 안 된다. 즉, 같은 행, 열, 대각선 상에 두 개 이상의 퀸이 위치할 수 없다.

퀸은 상하좌우, 대각선 8방향으로 막는 것이 없는 한 이동할 수 있다. 이는 장기의 비차와 각행의 움직임을 합친 것이다.

4개의 퀸으로 간략하게 설명하면 다음과 같다.

배치 예 A (올바른 배치)



배치 예 B (잘못된 배치)



예 A에서는 어떤 퀸도 다른 퀸을 공격할 수 없으므로 올바른 배치이다. 예 B에서는

두 퀸이 서로 공격할 수 있는 위치에 있으므로 잘못된 배치이다.

4. 해

''n'' × ''n'' 크기의 체스판에 ''n''개의 퀸을 서로 공격할 수 없도록 배치하는 N-퀸 문제의 해는 ''n'' 값에 따라 달라진다. 2-퀸과 3-퀸 문제에는 해가 존재하지 않지만, 4-퀸 문제부터는 해가 존재한다.

''n''이 커질수록 체스판의 크기(''n''2)와 퀸의 개수(''n'')가 모두 증가하여 문제 해결이 복잡해지지만, ''n''이 5에서 6으로 증가할 때는 오히려 해의 개수가 감소하는 특이한 현상이 나타난다.

N-퀸 문제의 해는 기본 해와 변형 해로 나눌 수 있다. 기본 해는 회전이나 대칭을 통해 서로 겹쳐지지 않는 고유한 해를 의미하며, 변형 해는 기본 해를 회전 및 대칭시켜 얻을 수 있는 모든 해를 포함한다.

''n'' = 27까지의 N-퀸 문제 해의 개수는 다음과 같다.[32]

n기본 해변형 해
111
200
300
412
5210
614
7640
81292
946352
1092724
113412,680
121,78714,200
139,23373,712
1445,752365,596
15285,0532,279,184
161,846,95514,772,512
1711,977,93995,815,104
1883,263,591666,090,624
19621,012,7544,968,057,848
204,878,666,80839,029,188,884
2139,333,324,973314,666,222,712
22336,376,244,0422,691,008,701,644
233,029,242,658,21024,233,937,684,440
2428,439,272,956,934227,514,171,973,736
25275,986,683,743,4342,207,893,435,808,352
262,789,712,466,510,28922,317,699,616,364,044
2729,363,791,967,678,199234,907,967,154,122,528



2009년 드레스덴 공과대학에서 26-퀸 문제의 해가 계산되었고,[30] 2016년 Q27 Project를 통해 27-퀸 문제의 모든 해가 밝혀졌다.[31]

4. 1. 8-퀸 문제의 해

8×8 체스판에서 8개의 퀸을 서로 공격할 수 없도록 배치하는 문제에는 92개의 해가 있다. 이 해들은 기본적으로 12가지의 기본 해로 구성되며, 이 기본 해들을 회전시키거나 반사시키는 방식으로 92개의 해를 얻을 수 있다.

다음은 12가지 기본 해를 나타낸 것이다.

------
------
------
------



각 기본 해는 회전과 반사를 통해 여러 가지 변형을 만들 수 있다. 해 1~11은 각각 8가지(회전, 대칭)의 변형을 가지며, 해 12는 점대칭으로 인해 4가지 변형만 가진다. 따라서 전체 해의 개수는 92개(= 8 × 11 + 4)가 된다.

''n'' × ''n'' 판에 ''n''개의 퀸을 배치하는 문제의 해의 수는 다음과 같다.

n1234567891011121314..242526
고유한 해10012161246923411,7879,23345,752..28,439,272,956,934275,986,683,743,4342,789,712,466,510,289
모든 해100210440923527242,68014,20073,712365,596..227,514,171,973,7362,207,893,435,808,35222,317,699,616,364,044


4. 2. N-퀸 문제의 해의 개수

''n'' 퀸 문제는 ''n'' × ''n'' 체스판에 ''n''개의 퀸을 서로 공격할 수 없도록 배치하는 문제이다. 이 문제의 해의 개수는 ''n''이 커짐에 따라 급격히 증가한다.

''n'' 퀸 문제의 해는 기본 해(unique solutions)와 변형 해(distinct solutions) 두 가지로 분류할 수 있다. 기본 해는 회전이나 대칭을 통해 서로 겹쳐지지 않는 해를 의미하며, 변형 해는 회전 및 대칭을 통해 겹쳐지는 해를 모두 포함한다.

''n'' 퀸 문제의 해의 개수는 ''n'' = 27까지 알려져 있다.[32]

n기본 해변형 해
111
200
300
412
5210
614
7640
81292
946352
1092724
113412,680
121,78714,200
139,23373,712
1445,752365,596
15285,0532,279,184
161,846,95514,772,512
1711,977,93995,815,104
1883,263,591666,090,624
19621,012,7544,968,057,848
204,878,666,80839,029,188,884
2139,333,324,973314,666,222,712
22336,376,244,0422,691,008,701,644
233,029,242,658,21024,233,937,684,440
2428,439,272,956,934227,514,171,973,736
25275,986,683,743,4342,207,893,435,808,352
262,789,712,466,510,28922,317,699,616,364,044
2729,363,791,967,678,199234,907,967,154,122,528



''n''이 증가함에 따라 전체 칸 수 ''n''2개에 대해 놓는 말의 수는 ''n''개이므로, 놓을 수 있는 장소(후보)가 증가함에 따라 해의 수에 조합 폭발이 일어난다. 다만, ''n''이 5에서 6으로 증가하는 경우에는 해의 수가 감소한다. 2009년 드레스덴 공과대학에서 26-퀸이 계산되었으며,[30] 현재 모든 해가 밝혀진 최대 해는 2016년에 Q27 Project에 의해 계산된 27-퀸이다.[31]

4. 3. 해의 존재성

n ≥ 4인 모든 n에 대해 해가 존재함을 보일 수 있다.[3]

5. 알고리즘

N-퀸 문제는 백트래킹, 깊이 우선 탐색, 최소 충돌 알고리즘 등 다양한 알고리즘으로 해결할 수 있다. 재귀 호출을 사용하여 해를 구할 수도 있다.[21][22][23]

여덟 퀸 문제의 모든 해를 찾는 것은 간단하지만 만만치 않은 문제의 좋은 예시이며, 제약 프로그래밍, 논리 프로그래밍, 유전 알고리즘과 같은 다양한 프로그래밍 기법의 예시 문제로 자주 사용된다.

무차별 대입 검색 알고리즘보다 훨씬 효율적인 방식으로 사용될 수 있는 수학적 귀납법은 빈 체스판에 0개의 퀸을 배치하는 '문제'의 해를 가지고 마무리된다. 더 나은 무차별 대입 알고리즘은 각 행에 단일 퀸을 배치하여 88 = 224 = 16,777,216개의 무작위 배치를 생성한다.

한 알고리즘은 숫자 1부터 8까지의 순열(8! = 40,320개)을 생성하여 여덟 룩 문제를 해결하고, 각 순열의 요소를 인덱스로 사용하여 각 행에 퀸을 배치한다. 그런 다음 대각선 공격 위치가 있는 보드를 거부한다.

이 애니메이션은 문제 해결을 위한 백트래킹을 보여준다. 충돌을 일으키지 않는 것으로 알려진 열에 퀸이 배치된다. 열을 찾을 수 없으면 프로그램은 마지막으로 양호한 상태로 돌아간 다음 다른 열을 시도한다.


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

8 퀸에 대한 최소 충돌 해결책


전수 검색의 대안은, 전형적으로 모든 퀸을 보드에 놓고 시작하는 '반복적 수정' 알고리즘으로, 예를 들어 열당 퀸을 하나씩 배치한다.[21] 그런 다음 충돌(공격)의 수를 계산하고, 퀸의 배치를 개선하는 방법을 결정하기 위해 휴리스틱을 사용한다. '최소 충돌' 휴리스틱 – 가장 많은 수의 충돌을 가진 조각을, 충돌 수가 가장 적은 동일한 열의 칸으로 이동하는 것 – 은 특히 효과적이다: 1,000,000 퀸 문제조차 쉽게 해결할 수 있다.[22][23]

위에 설명된 백트래킹 검색과 달리, 반복적 수정은 해를 보장하지 않는다. 모든 탐욕 알고리즘 절차와 마찬가지로, 지역 최적값에 갇힐 수 있다. (이 경우, 알고리즘은 다른 초기 구성으로 다시 시작될 수 있다.) 반면에, 깊이 우선 탐색의 범위를 훨씬 뛰어넘는 문제 크기를 해결할 수 있다.

백트래킹의 대안으로, 유효한 부분 해를 한 번에 한 행씩 재귀적으로 열거하여 해를 계산할 수 있다. 전체 보드 위치를 구성하는 대신, 막힌 대각선과 열은 비트 단위 연산으로 추적된다. 이렇게 하면 개별 솔루션을 복구할 수 없다.[24][25]

아래는 재귀적으로 해를 구성하는 C++ 코드이다.



#include
#define MAX_SIZE 8

// 최대 MAX_SIZE queen 문제까지 해결할 수 있다.

using namespace std;

int board[MAX_SIZE];

// board[i]는 i번째 행에 퀸이 몇번째 열에 있는지 의미하는 변수이다. (행열은 서로 바뀌어도 된다.)

// 즉 board[0] = 3일때, (1,4) 혹은 (4,1) 위치에 퀸이 있다

int n;

int cnt;

void path(int y) {

// y는 현재 몇개의 퀸이 배치되었는지를 의미하는 변수다.

int ko;

if( y == n ) {

// n개의 퀸이 배치가 되었다면 이 경우는 답이다.

cnt++;

return;

}

for( int i=0; i
// ko는 퀸이 배치될 수 있는지를 저장하는 플래그다.

ko = 1;

for( int j=0; j
// 이미 배치가 끝난 퀸을 참고해서 i번째 칸에 퀸을 설치할 수 있는지를 확인한다.

if( board[j] == i || abs(y-j) == abs(i-board[j]) ) {

// j번째 줄에 있는 퀸과 같은 칸에 있거나, 대각선에 같은 곳에 있다면, i번째 칸에 대한 탐색을 중단한다.

ko = 0;

break;

}

}

if( ko ) {

// 여기까지 왔다면 y번째 줄에 i번째 칸에 퀸을 놔두는 것이 가능하다.

board[y] = i;

path(y+1);

}

}

}

int main() {

int k;

cin >> k;

while( k-- ) {

cin >> n;

cnt = 0;

path(0);

cout << cnt << '\n';

}

return 0;

}



다음은 니클라우스 비르트의 해법을 파이썬 프로그래밍 언어로 번역한 것이다. 제너레이터 함수 형태의 코루틴을 사용함으로써, 원본의 두 가지 버전 모두를 통합하여 해법을 하나 또는 모두 계산할 수 있다. 오직 15,720개의 가능한 퀸 배치만 검사한다.[26][27]



def queens(n: int, i: int, a: list, b: list, c: list):

if i < n:

for j in range(n):

if j not in a and i + j not in b and i - j not in c:

yield from queens(n, i + 1, a + [j], b + [i + j], c + [i - j])

else:

yield a

for solution in queens(8, 0, [], [], []):

print(solution)


6. 연관 문제


  • 다른 기물 사용

: 8 × 8 체스판에는 32개의 나이트, 14개의 비숍, 8개의 룩, 16개의 킹을 서로 공격하지 않도록 배치할 수 있다. 나이트는 반대 색상의 칸으로만 이동하므로, 한 색상의 칸에 모두 배치하면 간단하게 해결된다. 룩과 킹의 경우도 간단한 해법이 존재한다. 16개의 킹은 체스판을 2 × 2 정사각형으로 나누고 각 정사각형의 같은 위치에 배치하면 된다. ''n'' × ''n'' 체스판에 ''n''개의 룩을 배치하는 문제는 차수가 ''n''인 순열 행렬과 관련이 있다.

  • 다른 판 모양

: 토러스형이나 원통형 체스판과 같은 다른 모양의 판에서도 문제를 고려할 수 있다. 폴리아는 토러스에서 ''n''이 6과 서로소일 때 ''n'' × ''n'' 정사각형 판에 ''n''개의 퀸을 배치할 수 있음을 연구하였다.[13]

  • 고차원: 크기가 ''n''인 ''d''차원 체스 공간에서 서로 공격하지 않는 퀸의 수를 구하는 문제도 있다. 일부 고차원에서는 ''n''개 이상의 퀸을 배치할 수도 있다.[10][11]
  • 체스 변형: 쇼기와 같은 체스 변형에서도 유사한 문제를 생각해 볼 수 있다. 예를 들어, ''n''+''k'' 용왕 문제는 ''k''개의 쇼기 보병과 ''n'' × ''n'' 쇼기판에 서로 공격하지 않는 ''n''+''k''개의 용왕을 배치하는 것이다.[12]
  • 지배: ''n'' × ''n'' 체스판에서 모든 칸을 공격하거나 차지하는 데 필요한 최소한의 퀸 또는 다른 기물의 수를 지배 수라고 한다. ''n'' = 8일 때 퀸의 지배 수는 5이다.[14][15]
  • 퀸과 다른 기물: 퀸과 다른 기물을 함께 배치하는 변형 문제도 있다. 예를 들어, ''n'' × ''n'' 체스판에 서로 공격하지 않도록 ''m''개의 퀸과 ''m''개의 나이트를 배치하거나,[16] 퀸과 폰을 배치하는 문제가 있다.[17]
  • 마방진: 1992년 데미뢰르, 라프라프, 타니크는 일부 마방진을 ''n'' 퀸 문제의 해법으로 변환하는 방법을 발표했으며, 그 반대의 변환도 가능하다.[18]
  • 라틴 방진: ''n'' × ''n'' 행렬에서 같은 숫자가 같은 행이나 열에 나타나지 않도록 1부터 ''n''까지의 각 숫자를 ''n''개의 위치에 배치하는 문제이다.
  • 정확한 덮개: ''n'' 퀸 문제는 일반화된 정확한 덮개 문제의 한 예로, 스도쿠 역시 이 문제의 또 다른 예시이다.
  • ''n'' 퀸 완성: 이미 일부 퀸이 배치된 ''n'' × ''n'' 체스판에서 나머지 행에 서로 공격하지 않도록 퀸을 배치할 수 있는지 묻는 문제이다. 이 문제는 NP-완전 및 #P-완전이다.[19]

7. 대중문화


  • 7번째 손님 게임에서 스타우프 저택 게임 룸의 8번째 퍼즐인 "여왕의 딜레마"는 사실상 여덟 퀸 문제이다.[28]
  • 레이튼 교수와 이상한 마을 게임에서 130번째 퍼즐인 "너무 많은 여왕 5" (クイーンの問題5|퀸의 문제 5일본어)는 여덟 퀸 문제이다.[29]

참조

[1] 서적 The Eight Queens Problem Macmillan 1960
[2] 서적 Structured Programming Academic Press 1972
[3] 논문 Explicit Solutions to the N-Queens Problem for All N 1991
[4] 논문 Constructions for the Solution of the m Queens Problem http://www.jstor.org[...] 1969-03-01
[5] 웹사이트 The Q27 Project http://github.com/pr[...]
[6] 웹사이트 Mathematician Answers Chess Problem About Attacking Queens https://www.quantama[...] 2021-09-22
[7] arXiv The number of $n$-queens configurations 2021-07-28
[8] arXiv New bounds on the number of n-queens configurations 2017-05-15
[9] arXiv The $n$-queens problem 2021-09-16
[10] 논문 The n-Queens Problem in Higher Dimensions 2006
[11] 웹사이트 Queens On A Chessboard – Beyond The 2nd Dimension http://queens.lynden[...] 2020-01-27
[12] 논문 Reflections on the n +k dragon kings problem 2018-12-01
[13] 서적 Uber die "doppelt-periodischen" Losungen des n-Damen-Problems MIT Press 1984
[14] 논문 Domination and irredundance in the queens' graph 1997
[15] 서적 Graph Theory: Favorite Conjectures and Open Problems – 2 Springer 2018
[16] 웹사이트 Queens and knights problem http://www.vector.or[...] 2005-09-20
[17] 논문 A survey of known results and research areas for '''n'''-queens 2009
[18] 논문 Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions 1992
[19] 논문 Complexity of ''n''-Queens Completion https://jair.org/ind[...] 2017-09-07
[20] 논문 The ''n''-queens completion problem 2022-07-06
[21] 웹사이트 A Polynomial Time Algorithm for the N-Queen Problem http://citeseerx.ist[...] 1990
[22] 논문 Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems https://dx.doi.org/1[...] 1992-12-01
[23] 논문 Efficient local search with conflict minimization: a case study of the n-queens problem https://ieeexplore.i[...] 1994-10
[24] 논문 Bit-vector encoding of n-queen problem 2002-02
[25] 기술보고서 Backtracking Algorithms in MCPL using Bit Patterns and Recursion http://www.cl.cam.ac[...] 1997
[26] 서적 Algorithms + Data Structures = Programs Prentice-Hall 1976
[27] 서적 Algorithms and Data Structures https://informatika-[...] 2012
[28] 서적 The 7th Guest: The Official Strategy Guide http://www.thealmigh[...] Prima Games 2021-04-22
[29] 웹사이트 ナゾ130 クイーンの問題5 https://layton-fushi[...] 2021-09-17
[30] 웹사이트 QUEENS@TUD http://queens.inf.tu[...] 2016-09-07
[31] 웹사이트 Q27 Project: Facts https://github.com/p[...] 2018-02-10
[32] 웹사이트 QUEENS@TUD: Facts http://queens.inf.tu[...] 2016-09-07
[33] 서적 The 7th Guest: The Official Strategy Guide http://www.thealmigh[...] Prima Games 2021-04-22
[34] 웹사이트 ナゾ130　クイーンの問題5 https://layton-fushi[...] 2021-09-17


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com