여덟 퀸 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 로봇이 더함: ca, cs, da, de, es, fa, fr, he, hu, it, ja, ka, pl, pt, ru, sl, sr, th, tr, vi, zh |
|||
289번째 줄: | 289번째 줄: | ||
== 연관 문제 == |
== 연관 문제 == |
||
*''' 다른 기물 사용 ''' |
|||
나이트, 비숍등에 대해서도 해를 찾을 수 있다. |
|||
32개의 나이트, 14개의 비숍, 8개의 룩, 16개의 킹이 필요하다. |
|||
*''' 다른 판 모양 ''' |
|||
토러스형이나 원통형 조건에 대해 생각할 수 있다. 토러스에서는 폴리아의 연구에 의해 n이 6과 서로소일때 nxn정사각형판에 n개의 퀸을 채울 수 있다. |
|||
*'''지배''' |
|||
최소한의 퀸을 써서 모든칸을 공격하는 것이다. 8x8에서는 5개가 필요하다. |
|||
== 소스 == |
|||
<source lang="c"> |
|||
#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; |
|||
} |
|||
</source> |
|||
[[분류:퍼즐]] |
[[분류:퍼즐]] |
2010년 8월 23일 (월) 14:53 판
이 문서는 위키백과의 편집 지침에 맞춰 다듬어야 합니다. |
N queen 문제는 NxN 정사각형에 체스의 기물인 퀸을 N개 배치하는 문제이다.
역사
1848년 막스 베첼이 제안하였다.
해법
구성적인 해법으로 N이 2,3인경우를 제외하고 해를 찾을 수 있다.
해의 수
8x8의 해를 나열하면 아래와 같다.
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
아래에는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;
}