n女王問題の解法とその比較
- 発表者 26期 澤田
- 2010年度前期プロ発
- 使用言語 C言語 (Linux gcc, Windows bcc32, MS-DOS5.0 Turbo C LSI-C86試食版にて動作確認)
- 対象OS Linux/UNIX系OS および MS-DOS/Windows系OS
- ライブラリ等 特になし
- 添付資料 2010前期プロ発_n女王問題とその解法.odp
- 添付ソースコード Windows用 Linux用 ※違いは文字コード・改行コードのみ
plugin_slideshare: エラー ( 正しいHTMLタグを入力してください. )
概要
n×n目のチェス盤にn個のクイーンをお互いに取られ合わない用よう配置するという数学パズルを解く。
チェスのクイーンは将棋の飛車と角を合わせた動きを取る。
図1 クイーンの効き筋
図2 8女王問題の解の一つ
この問題を解くにはすべての盤の状態をしらみつぶしに調べ尽くせばよい。
コンピュータの得意とする処理である。
しかし、盤の目の総数は
あり、n=8の時は4,426,165,368 通りにもなる。
あきらかに解ではない状態をカットすることで計算量を減らす工夫が必要になる。
今回は生成後検査法とバックトラック法という技法をn女王問題の解法とその比較
発表者 26期 澤田使い計算量を比較する。
また、しらみつぶしを行うためには再帰というプログラミング技法が有効である。
生成後検査法
クイーンがn個配置された盤を生成後、解であるかどうかを検査する方法。
今回はすべての組み合わせを生成せず、生成される組み合わせをあらかじめ減らしてから検査を行う。
以下に組み合わせの減らし方を説明する。
列に対して
同じ列に2個以上クイーンを配置すると解にならない。
各列に1個ずつクイーンを配置する組み合わせをしらみつぶしに調べる。
置き方の総数が
まで減る。
n=8の場合は16,777,216通り
行に対して
行についても同様な制限を課す。
各行各列に1個クイーンを配置する組み合わせをしらみつぶしに調べる。
置き方の総数は
まで減る。
n=8の場合40,320通り。
バックトラック法
斜めについても同様である。
しらみつぶしを行う際、解でないことが判明した枝についてはさらに下位の枝について調査しても無駄である。
その枝については調査をうちきり、親の枝に戻る。
このことを枝刈りという。
生成後検査法ではクイーンを8個配置した後に解であるかを検査していたが、バックトラック法ではクイーンを8個配置できた時点で自動的に解となる。
早めに大きな枝を早く刈ることが出来れば計算量は激減する。
結果
記述中
考察
記述中
感想
記述中
参考文献
石畑清. 岩波講座ソフトウェア科学3 アルゴリズムとデータ構造, 1990, 岩波書店
柴田望洋 辻亮介. 新版 C言語によるアルゴリズムとデータ構造, 2005, ソフトバンクパブリッシング
河西 朝雄. C言語によるはじめてのアルゴリズム入門, , 技術評論社
使用方法
Ubuntu 10.04、Debian squeeze、MS WindowsXP、MS-DOS 5.0上で動作を確認した。
実行時に女王の個数をコマンドラインオプションとして指定する。
例えば次のようにすると8女王問題の解を列挙する。
例 実行ファイルがnqueen (nqueen.exe)の場合
(Linux/UNIX) ./nqueen 8
(Windows/DOS) nqueen 8
解1 1試行
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
中略
解92 92試行
. . . . . . . Q
. . . Q . . . .
Q . . . . . . .
. . Q . . . . .
. . . . . Q . .
. Q . . . . . .
. . . . . . Q .
. . . . Q . . .
8女王 解92個 試行回数92回
試行回数/解 1
さらに第2引数を指定することで別の解法を試すこともできる。
解法次第で処理速度が大きく異なることがわかる。
例 $./nqueen
| 第2引数 |
解法 |
| 0 |
1からnまでの解の数を表示 |
| 1 |
生成後検査法 列に対して |
| 2 |
生成後検査法 行に対して |
| 3 |
バックトラック法 |
第2引数を指定していない場合は自動的にバックトラック法が適用される。
なおバックトラック法では枝刈りを行うので試行回数の表示に妥当性はない。
第2引数に0を指定すると1からnまでの解の数が表示される。
亀山くんより女王の個数と解の個数の関係を見つけられたら面白いのではとの指摘を受け実装してみた。
例 ./nqueen 20 0
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
18 666090624
19 673090552
20 374483220
21 1133610104
nが大きくなるにつれて飛躍的に計算回数が多くなるので注意。
n=20まで計算するのにAthlon64X2 2.6GHz機で一週間程度かかっている。またn=21までは約40日かかった。
女王と解の関係性を見つけられた人はぜひ教えてください。
ソースコード
いきあたりばったりで作ったので自作関数の引数がひどいことになっているのはご愛嬌。
free()の使い方とか間違っているかもしれない。
#include <stdio.h>
#include <stdlib.h>
void queen1(int i, int num, int *q);
void queen2(int i, int num, int *q, int *c);
void queen3(int i, int num, int *q, int *c, int *l, int *r, int mode);
void queensolve(int num, int *q, int *c, int *l, int *r);
void print(int num, int *q);
void check(int num, int *q);
int sn = 0; /* 解カウンター */
int t = 0; /* 試行回数カウンター */
int main(int argc, char *argv[])
{
int *q, *c, *l, *r;
int num, i;
if (argc < 2) {
fprintf(stderr, "Usage: %s n [1-3]\n", argv[0]);
exit(1);
}
num = atoi(argv[1]);
q = (int*)malloc(sizeof(int) * num);
c = (int*)malloc(sizeof(int) * num);
l = (int*)malloc(sizeof(int) * 2 * num);
r = (int*)malloc(sizeof(int) * 2 * num);
for (i = 0; i < num; i++) {
q[i] = c[i] = 0;
}
for (i = 0; i < 2 * num; i++) {
l[i] = r[i] = 0;
}
if (argc == 2) {
queen3(0, num, q, c, l, r, 1);
}
else {
switch (atoi(argv[2])) {
case 1:
queen1(0, num, q);
break;
case 2:
queen2(0, num, q, c);
break;
case 3:
queen3(0, num, q, c, l, r, 1);
break;
default :
queensolve(num, q, c, l, r);
}
}
printf("%d女王 解%d個 試行回数%d回\n", num, sn, t);
if (sn != 0) {
printf("試行回数/解 %d\n", t/sn);
}
free(q);
free(c);
free(l);
free(r);
return 0;
}
/* 解のチェック (生成後検査法にて使用) */
void check(int num, int *q)
{
int i, j, n;
int *c_c;
int *c_r;
int *c_l;
c_c = (int*)malloc(sizeof(int) * num);
c_r = (int*)malloc(sizeof(int) * 2 * num);
c_l = (int*)malloc(sizeof(int) * 2 * num);
n = 0;
for (i = 0; i < num; i++) {
c_c[i] = 0;
}
for (i = 0; i < 2 * num; i++) {
c_r[i] = c_l[i] = 0;
}
for (i = 0; i < num; i++) {
for (j = 0; j < num; j++) {
if (q[i] == j && c_c[j] == 0 &&
c_r[i + j] == 0 && c_l[i - j + num - 1] == 0) {
c_c[j] = 1;
c_r[i + j] = 1;
c_l[i - j + num - 1] = 1;
n++;
}
}
}
if (n == num) {
++sn;
print(num, q);
}
free(c_c);
free(c_l);
free(c_r);
}
/* 盤面の表示 */
void print(int num, int *q)
{
int i, j;
int x, y;
printf(" 解%d %d試行\n", sn, t);
for (i = 0; i < num; i++) {
for (j = 0; j < num; j++) {
if (q[i] == j) {
printf(" Q");
}
else {
printf(" .");
}
}
printf("\n");
}
printf("\n");
}
/* クイーンを配置 各列にクイーン(生成後検査法1) */
void queen1(int i, int num, int *q)
{
int j;
for (j = 0; j < num; j++) {
q[i] = j;
if (i == (num - 1)) {
t++;
check(num, q);
}
else queen1(i + 1, num, q);
}
}
/* クイーンを配置 各行各列にクイーン(生成後検査法2) */
void queen2(int i, int num, int *q, int *c)
{
int j;
for (j = 0; j < num; j++) {
if (c[j] == 0) {
q[i] = j;
c[j] = 1;
if (i == (num - 1)) {
t++;
check(num, q);
}
else queen2(i + 1, num, q, c);
c[j] = 0;
}
}
}
/* クイーンを配置 斜めも考慮(バックトラック法) */
void queen3(int i, int num, int *q, int *c, int *l, int *r, int mode)
{
int j;
for (j = 0; j < num; j++) {
if (c[j] == 0 && r[i + j] == 0 && l[i - j + num - 1] == 0) {
q[i] = j;
c[j] = r[i + j] = l[i - j + num - 1] = 1;
if (i == (num - 1)) {
t++;
sn++;
if (mode == 1) {
print(num, q);
}
}
else queen3(i + 1, num, q, c, l, r, mode);
c[j] = r[i + j] = l[i - j + num - 1] = 0;
}
}
}
/* 1?n女王問題の解の数を求める */
void queensolve(int num, int *q, int *c, int *l, int *r)
{
int i;
for (i = 0; i < num; i++) {
q[i] = c[i] = 0;
}
for (i = 0; i < 2 * num; i++) {
l[i] = r[i] = 0;
}
for (i = 1; i <= num; i++) {
sn = 0;
queen3(0, i, q, c, l, r, 0);
printf("%d\t%d\n", i, sn);
}
free(q);
free(c);
free(l);
free(r);
exit(0);
}
最終更新：2010年12月21日 01:48
