2010년 8월 23일 (월) 16:18 판
N queen 문제는 NxN 정사각형에 체스의 기물인 퀸을 N개 배치하는 문제이다.
역사
1848년 막스 베첼이 제안하였다.
해법
구성적인 해법으로 N이 2,3인경우를 제외하고 해를 찾을 수 있다.
해의 수
8x8의 해를 나열하면 아래와 같다.
| 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 | |
해 1
|
| 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 | |
해 2
|
| 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 | |
해 3
|
| 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 | |
해 4
|
| 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 | |
해 5
|
| 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 | |
해 6
|
| 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 | |
해 7
|
| 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
|
| 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 | |
해 9
|
| 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 | |
해 10
|
| 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 | |
해 11
|
| 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 | |
해 12
|
아래에는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개의 퀸을 채울 수 있다.
최소한의 퀸을 써서 모든칸을 공격하는 것이다. 8x8에서는 5개가 필요하다.
소스
#include <iostream>
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;
}