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

위키백과, 우리 모두의 백과사전.
입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
Irafox (토론 | 기여)
9,341 편집
잔글편집 요약 없음
서울역 (토론 | 기여)
29 편집
8번째 줄: 8번째 줄:


== 해의 수 ==
== 해의 수 ==
8x8의 해를 나열하면 아래와 같다.
<table>
<tr>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|ql|__|__|__|__|=
7 |__|__|__|__|__|__|ql|__|=
6 |__|__|ql|__|__|__|__|__|=
5 |__|__|__|__|__|__|__|ql|=
4 |__|ql|__|__|__|__|__|__|=
3 |__|__|__|__|ql|__|__|__|=
2 |ql|__|__|__|__|__|__|__|=
1 |__|__|__|__|__|ql|__|__|=
|해 1
}}
</td>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|__|ql|__|__|__|=
7 |__|ql|__|__|__|__|__|__|=
6 |__|__|__|ql|__|__|__|__|=
5 |__|__|__|__|__|__|ql|__|=
4 |__|__|ql|__|__|__|__|__|=
3 |__|__|__|__|__|__|__|ql|=
2 |__|__|__|__|__|ql|__|__|=
1 |ql|__|__|__|__|__|__|__|=
|해 2
}}
</td>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|ql|__|__|__|__|=
7 |__|ql|__|__|__|__|__|__|=
6 |__|__|__|__|__|__|ql|__|=
5 |__|__|ql|__|__|__|__|__|=
4 |__|__|__|__|__|ql|__|__|=
3 |__|__|__|__|__|__|__|ql|=
2 |__|__|__|__|ql|__|__|__|=
1 |ql|__|__|__|__|__|__|__|=
|해 3
}}
</td>
</tr>
<tr>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|ql|__|__|__|__|=
7 |__|__|__|__|__|ql|__|__|=
6 |__|__|__|__|__|__|__|ql|=
5 |__|__|ql|__|__|__|__|__|=
4 |ql|__|__|__|__|__|__|__|=
3 |__|__|__|__|__|__|ql|__|=
2 |__|__|__|__|ql|__|__|__|=
1 |__|ql|__|__|__|__|__|__|=
|해 4
}}
</td>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|ql|__|__|__|__|__|=
7 |__|__|__|__|__|ql|__|__|=
6 |__|__|__|__|__|__|__|ql|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|__|ql|__|__|__|__|=
3 |__|__|__|__|__|__|ql|__|=
2 |__|__|__|__|ql|__|__|__|=
1 |__|ql|__|__|__|__|__|__|=
|해 5
}}
</td>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|__|ql|__|__|__|=
7 |__|__|ql|__|__|__|__|__|=
6 |__|__|__|__|__|__|__|ql|=
5 |__|__|__|ql|__|__|__|__|=
4 |__|__|__|__|__|__|ql|__|=
3 |ql|__|__|__|__|__|__|__|=
2 |__|__|__|__|__|ql|__|__|=
1 |__|ql|__|__|__|__|__|__|=
|해 6
}}
</td>
</tr>
<tr>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|__|ql|__|__|__|=
7 |__|__|__|__|__|__|ql|__|=
6 |__|__|__|ql|__|__|__|__|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|ql|__|__|__|__|__|=
3 |__|__|__|__|__|__|__|ql|=
2 |__|__|__|__|__|ql|__|__|=
1 |__|ql|__|__|__|__|__|__|=
|해 7
}}
</td>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|ql|__|__|__|__|=
7 |ql|__|__|__|__|__|__|__|=
6 |__|__|__|__|ql|__|__|__|=
5 |__|__|__|__|__|__|__|ql|=
4 |__|__|__|__|__|ql|__|__|=
3 |__|__|ql|__|__|__|__|__|=
2 |__|__|__|__|__|__|ql|__|=
1 |__|ql|__|__|__|__|__|__|=
|해 8
}}
</td>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|ql|__|__|__|__|__|=
7 |__|__|__|__|__|ql|__|__|=
6 |__|__|__|ql|__|__|__|__|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|__|__|__|__|__|ql|=
3 |__|__|__|__|ql|__|__|__|=
2 |__|__|__|__|__|__|ql|__|=
1 |__|ql|__|__|__|__|__|__|=
|해 9
}}
</td>
</tr>
<tr>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|__|__|ql|__|__|=
7 |__|ql|__|__|__|__|__|__|=
6 |__|__|__|__|__|__|ql|__|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|__|ql|__|__|__|__|=
3 |__|__|__|__|__|__|__|ql|=
2 |__|__|__|__|ql|__|__|__|=
1 |__|__|ql|__|__|__|__|__|=
|해 10
}}
</td>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|ql|__|__|__|__|=
7 |__|__|__|__|__|__|ql|__|=
6 |ql|__|__|__|__|__|__|__|=
5 |__|__|__|__|__|__|__|ql|=
4 |__|__|__|__|ql|__|__|__|=
3 |__|ql|__|__|__|__|__|__|=
2 |__|__|__|__|__|ql|__|__|=
1 |__|__|ql|__|__|__|__|__|=
|해 11
}}
</td>
<td>
{{체스판|=
| tright
|
|=

8 |__|__|__|__|__|ql|__|__|=
7 |__|__|__|ql|__|__|__|__|=
6 |__|__|__|__|__|__|ql|__|=
5 |ql|__|__|__|__|__|__|__|=
4 |__|__|__|__|__|__|__|ql|=
3 |__|ql|__|__|__|__|__|__|=
2 |__|__|__|__|ql|__|__|__|=
1 |__|__|ql|__|__|__|__|__|=
|해 12
}}
</td>
</tr>

