8 퀸 문제

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
Solid white.svg a b c d e f g h Solid white.svg
8 a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ 8
7 a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __ 7
6 a6 __ b6 __ c6 ql d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql 5
4 a4 __ b4 ql c4 __ d4 __ e4 __ f4 __ g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __ 3
2 a2 ql b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 __ 2
1 a1 __ b1 __ c1 __ d1 __ e1 __ f1 ql g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
해 중 하나.

8 퀸 문제는 8x8크기의 체스판에 을 8개 배치하는 문제이다. 1848년 막스 베첼이 처음 제안하였다. 이 문제를 일반화하면 NxN 크기의 체스판에 을 N개 배치하는 N 퀸 문제가 된다. 구성적인 해법으로 N이 2,3인경우를 제외하고 해를 찾을 수 있다.

[편집]

8x8의 해를 나열하면 아래와 같다.

Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ 8
7 a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 __ 7
6 a6 ql b6 __ c6 __ d6 __ e6 ql f6 __ g6 __ h6 __ 6
5 a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 ql c4 __ d4 ql e4 __ f4 __ g4 __ h4 __ 4
3 a3 __ b3 __ c3 ql d3 ql e3 ql f3 ql g3 ql h3 ql 3
2 a2 ql b2 ql c2 __ d2 __ e2 __ f2 __ g2 __ h2 __ 2
1 a1 __ b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 __ g8 ql h8 __ 8
7 a7 __ b7 __ c7 __ d7 ql e7 __ f7 __ g7 __ h7 __ 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 ql g6 __ h6 __ 6
5 a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 ql b4 __ c4 __ d4 __ e4 ql f4 __ g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __ 3
2 a2 __ b2 ql c2 __ d2 __ e2 __ f2 __ g2 __ h2 ql 2
1 a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ 8
7 a7 __ b7 __ c7 __ d7 ql e7 __ f7 __ g7 __ h7 __ 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 ql b5 __ c5 __ d5 __ e5 ql f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 ql 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __ 3
2 a2 __ b2 ql c2 __ d2 __ e2 __ f2 __ g2 ql h2 __ 2
1 a1 __ b1 __ c1 ql d1 __ e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ 8
7 a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 ql 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 __ b5 ql c5 __ d5 __ e5 ql f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 ql d4 __ e4 __ f4 __ g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __ 3
2 a2 ql b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __ 2
1 a1 __ b1 __ c1 __ d1 ql e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ 8
7 a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 ql 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 __ b5 ql c5 ql d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 __ f4 ql g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __ 3
2 a2 ql b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __ 2
1 a1 __ b1 __ c1 __ d1 ql e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 __ g8 ql h8 __ 8
7 a7 __ b7 __ c7 __ d7 __ e7 ql f7 __ g7 __ h7 __ 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 __ b5 ql c5 __ d5 __ e5 __ f5 ql g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 __ 4
3 a3 ql b3 __ c3 ql d3 __ e3 __ f3 __ g3 __ h3 __ 3
2 a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 ql 2
1 a1 __ b1 __ c1 __ d1 ql e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 __ g8 ql h8 __ 8
7 a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 __ 7
6 a6 ql b6 __ c6 __ d6 __ e6 __ f6 ql g6 __ h6 __ 6
5 a5 __ b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 ql f4 __ g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __ 3
2 a2 __ b2 ql c2 __ d2 __ e2 __ f2 __ g2 __ h2 ql 2
1 a1 __ b1 __ c1 __ d1 ql e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ 8
7 a7 __ b7 __ c7 ql d7 __ e7 __ f7 __ g7 __ h7 __ 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 ql h6 __ 6
5 a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 ql c4 __ d4 __ e4 __ f4 __ g4 __ h4 ql 4
3 a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __ 3
2 a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 __ 2
1 a1 ql b1 __ c1 __ d1 ql e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 ql f8 __ g8 __ h8 __ 8
7 a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 ql 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 ql g6 __ h6 __ 6
5 a5 __ b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 __ 4
3 a3 __ b3 ql c3 __ d3 __ e3 __ f3 __ g3 ql h3 __ 3
2 a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 __ 2
1 a1 ql b1 __ c1 __ d1 ql e1 __ f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 __ g8 __ h8 ql 8
7 a7 __ b7 __ c7 __ d7 ql e7 __ f7 __ g7 __ h7 __ 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 ql b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 __ f4 ql g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 __ g3 __ h3 __ 3
2 a2 __ b2 ql c2 __ d2 __ e2 __ f2 __ g2 ql h2 __ 2
1 a1 __ b1 __ c1 __ d1 __ e1 ql f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 ql g8 __ h8 __ 8
7 a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 __ h7 __ 7
6 a6 ql b6 __ c6 ql d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 ql c4 __ d4 __ e4 __ f4 __ g4 ql h4 __ 4
3 a3 __ b3 __ c3 __ d3 ql e3 __ f3 __ g3 __ h3 __ 3
2 a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 ql 2
1 a1 __ b1 __ c1 __ d1 __ e1 ql f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__
Solid white.svg a b c d e f g h Solid white.svg
8 a8 b8 c8 __ d8 __ e8 __ f8 __ g8 __ h8 ql 8
7 a7 __ b7 __ c7 __ d7 __ e7 __ f7 ql g7 __ h7 __ 7
6 a6 __ b6 __ c6 __ d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 ql b5 __ c5 ql d5 __ e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 __ f4 __ g4 __ h4 __ 4
3 a3 __ b3 ql c3 __ d3 ql e3 __ f3 __ g3 __ h3 __ 3
2 a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 ql h2 __ 2
1 a1 __ b1 __ c1 __ d1 __ e1 ql f1 __ g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg
__

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개의 퀸을 채울 수 있다.

  • 지배

최소한의 퀸을 써서 모든칸을 공격하는 것이다. 8x8에서는 5개가 필요하다.

풀이 프로그램[편집]

아래는 재귀적으로 해를 구성하는 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; 
}

아래 애니메이션을 보면 재귀적으로 해를 탐색하는 과정을 알 수 있다.

Eight-queens-animation.gif