［PDF］Nクイーン問題

Ｎクイー ン問題
Ｎクイーン問題
０．目次
１．Ｎクイーン問題
１．１
１．２
１．３
バックトラックに基づく解法
バックトラックに基づく解法の改良
順列生成に基づく解法
- 1 -
Ｎクイー ン問題
１．Ｎクイーン問題
Ｎ 個 の ク イ ー ン を Ｎ × Ｎ の チ ェ ス 盤 上 に 、 互 い に き き 筋 (縦 、 横 、 斜 め 方 向 )に
入らないように置く方法を考察する。
●クイーンのきき筋
Ｑ
● Nク イ ー ン 問 題 の 解 の 数 。
N
3
4
5
6
7
8
9
10
解の数
0
2
10
4
40
92
352
724
N
11
12
13
14
15
16
17
18
解の数
2680
14200
73712
365596
2279184
14772512
95815104
666090624
- 2 -
N
19
20
21
22
23
24
解の数
4968057848
39029188884
314666222712
2691008701644
24233937684440
227514171973736
Ｎクイー ン問題
１．１
バックトラックに基づく解法
チ ェ ス 盤 の マ ス 目 を 指 定 す る た め に 、 n× n の 行 列 と み な し 、 i行 目 、 j列 目 の
マ ス 目 を (i,j) で 指 定 す る 。
→
j列 目
↓
i行 目
●バックトラックの考え方
（１）左の列から右の列へ順にひとつずつクイーンを置いていく。
（２）これからクイーンを置こうとする列のすべてのマス目のうち、
・すでに置かれたクイーンのきき筋に入らないマス目があれば、
そのマス目にクイーンを置き、右隣の列にクイーンを置くことを
続ける。
・ そ の よ う な マ ス 目 が 複 数 個 あ る と き は そ の 中 で 一 番 下 (行 番 号 の
大 き い 方 を 下 と す る )の マ ス 目 を 選 ぶ 。
・すべてのマス目がすでに置かれたクイーンのきき筋に入っている
ときは、前の列に戻り、クイーンの置かれたマス目のひとつ上から
一番上のマス目までに対して（２）と同様のことを行う。
（３）こうして、最後の列にクイーンが置ければ解になる。
もし、前の列に戻れなくなったら終了となる。
- 3 -
Ｎクイー ン問題
1
2
3
4
状 態 (1)
1 2 3 4
□□□□
□□□□
□□□□
●□□□
1
2
3
4
状 態 (6)
1 2 3 4
□●□×
□□□×
□□●×
●□□×
1
2
3
4
状 態 (11)解
1 2 3 4
□●□□
□□□●
●□□×
□□●×
1
2
3
4
状 態 (16)
1 2 3 4
□□●□
●□×□
□□×□
□●×□
1
2
3
4
状 態 (21)
1 2 3 4
●□□□
□□□□
□□□□
□●□□
1
2
3
4
状 態 (26)
1 2 3 4
●□×□
□□×□
□●×□
□□×□
1
2
3
4
状 態 (2)
1 2 3 4
□□□□
□●□□
□×□□
●×□□
1
2
3
4
状 態 (7)
1 2 3 4
□●×□
□□×□
□□□□
●□□□
1
2
3
4
状 態 (12)
1 2 3 4
□●□×
□□□□
●□□□
□□●□
1
2
3
4
状 態 (17)解
1 2 3 4
□□●□
●□□□
□□□●
□●□×
1
2
3
4
状 態 (22)
1 2 3 4
●□□□
□□●□
□□×□
□●×□
1
2
3
4
状 態 (27)
1 2 3 4
●×□□
□×□□
□□□□
□□□□
1
2
3
4
状 態 (3)
1 2 3 4
□□×□
□●×□
□□×□
●□×□
1
2
3
4
状 態 (8)
1 2 3 4
□□□□
□□□□
●□□□
□□□□
1
2
3
4
状 態 (13)
1 2 3 4
□●×□
□□×□
●□×□
□□□□
1
2
3
4
状 態 (18)
1 2 3 4
□□●×
●□□×
□□□□
□●□□
1
2
3
4
状 態 (23)
1 2 3 4
●□□×
□□●×
□□□×
□●□×
1
2
3
4
状 態 (28)終 了
1 2 3 4
□□□□
□□□□
□□□□
□□□□
解 の 候 補 は 、 n**n個 に な る 。
- 4 -
1
2
3
4
状 態 (4)
1 2 3 4
□●□□
□□□□
□□□□
●□□□
1
2
3
4
状 態 (9)
1 2 3 4
□●□□
□×□□
●×□□
□×□□
1
2
3
4
状 態 (14)
1 2 3 4
□□□□
●□□□
□□□□
□□□□
1
2
3
4
状 態 (19)
1 2 3 4
□×□□
●×□□
□×□□
□□□□
1
2
3
4
状 態 (24)
1 2 3 4
●□×□
□□□□
□□□□
□●□□
1
2
3
4
状 態 (5)
1 2 3 4
□●□□
□□□□
□□●□
●□×□
1
2
3
4
状 態 (10)
1 2 3 4
□●□□
□□□□
●□□□
□□●□
1
2
3
4
状 態 (15)
1 2 3 4
□□□□
●□□□
□□□□
□●□□
1
2
3
4
状 態 (20)
1 2 3 4
●□□□
□□□□
□□□□
□□□□
1
2
3
4
状 態 (25)
1 2 3 4
●□□□
□□□□
□●□□
□□□□
Ｎクイー ン問題
●４×４のチェス盤における探索過程
(1,4)
(2,4)
(2,3)
(2,2)
(2,1)
(1,3)
(2,4)
(2,3)
(2,2)
(2,1)
(3,4)
(3,3)
(3,2)
(3,1)
(3,4)
(3,3)
(3,4)
(4,4)
(4,3)
(4,2)
(4,1)
(4,4)
(4,3)
(4,2)
(4,1)
解
(3,3)
(3,2)
(3,1)
(1,2)
(2,4)
(3,4)
(3,3)
(3,2)
(3,1)
(4,4)
(4,3)
(4,2)
(4,1)
(2,3)
(2,2)
(2,1)
(1,1)
(2,4)
(3,4)
(3,3)
(3,2)
(3,1)
(2,3)
(3,4)
(3,3)
(3,2)
(3,1)
(2,2)
(2,1)
- 5 -
(4,4)
(4,3)
(4,2)
(4,1)
解
Ｎクイー ン問題
●バックトラックに基づくＮクイーン問題プログラム
(i,j)に ク イ ー ン Qを 置 く 場 合 、 チ ェ ッ ク す る マ ス 目 を 青 で 示 す 。
→
j
↓
i
Q
● Ｎ ク イ ー ン 問 題 プ ロ グ ラ ム (nq111.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* << nq111.c >> */
/* Ｎ ク イ ー ン 問 題 */
#include <stdio.h>
#define N 30
/* チ ェ ス 盤 サ イ ズ の 最 大 値 。 */
int b[N+1][N+1], /* チ ェ ス 盤 を 表 す 配 列 。
b[i][j]=0： マ ス 目 (i,j)に ク イ ー ン が あ る 場 合 。
b[i][j]=1： マ ス 目 (i,j)に ク イ ー ン が な い 場 合 。 */
count,
/* 配 置 の 個 数 。 */
n;
/* チ ェ ス 盤 の サ イ ズ 。 */
void queen(int i, int j);
int main() {
int i,j;
while( 1 ) {
/* nの 読 み 込 み 。 */
scanf("%d",&n);
if( (n <= 0)||(n > N) ) { break; }
/* チ ェ ス 盤 等 の 初 期 設 定 。 */
for( i=1; i<=n; i++ ) {
for( j=1; j<=n; j++ ) { b[i][j] = 0; }
}
count = 0;
/* バ ッ ク ト ラ ッ ク 。 */
queen(n,0);
printf("%d× %dの チ ェ ス 盤
解 の 数 ： %d\n",n,n,count);
}
}
/* マ ス 目 (i,j)に ク イ ー ン を 置 く 操 作 。 */
void queen(int i, int j) {
int p,q;
- 6 -
Ｎクイー ン問題
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/* 横 方 向 の マ ス 目 を 調 べ る 。 */
for( q=j-1; q>=1; q-- ) {
/* す で に あ る 場 合 、 戻 る 。 */
if( b[i][q] == 1 ) { return; }
}
/* 斜 め 上 方 向 の マ ス 目 を 調 べ る 。 */
p = i-1; q = j-1;
while( (p >= 1)&&(q >= 1) ) {
/* す で に あ る 場 合 、 戻 る 。 */
if( b[p][q] == 1 ) { return; }
p--; q--;
}
/* 斜 め 下 方 向 の マ ス 目 を 調 べ る 。 */
p = i+1; q = j-1;
while( (p <= n)&&(q >= 1) ) {
/* す で に あ る 場 合 、 戻 る 。 */
if( b[p][q] == 1 ) { return; }
p++; q--;
}
/* き き 筋 に 他 の ク イ ー ン が な い の で 、 j列 目 の マ ス 目 (i,j)に ク イ ー ン を 置 く 。 */
b[i][j] = 1;
if( j == n ) {
/* 解 の 表 示 。 */
count++; printf("[%d] \n",count);
for( p=1; p<=n; p++ ) {
for( q=1; q<=n; q++ ) { printf("%3d",b[p][q]); }
printf("\n");
}
} else {
/* 右 隣 の 列 j+1の n個 の マ ス 目 を 調 べ る 。 */
for( p=n; p>=1; p-- ) {
queen(p,j+1);
}
}
/* j列 目 の マ ス 目 (i,j)か ら ク イ ー ン を 取 り 除 く 。 */
b[i][j] = 0;
}
- 7 -
Ｎクイー ン問題
実行結果
% cc nq111.c
% a.out
4
[1]
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
[2]
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
4× 4の チ ェ ス 盤 解 の 数 ： 2
8
＜＜途中省略＞＞
8× 8の チ ェ ス 盤 解 の 数 ： 92
0
実行時間
実行時間測定
% time ./a.out
13 0
13× 13の チ ェ ス 盤 解 の 数 ： 73712
2.579u 0.001s 0:04.73 54.3%
0+0k 0+8io 0pf+0w
% time ./a.out
14 0
14× 14の チ ェ ス 盤 解 の 数 ： 365596
16.881u 0.000s 0:18.67 90.4%
0+0k 0+8io 0pf+0w
% time ./a.out
15 0
15× 15の チ ェ ス 盤 解 の 数 ： 2279184
116.365u 0.000s 1:58.95 97.8%
0+0k 0+8io 0pf+0w
- 8 -
Ｎクイー ン問題
１．２
バックトラックに基づく解法の改良
横方向、斜め方向を配列で表現し、すでにクイーンが置かれているかいないか
の判断を早める。
横方向
左斜め上方向
(i-j+nが 一 定 )
→j
↓1
i 2
3
4
1
2
3
4
1
4
5
6
7
2
3
4
5
6
3
2
3
4
5
4
1
2
3
4
左斜め下方向
(i+jが 一 定 ）
1
2
3
4
1
2
3
4
5
2
3
4
5
6
3
4
5
6
7
4
5
6
7
8
●バックトラックに基づくＮクイーン問題プログラムの改良
(i,j)に ク イ ー ン を 置 く 場 合 、 チ ェ ッ ク す る マ ス 目 。
→
j列 目
↓
i行 目
Ｑ
青線
ue[i-j+n]
赤線
gyo[i]
緑線
sita[i+j]
● Ｎ ク イ ー ン 問 題 プ ロ グ ラ ム (nq121.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* << nq121.c >> */
/* Ｎ ク イ ー ン 問 題 */
#include <stdio.h>
#define N 30
/* チ ェ ス 盤 サ イ ズ の 最 大 値 。 */
int gyo[N+1],
/* gyo[i]=0： 行 iに ク イ ー ン が な い 。
gyo[i]=1： 行 iに ク イ ー ン が あ る 。 */
ue[2*N],
/* ue[i-j+n]=0:左 斜 め 上 方 向 i-j+nに ク イ ー ン が な い 。
ue[i-j+n]=1:左 斜 め 上 方 向 i-j+nに ク イ ー ン が あ る 。 */
sita[2*N+1], /* sita[i+j]=0： 左 斜 め 下 方 向 i+jに ク イ ー ン が な い 。
sita[i+j]=1： 左 斜 め 下 方 向 i+jに ク イ ー ン が あ る 。 */
kai[N+1],
/* 解 ： 列 jの 行 kai[j]に ク イ ー ン が あ る 。 */
count,
/* 得 ら れ た 配 置 の 個 数 。 */
n;
/* チ ェ ス 盤 の サ イ ズ 。 */
void queen(int i, int j);
int main() {
int k;
while( 1 ) {
/* nの 読 み 込 み 。 */
- 9 -
Ｎクイー ン問題
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
scanf("%d",&n);
if( (n <= 0)||(n > N) ) { break; }
/* チ ェ ス 盤 等 の 初 期 設 定 。 */
for( k=1; k<=n; k++ ) { gyo[k] = 0; }
for( k=1; k<=2*n-1; k++ ) { ue[k] = 0; }
for( k=2; k<=2*n; k++ ) { sita[k] = 0; }
count = 0;
/* バ ッ ク ト ラ ッ ク 。 */
for( k=n; k>=1; k-- ) { queen(k,1); }
printf("%d× %dの チ ェ ス 盤 解 の 数 ： %d\n",n,n,count);
}
}
/* マ ス 目 (i,j)に ク イ ー ン を 置 く 操 作 。 */
void queen(int i, int j) {
int k;
/* 横 方 向 の マ ス 目 を 調 べ 、 す で に あ る 場 合 、 戻 る 。 */
if( gyo[i] == 1 ) { return; }
/* 左 斜 め 上 方 向 の マ ス 目 を 調 べ 、 す で に あ る 場 合 、 戻 る 。 */
if( ue[i-j+n] == 1 ) { return; }
/* 左 斜 め 下 方 向 の マ ス 目 を 調 べ 、 す で に あ る 場 合 、 戻 る 。 */
if( sita[i+j] == 1 ) { return; }
/* き き 筋 に 他 の ク イ ー ン が な い の で 、 マ ス 目 (i,j)に ク イ ー ン を 置 く 。 */
kai[j] = i;
gyo[i] = 1;
ue[i-j+n] = 1;
sita[i+j] = 1;
if( j == n ) {
/* 解 の 表 示 。 */
count++; printf("[%d]:",count);
for( k=1; k<=n; k++ ) {
printf("%3d",kai[k]);
}
printf("\n");
} else {
/* 右 隣 の 列 j+1の n個 の マ ス 目 を 調 べ る 。 */
for( k=n; k>=1; k-- ) {
queen(k,j+1);
}
}
/* マ ス 目 (i,j)の ク イ ー ン を 取 り 除 く 。 */
kai[j] = 0;
- 10 -
Ｎクイー ン問題
71
72
73
74
gyo[i] = 0;
ue[i-j+n] = 0;
sita[i+j] = 0;
}
実行結果
% cc nq121.c
% ./a.out
5
[1]: 5 3 1 4 2
[2]: 5 2 4 1 3
＜＜途中省略＞＞
[10]: 1 3 5 2 4
5× 5の チ ェ ス 盤 解 の 数 ： 10
11
＜＜途中省略＞＞
11× 11の チ ェ ス 盤 解 の 数 ： 2680
0
実行時間
実行時間測定
% time ./a.out
14 0
14× 14の チ ェ ス 盤 解 の 数 ： 365596
4.077u 0.000s 0:06.58 61.8%
0+0k 0+0io 0pf+0w
% time ./a.out
15 0
15× 15の チ ェ ス 盤 解 の 数 ： 2279184
26.523u 0.000s 0:28.89 91.7%
0+0k 0+8io 0pf+0w
% time ./a.out
16 0
16× 16の チ ェ ス 盤 解 の 数 ： 14772512
183.400u 0.000s 3:08.56 97.2%
0+0k 0+8io 0pf+0w
- 11 -
Ｎクイー ン問題
１．３
部分順列生成に基づく解法
解 の 候 補 を n**nか ら n!に 縮 小 す る 。
斜め方向を配列で表現し、効率をあげる。
●考え方：部分順列の生成
集 合 {x(1),...,x(k)}上 の す べ て の 順 列 を [x(1),...,x(k)]で 表 す 。
k個 の 要 素 か ら 1個 ず つ 抽 出 し て い く 。
[x(1),x(2),...,x(k)] = x(1)[x(2),x(3),...,x(k)]
∪ x(2)[x(1),x(3),...,x(k)]
∪ x(3)[x(2),x(1),...,x(k)]
・・・・・・・・・・・・・
∪ x(k-1)[x(2),x(3),...,x(1),x(k)]
∪ x(k)[x(2),x(3),...,x(k-1),x(1)]
抽出する順序に任意性があるので種々の生成法が考えられる。
- 12 -
Ｎクイー ン問題
●考え方１
抽出を繰り返し行う。未決定の先頭要素を残りの要素の先頭から
順に交換していく。
・樹形図１
[1234]
1[234]
2[134]
3[214]
4[231]
12[34]
123[4]
124[3]
13[24]
132[4]
134[2]
14[32]
143[2]
142[3]
21[34]
213[4]
214[3]
23[14]
231[4]
234[1]
24[31]
243[1]
241[3]
32[14]
321[4]
324[1]
31[24]
312[4]
314[2]
34[12]
341[2]
342[1]
42[31]
423[1]
421[3]
43[21]
432[1]
431[2]
41[32]
413[2]
412[3]
- 13 -
Ｎクイー ン問題
・樹形図２：要素の交換・移動状況
要素を交換した後、すぐ元に戻すことを繰り返す。
こ の よ う に す る と 、順 列 に 関 す る プ ロ グ ラ ム を 記 述 し や す く な る 。
赤い×は要素の交換、青い×は元に戻すことを意味する。
[1234]
1[234]
12[34]
123[4]
1234
124[3]
1243
123[4]
13[24]
132[4]
1324
134[2]
143[2]
1342
1432
142[3]
1423
21[34]
213[4]
2134
23[14]
214[3]
231[4]
234[1]
2143
2314
2341
243[1]
241[3]
2431
2413
321[4]
3214
324[1]
312[4]
314[2]
341[2]
342[1]
3241
3124
3142
3412
3421
423[1]
4231
421[3]
432[1]
431[2]
413[2]
412[3]
4213
4321
4312
4132
4123
12[34]
14[32]
12[34]
2[134]
1[234]
21[34]
24[31]
21[34]
3[214]
32[14]
1[234]
31[24]
34[12]
4[231]
42[31]
1[234]
43[21]
41[32]
- 14 -
Ｎクイー ン問題
● 部 分 順 列 生 成 プ ロ グ ラ ム (nq131.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/* << nq131.c >> */
/* 集 合 {1,2,… ,n}か ら r個 取 り 出 し ,１ 列 に 並 べ る 部 分 順 列 を 生 成 す る 。 */
#include <stdio.h>
#define N 30 /* 集 合 の 最 大 要 素 数 。 */
int p[N+1], /* 部 分 順 列 を 保 存 す る 配 列 。 */
n,
/* 集 合 の 要 素 数 。 */
r;
/* 取 り 出 す 個 数 。 */
double count; /* 部 分 順 列 の 個 数 。 */
void perm(int k);
int main() {
int i;
while( 1 ) {
/* n,rの 読 み 込 み 。 */
scanf("%d%d",&n,&r);
if( (n <= 0)||(n > N)||(r > n) ) { break; }
/* 初 期 設 定 。 */
for( i=1; i<=n; i++ ) { p[i] = i; }
count = 0;
/* 部 分 順 列 の 生 成 。 */
perm(1);
printf("n=%d r=%d count=%16.0f\n",n,r,count);
}
}
/* 部 分 順 列 の 生 成 。 */
void perm(int k) {
int i,w;
if( k > r ) {
/* 部 分 順 列 の 表 示 。 */
count++; printf("%6.0f: ",count);
for( i=1; i<=r; i++ ) { printf("%2d ",p[i]); }
printf("\n");
return;
}
for( i=k; i<=n; i++ ) {
/* 交 換 。 */
w = p[k]; p[k] = p[i]; p[i] = w;
perm(k+1);
/* 交 換 を 一 度 戻 す 。 */
w = p[k]; p[k] = p[i]; p[i] = w;
}
}
- 15 -
Ｎクイー ン問題
実行結果
% cc nq131.c
% ./a.out
3 1
1: 1
2: 2
3: 3
n=3 r=1 count=
3 2
1: 1 2
2: 1 3
3: 2 1
4: 2 3
5: 3 2
6: 3 1
n=3 r=2 count=
3 3
1: 1 2
2: 1 3
3: 2 1
4: 2 3
5: 3 2
6: 3 1
n=3 r=3 count=
0 0
3
6
3
2
3
1
1
2
6
実行時間
実行時間測定
% time ./a.out
11 11 0 0
n=11 r=11 count=
39916800
1.202u 0.001s 0:05.08 23.6%
0+0k 0+8io 0pf+0w
% time ./a.out
12 12 0 0
n=12 r=12 count=
479001600
14.415u 0.000s 0:17.93 80.3%
0+0k 0+8io 0pf+0w
% time ./a.out
13 13 0 0
n=13 r=13 count=
6227020800
187.563u 0.011s 3:10.93 98.2%
0+0k 0+8io 0pf+0w
- 16 -
Ｎクイー ン問題
データの移動に着目すると、効率のよいプログラムが得られる。
・樹形図３
[1234]
1[234]
12[34]
123[4]
124[3]
13[24]
132[4]
134[2]
14[32]
143[2]
142[3]
2[134]
3[214]
4[231]
21[34]
213[4]
214[3]
23[14]
231[4]
234[1]
24[31]
243[1]
241[3]
32[14]
321[4]
324[1]
31[24]
312[4]
314[2]
34[12]
341[2]
342[1]
42[31]
423[1]
421[3]
43[21]
432[1]
431[2]
41[32]
413[2]
412[3]
- 17 -
Ｎクイー ン問題
● 部 分 順 列 生 成 プ ロ グ ラ ム (nq132.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/* << nq132.c >> */
/* 集 合 {1,2,… ,n}か ら r個 取 り 出 し ,１ 列 に 並 べ る 部 分 順 列 を 生 成 す る 。 */
#include <stdio.h>
#define N 30 /* 集 合 の 最 大 要 素 数 。 */
int p[N+1], /* 部 分 順 列 を 保 存 す る 配 列 。 */
n,
/* 集 合 の 要 素 数 。 */
r;
/* 取 り 出 す 個 数 。 */
double count; /* 部 分 順 列 の 個 数 。 */
void perm(int k);
int main() {
int i;
while( 1 ) {
/* n,rの 読 み 込 み 。 */
scanf("%d%d",&n,&r);
if( (n <= 0)||(n > N)||(r > n) ) { break; }
/* 初 期 設 定 。 */
for( i=1; i<=n; i++ ) { p[i] = i; }
count = 0;
/* 部 分 順 列 の 生 成 。 */
perm(1);
printf("n=%d r=%d count=%16.0f\n",n,r,count);
}
}
/* 部 分 順 列 の 生 成 。 */
void perm(int k) {
int i,w;
if( k > r ) {
/* 部 分 順 列 の 表 示 。 */
count++; printf("%6.0f: ",count);
for( i=1; i<=r; i++ ) { printf("%2d ",p[i]); }
printf("\n");
return;
}
w = p[k];
for( i=k; i<=n; i++ ) {
p[k] = p[i]; p[i] = w;
perm(k+1);
p[i] = p[k];
}
p[k] = w;
}
- 18 -
Ｎクイー ン問題
実行結果
% cc nq132.c
% ./a.out
3 1
1: 1
2: 2
3: 3
n=3 r=1 count=
3 2
1: 1 2
2: 1 3
3: 2 1
4: 2 3
5: 3 2
6: 3 1
n=3 r=2 count=
3 3
1: 1 2
2: 1 3
3: 2 1
4: 2 3
5: 3 2
6: 3 1
n=3 r=3 count=
0 0
3
6
3
2
3
1
1
2
6
実行時間
実行時間測定
% time ./a.out
11 11 0 0
n=11 r=11 count=
39916800
1.018u 0.000s 0:04.65 21.7%
0+0k 0+8io 0pf+0w
% time ./a.out
12 12 0 0
n=12 r=12 count=
479001600
12.219u 0.000s 0:15.54 78.5%
0+0k 0+8io 0pf+0w
% time ./a.out
13 13 0 0
n=13 r=13 count=
6227020800
158.758u 0.000s 2:42.25 97.8%
0+0k 0+8io 0pf+0w
- 19 -
Ｎクイー ン問題
● Ｎ ク イ ー ン 問 題 プ ロ グ ラ ム (nq133.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/* << nq133.c >> */
/* Ｎ ク イ ー ン 問 題 */
#include <stdio.h>
#define N 30
/* チ ェ ス 盤 サ イ ズ の 最 大 値 。 */
int p[N+1],
/* 部 分 順 列 を 保 存 す る 配 列 。 */
count,
/* 生 成 さ れ る 解 の 個 数 。 */
n,
/* 要 素 数 。 */
ue[2*N],
/* ue[i-j+n]=0:左 斜 め 上 方 向 i-j+nに ク イ ー ン が な い 。
ue[i-j+n]=1:左 斜 め 上 方 向 i-j+nに ク イ ー ン が あ る 。 */
sita[2*N+1]; /* sita[i+j]=0:左 斜 め 下 方 向 i+jに ク イ ー ン が な い 。
sita[i+j]=1:左 斜 め 下 方 向 i+jに ク イ ー ン が あ る 。 */
void perm(int k);
int main() {
int i;
while( 1 ) {
/* nの 読 み 込 み 。 */
scanf("%d",&n);
if( (n <= 0)||(n > N) ) { break; }
/* 部 分 順 列 生 成 の 初 期 設 定 。 */
for( i=1; i<=n; i++ ) { p[i] = i; }
/* チ ェ ス 盤 等 の 初 期 設 定 。 */
for( i=1; i<=2*n-1; i++ ) { ue[i] = 0; }
for( i=2; i<=2*n; i++ ) { sita[i] = 0; }
count = 0;
/* バ ッ ク ト ラ ッ ク 。 */
perm(1);
printf("チ ェ ス 盤 %d× %dの 解 の 数 ： %d \n",n,n,count);
}
}
/* 配 置 の 生 成 。 */
void perm(int k) {
int i,w;
if( k > n ) {
/* 解 の 表 示 。 */
count++; printf("[%d]:",count);
for( i=1; i<=n; i++ ) {
printf("%3d",p[i]);
}
printf("\n");
return;
}
- 20 -
Ｎクイー ン問題
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
w = p[k];
for( i=k; i<=n; i++ ) {
p[k] = p[i]; p[i] = w;
/* マ ス 目 (p[k],k)に ク イ ー ン が 置 け る こ と が わ か っ た の で 置 く 。 */
if( (ue[p[k]-k+n] == ①
ue[p[k]-k+n] = ③
;
sita[p[k]+k] = ④
;
)&&(sita[p[k]+k] == ②
perm(k+1);
/* マ ス 目 (p[k],k)か ら ク イ ー ン を 取 り 除 く 。 */
ue[p[k]-k+n] = ⑤
;
sita[p[k]+k] = ⑥
;
}
p[i] = p[k];
}
p[k] = w;
}
実行結果
% cc nq133.c
% ./a.out
5
[1]: 1 3 5 2 4
[2]: 1 4 2 5 3
[3]: 2 4 1 3 5
[4]: 2 5 3 1 4
[5]: 3 1 4 2 5
[6]: 3 5 2 4 1
[7]: 4 2 5 3 1
[8]: 4 1 3 5 2
[9]: 5 2 4 1 3
[10]: 5 3 1 4 2
チ ェ ス 盤 5× 5の 解 の 数 ： 10
6
[1]: 2 4 6 1 3 5
[2]: 3 6 2 5 1 4
[3]: 4 1 5 2 6 3
[4]: 5 3 1 6 4 2
チ ェ ス 盤 6× 6の 解 の 数 ： 4
0
- 21 -
) ) {
Ｎクイー ン問題
実行時間
実行時間測定
% time ./a.out
14 0
チ ェ ス 盤 14× 14の 解 の 数 ： 365596
1.874u 0.000s 0:03.50 53.4%
0+0k 0+8io 0pf+0w
% time ./a.out
15 0
チ ェ ス 盤 15× 15の 解 の 数 ： 2279184
11.896u 0.000s 0:14.08 84.4%
0+0k 0+8io 0pf+0w
% time ./a.out
16 0
チ ェ ス 盤 16× 16の 解 の 数 ： 14772512
80.297u 0.000s 1:21.92 98.0%
0+0k 0+8io 0pf+0w
- 22 -