</table>

아래에는''n''개의 퀸을 ''n'' × ''n'' 판에 나타내는 해의 수를 나타내었다. 고유한 해는{{OEIS|id=A002562}}에 일반적인 해(대칭이라도 따로 생 해는{{OEIS|id=A000170}}에 있다.
{| class="wikitable"
!style="padding: 0em .5em;"|''n'':
!style="padding: 0em .5em;"|1
!style="padding: 0em .5em;"|2
!style="padding: 0em .5em;"|3
!style="padding: 0em .5em;"|4
!style="padding: 0em .5em;"|5
!style="padding: 0em .5em;"|6
!style="padding: 0em .5em;"|7
!style="padding: 0em .5em;"|8
!style="padding: 0em .5em;"|9
!style="padding: 0em .5em;"|10
!style="padding: 0em .5em;"|11
!style="padding: 0em .5em;"|12
!style="padding: 0em .5em;"|13
!style="padding: 0em .5em;"|14
!style="padding: 0em .5em;"|..
!style="padding: 0em .5em;"|24
!style="padding: 0em .5em;"|25
!style="padding: 0em .5em;"|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
|}


== 연관 문제 ==
== 연관 문제 ==

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

N queen 문제는 NxN 정사각형에 체스의 기물인 퀸을 N개 배치하는 문제이다.

역사

1848년 막스 베첼이 제안하였다.

해법

구성적인 해법으로 N이 2,3인경우를 제외하고 해를 찾을 수 있다.

해의 수

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

abcdefgh
8
d8 white queen
g7 white queen
c6 white queen
h5 white queen
b4 white queen
e3 white queen
a2 white queen
f1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 1
abcdefgh
8
e8 white queen
b7 white queen
d6 white queen
g5 white queen
c4 white queen
h3 white queen
f2 white queen
a1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 2
abcdefgh
8
d8 white queen
b7 white queen
g6 white queen
c5 white queen
f4 white queen
h3 white queen
e2 white queen
a1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 3
abcdefgh
8
d8 white queen
f7 white queen
h6 white queen
c5 white queen
a4 white queen
g3 white queen
e2 white queen
b1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 4
abcdefgh
8
c8 white queen
f7 white queen
h6 white queen
a5 white queen
d4 white queen
g3 white queen
e2 white queen
b1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 5
abcdefgh
8
e8 white queen
c7 white queen
h6 white queen
d5 white queen
g4 white queen
a3 white queen
f2 white queen
b1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 6
abcdefgh
8
e8 white queen
g7 white queen
d6 white queen
a5 white queen
c4 white queen
h3 white queen
f2 white queen
b1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 7
abcdefgh
8
d8 white queen
a7 white queen
e6 white queen
h5 white queen
f4 white queen
c3 white queen
g2 white queen
b1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 8
abcdefgh
8
c8 white queen
f7 white queen
d6 white queen
a5 white queen
h4 white queen
e3 white queen
g2 white queen
b1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 9
abcdefgh
8
f8 white queen
b7 white queen
g6 white queen
a5 white queen
d4 white queen
h3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 10
abcdefgh
8
d8 white queen
g7 white queen
a6 white queen
h5 white queen
e4 white queen
b3 white queen
f2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 11
abcdefgh
8
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
해 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

연관 문제

나이트, 비숍등에 대해서도 해를 찾을 수 있다.

원본 주소 "https://ko.wikipedia.org/w/index.php?title=여덟_퀸_문제&oldid=5581972"