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의 해를 나열하면 아래와 같다.

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

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; 
}

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

Eight-queens-animation.gif