여덟 퀸 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
해 복구. 119.214.92.193(토론)의 13077736판 편집을 되돌림 |
체스판 문법을 수정. |
||
1번째 줄: | 1번째 줄: | ||
{{Chess diagram|= |
{{Chess diagram|= |
||
| tright |
| tright |
||
| 해 중 하나. |
|||
|= |
|||
| | | |ql| | | | |= |
|||
| | | | | | |ql| |= |
|||
| | |ql| | | | | |= |
|||
| | | | | | | |ql|= |
|||
| |ql| | | | | | |= |
|||
| | | | |ql| | | |= |
|||
|ql| | | | | | | |= |
|||
| | | | | |ql| | |= |
|||
| |
| |
||
|= |
|||
8 |__|__|__|ql|__|__|__|__|= |
|||
7 |__|__|__|__|__|__|ql|__|= |
|||
6 |__|__|ql|__|__|__|__|__|= |
|||
5 |__|__|__|__|__|__|__|ql|= |
|||
4 |__|ql|__|__|__|__|__|__|= |
|||
3 |__|__|__|__|ql|__|__|__|= |
|||
2 |ql|__|__|__|__|__|__|__|= |
|||
1 |__|__|__|__|__|ql|__|__|= |
|||
|해 중 하나. |
|||
}} |
}} |
||
'''8 퀸 문제'''는 8x8크기의 체스판에 [[퀸 (체스)|퀸]]을 8개 배치하는 문제이다. 1848년 [[막스 베첼]]이 처음 제안하였다. 이 문제를 일반화하면 NxN 크기의 체스판에 [[퀸 (체스)|퀸]]을 N개 배치하는 N 퀸 문제가 된다. 구성적인 해법으로 N이 2,3인경우를 제외하고 해를 찾을 수 있다. |
'''8 퀸 문제'''는 8x8크기의 체스판에 [[퀸 (체스)|퀸]]을 8개 배치하는 문제이다. 1848년 [[막스 베첼]]이 처음 제안하였다. 이 문제를 일반화하면 NxN 크기의 체스판에 [[퀸 (체스)|퀸]]을 N개 배치하는 N 퀸 문제가 된다. 구성적인 해법으로 N이 2,3인경우를 제외하고 해를 찾을 수 있다. |
||
23번째 줄: | 22번째 줄: | ||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 1 |
|||
8 |__|__|__|ql|__|__|__|__|= |
|||
|= |
|||
7 |__|__|__|__|__|__|ql|__|= |
|||
| | | |ql| | | | |= |
|||
| | | | | | |ql| |= |
|||
| | |ql| | | | | |= |
|||
| | | | | | | |ql|= |
|||
| |ql| | | | | | |= |
|||
| | | | |ql| | | |= |
|||
|ql| | | | | | | |= |
|||
|해 1 |
|||
| | | | | |ql| | |= |
|||
| |
|||
}} |
}} |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 2 |
|||
8 |__|__|__|__|ql|__|__|__|= |
|||
|= |
|||
7 |__|ql|__|__|__|__|__|__|= |
|||
| | | | |ql| | | |= |
|||
| |ql| | | | | | |= |
|||
| | | |ql| | | | |= |
|||
| | | | | | |ql| |= |
|||
| | |ql| | | | | |= |
|||
| | | | | | | |ql|= |
|||
| | | | | |ql| | |= |
|||
|해 2 |
|||
|ql| | | | | | | |= |
|||
| |
|||
}} |
}} |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 3 |
|||
8 |__|__|__|ql|__|__|__|__|= |
|||
|= |
|||
7 |__|ql|__|__|__|__|__|__|= |
|||
| | | |ql| | | | |= |
|||
| |ql| | | | | | |= |
|||
| | | | | | |ql| |= |
|||
| | |ql| | | | | |= |
|||
| | | | | |ql| | |= |
|||
| | | | | | | |ql|= |
|||
| | | | |ql| | | |= |
|||
|해 3 |
|||
|ql| | | | | | | |= |
|||
| |
|||
}} |
}} |
||
|- |
|- |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 4 |
|||
8 |__|__|__|ql|__|__|__|__|= |
|||
|= |
|||
7 |__|__|__|__|__|ql|__|__|= |
|||
| | | |ql| | | | |= |
|||
| | | | | |ql| | |= |
|||
| | | | | | | |ql|= |
|||
| | |ql| | | | | |= |
|||
|ql| | | | | | | |= |
|||
| | | | | | |ql| |= |
|||
| | | | |ql| | | |= |
|||
|해 4 |
|||
| |ql| | | | | | |= |
|||
| |
|||
}} |
}} |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 5 |
|||
8 |__|__|ql|__|__|__|__|__|= |
|||
|= |
|||
7 |__|__|__|__|__|ql|__|__|= |
|||
| | |ql| | | | | |= |
|||
| | | | | |ql| | |= |
|||
| | | | | | | |ql|= |
|||
|ql| | | | | | | |= |
|||
| | | |ql| | | | |= |
|||
| | | | | | |ql| |= |
|||
| | | | |ql| | | |= |
|||
|해 5 |
|||
| |ql| | | | | | |= |
|||
| |
|||
}} |
}} |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 6 |
|||
8 |__|__|__|__|ql|__|__|__|= |
|||
|= |
|||
7 |__|__|ql|__|__|__|__|__|= |
|||
| | | | |ql| | | |= |
|||
| | |ql| | | | | |= |
|||
| | | | | | | |ql|= |
|||
| | | |ql| | | | |= |
|||
| | | | | | |ql| |= |
|||
|ql| | | | | | | |= |
|||
| | | | | |ql| | |= |
|||
|해 6 |
|||
| |ql| | | | | | |= |
|||
| |
|||
}} |
}} |
||
|- |
|- |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 7 |
|||
8 |__|__|__|__|ql|__|__|__|= |
|||
|= |
|||
7 |__|__|__|__|__|__|ql|__|= |
|||
| | | | |ql| | | |= |
|||
| | | | | | |ql| |= |
|||
| | | |ql| | | | |= |
|||
|ql| | | | | | | |= |
|||
| | |ql| | | | | |= |
|||
| | | | | | | |ql|= |
|||
| | | | | |ql| | |= |
|||
|해 7 |
|||
| |ql| | | | | | |= |
|||
| |
|||
}} |
}} |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 8 |
|||
8 |__|__|__|ql|__|__|__|__|= |
|||
|= |
|||
7 |ql|__|__|__|__|__|__|__|= |
|||
| | | |ql| | | | |= |
|||
|ql| | | | | | | |= |
|||
| | | | |ql| | | |= |
|||
| | | | | | | |ql|= |
|||
| | | | | |ql| | |= |
|||
| | |ql| | | | | |= |
|||
| | | | | | |ql| |= |
|||
|해 8 |
|||
| |ql| | | | | | |= |
|||
| |
|||
}} |
}} |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 9 |
|||
8 |__|__|ql|__|__|__|__|__|= |
|||
|= |
|||
7 |__|__|__|__|__|ql|__|__|= |
|||
| | |ql| | | | | |= |
|||
| | | | | |ql| | |= |
|||
| | | |ql| | | | |= |
|||
|ql| | | | | | | |= |
|||
| | | | | | | |ql|= |
|||
| | | | |ql| | | |= |
|||
| | | | | | |ql| |= |
|||
| |ql| | | | | | |= |
|||
|해 9 |
|해 9 |
||
}} |
}} |
||
143번째 줄: | 160번째 줄: | ||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 10 |
|||
8 |__|__|__|__|__|ql|__|__|= |
|||
|= |
|||
7 |__|ql|__|__|__|__|__|__|= |
|||
| | | | | |ql| | |= |
|||
| |ql| | | | | | |= |
|||
| | | | | | |ql| |= |
|||
|ql| | | | | | | |= |
|||
| | | |ql| | | | |= |
|||
| | | | | | | |ql|= |
|||
| | | | |ql| | | |= |
|||
|해 10 |
|||
| | |ql| | | | | |= |
|||
| |
|||
}} |
}} |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 11 |
|||
8 |__|__|__|ql|__|__|__|__|= |
|||
|= |
|||
7 |__|__|__|__|__|__|ql|__|= |
|||
| | | |ql| | | | |= |
|||
| | | | | | |ql| |= |
|||
|ql| | | | | | | |= |
|||
| | | | | | | |ql|= |
|||
| | | | |ql| | | |= |
|||
| |ql| | | | | | |= |
|||
| | | | | |ql| | |= |
|||
|해 11 |
|||
| | |ql| | | | | |= |
|||
| |
|||
}} |
}} |
||
| |
| |
||
{{체스판|= |
{{체스판|= |
||
| tright |
| tright |
||
| 해 12 |
|||
8 |__|__|__|__|__|ql|__|__|= |
|||
|= |
|||
7 |__|__|__|ql|__|__|__|__|= |
|||
| | | | | |ql| | |= |
|||
| | | |ql| | | | |= |
|||
| | | | | | |ql| |= |
|||
|ql| | | | | | | |= |
|||
| | | | | | | |ql|= |
|||
| |ql| | | | | | |= |
|||
| | | | |ql| | | |= |
|||
|해 12 |
|||
| | |ql| | | | | |= |
|||
| |
|||
}} |
}} |
||
|} |
|} |
2016년 6월 2일 (목) 00:40 판
해 중 하나.
a | b | c | d | e | f | g | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | b | c | d | e | f | g | h |
8 퀸 문제는 8x8크기의 체스판에 퀸을 8개 배치하는 문제이다. 1848년 막스 베첼이 처음 제안하였다. 이 문제를 일반화하면 NxN 크기의 체스판에 퀸을 N개 배치하는 N 퀸 문제가 된다. 구성적인 해법으로 N이 2,3인경우를 제외하고 해를 찾을 수 있다.
해
8x8의 해를 나열하면 아래와 같다.
해 1
|
해 2
|
해 3
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
해 4
|
해 5
|
해 6
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
해 7
|
해 8
|
해 9
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
해 10
|
해 11
|
해 12
|
N 퀸 문제
아래에는n개의 퀸을 n × n 판에 나타내는 해의 수를 나타내었다. 고유한 해(선대칭이나 점대칭으로 대칭인 해)는 온라인 정수열 사전에서(OEIS의 수열 A002562)에 일반적인 해(대칭을 구별한 해)는(OEIS의 수열 A000170)에 등재되어 있다.
n: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | .. | 24 | 25 | 26 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
unique: | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | 341 | 1,787 | 9,233 | 45,752 | .. | 28,439,272,956,934 | 275,986,683,743,434 | 2,789,712,466,510,289 |
distinct: | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2,680 | 14,200 | 73,712 | 365,596 | .. | 227,514,171,973,736 | 2,207,893,435,808,352 | 22,317,699,616,364,044 |
연관 문제
- 다른 기물 사용
32개의 나이트, 14개의 비숍, 8개의 룩, 16개의 킹이 필요하다.
- 다른 판 모양
토러스형이나 원통형 조건에 대해 생각할 수 있다. 토러스에서는 폴리아의 연구에 의해 n이 6과 서로소일때 nxn정사각형판에 n개의 퀸을 채울 수 있다.
풀이 프로그램
아래는 재귀적으로 해를 구성하는 C++ 코드이다.
#include <iostream>
#include <cmath>
using namespace std;
int board[12];
int n;
int cnt;
void path(int y) {
int ko = 1;
if( y == n ) {
cnt++;
return;
}
for( int i=0; i<n; i++ ) {
ko = 1;
for( int j=0; j<y; j++ ) {
if( board[j] == i || abs(y-j) == abs(i-board[j]) ) {
ko = 0;
break;
}
}
if( ko ) {
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;
}
아래 애니메이션을 보면 재귀적으로 해를 탐색하는 과정을 알 수 있다.