여덟 퀸 문제: 두 판 사이의 차이

입체적으로 역사 찾아보기

← 이전 편집 다음 편집 →

내용 삭제됨 내용 추가됨

시각위키텍스트

인라인

2010년 8월 23일 (월) 14:53 판

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