今回の問題は、「ナイトの巡歴」です。将棋の桂馬は前方向２カ所にしか動けませんが、 チェスのナイトは前後左右の８カ所に動くことができます。下図を見てください。
| O | O | |||
| O | O | |||
| K | ||||
| O | O | |||
| O | O |
「ナイトの巡歴」は、ナイトを動かしてすべてのマス目を訪れる経路を求める問題です。 チェス本来の８x８盤面では、長い時間が掛かってしまいますので、まずは３x４での解法プログラムを紹介します。
use strict;
my %jump;
my $m = 4; my $n = 3; my $start = "11";
foreach (grep /^[1-$m][1-$n]$/, 11 .. ($m . $n)) {
my ($i, $j) = split //, $_;
@{$jump{$_}} = grep /^[1-$m][1-$n]$/, (($i - 2) . ($j - 1), ($i - 2) . ($j + 1),
($i - 1) . ($j - 2), ($i - 1) . ($j + 2),
($i + 1) . ($j - 2), ($i + 1) . ($j + 2),
($i + 2) . ($j - 1), ($i + 2) . ($j + 1));
}
my @keiro = ([$start]);
while (@keiro) {
my $ref = pop(@keiro);
my $c_p = $ref->[0];
my @before = gather($ref);
foreach my $n_p (@{$jump{$c_p}}) {
next if grep /$n_p/, @before;
if (@before == ($m * $n - 1)) {
print join(" => ", @before), " => $n_p\n";
} else {
push @keiro, [$n_p, $ref];
}
}
}
sub gather {
my $tmp_ref = shift;
my @work;
while ($tmp_ref) {
my $pos;
($pos, $tmp_ref) = @$tmp_ref;
unshift @work, $pos;
}
return @work;
}まず最初に、準備段階として、盤面のマス目毎に番号を付けます。 番号の付け方としては、１から順番に付ける方法もありますが、今回は左上を 11 として右下は 43 になるように付けます。その部分のプログラムを見てみましょう。
my $m = 4; my $n = 3; foreach (grep /^[1-$m][1-$n]$/, 11 .. ($m . $n))
変数 $m に行数、変数 $n に列数を指定します。そして、foreach の LIST 部で盤面を作成してしまいます。作成される盤面は、下図のようになります。
| 11 | 12 | 13 |
| 21 | 22 | 23 |
| 31 | 32 | 33 |
| 41 | 42 | 43 |
次に、foreach のループを使ってマス目毎に移動リストを作成します。 マス目が２桁の数字になっているので、計算によって移動リストを作成することができます。
foreach (grep /^[1-$m][1-$n]$/, 11 .. ($m . $n)) {
my ($i, $j) = split //, $_;
@{$jump{$_}} = grep /^[1-$m][1-$n]$/, (($i - 2) . ($j - 1), ($i - 2) . ($j + 1),
($i - 1) . ($j - 2), ($i - 1) . ($j + 2),
($i + 1) . ($j - 2), ($i + 1) . ($j + 2),
($i + 2) . ($j - 1), ($i + 2) . ($j + 1));
}
このコードを実行することによって、ハッシュ %jump が作成されます。これは、以下のコードを実行するのと等価になります (４x３の場合)。
%jump = ( 11 => [23, 32],
12 => [31, 33],
...
23 => [11, 31, 42],
31 => [12, 23, 43],
...
42 => [21, 23],
43 => [22, 31]);
これで、準備は完了です。ここでのポイントは、変数 $m と $n を指定することによって、９x９までの任意の盤面と移動リストを作成できることです。 このようにしておけば、盤面の大きさを変更してテストするのに非常に便利になります。
さていよいよ、経路の探索です。その前に、経路情報の管理方法について述べます。配列 @keiro は、最初に [$start] だけが入っていますが、その後は探索途中の末尾のデータが格納されます。 そのデータ構造は、[pos, ref] のようになっており、pos は現在のマス目の位置、ref はその前の無名配列へのリファレンスになっています。その前の無名配列は、位置とその前の前へのリファレンスを 持っています。このようにして、スタート位置からの経路を保持します (サブルーチン gather は、経路を収集する役割をする)。それでは、経路の探索のプログラムを見てみましょう。
while (@keiro) {
my $ref = pop(@keiro);
my $c_p = $ref->[0];
my @before = gather($ref);
foreach my $n_p (@{$jump{$c_p}}) {
next if grep /$n_p/, @before;
if (@before == ($m * $n - 1)) {
print join(" => ", @before), " => ", $n_p, "\n";
} else {
push @keiro, [$n_p, $ref];
}
}
}
今回のプログラムでは、while ループを使ってみました。まず、@keiro から pop を使って１つ取り出します。ここでの pop は、少し偽物の深さ優先探索 (幅併用型) になります。代わりに shift 使えば、(こちらは正真正銘の) 幅優先探索になります。 pop で取り出したのは、配列へのリファレンスなのでそれを保存し、そのリファレンスから変数 $c_p (現在位置) と @before (スタート位置からの経路情報) を作成します。 後は簡単で、%jump から次の移動位置を取得して、すでに訪れたマス目ならスキップし、 ゴールの場合は表示します。また、探索の途中の場合は、@keiro に保存して次のループに移ります。
プログラムを実行して、いろいろとテストしてみることにしましょう。 まずは、このプログラムを実行して得られる出力です。
11 => 32 => 13 => 21 => 42 => 23 => 31 => 43 => 22 => 41 => 33 => 12 11 => 32 => 13 => 21 => 42 => 23 => 31 => 12 => 33 => 41 => 22 => 43
次に、盤面の大きさを変えながらテストしてみます。 求めるのは、経路数と掛かる時間です。なお時間の計測は、次のコードを使いました。
my $sw = time(); # プログラムの最初の方に置く ... END { print time() - $sw, " seconds\n"; } # プログラムの最後に置く
END ブロックを使うと、１つの経路を探索した時点で exit でプログラムを終了したとしても実行されます。全経路探索でも、１つの経路探索でも共通して使えます。 以下のデータは、私のパソコンで実行した結果です。
| while版 | | | 再帰版 | |||
|---|---|---|---|---|---|
| 経路数 | 全経路 | １つ | | | １つ | |
| 4 x 4 | 0 | 1 | - | | | - |
| 5 x 4 | 32 | 5 | 0 | | | 0 |
| 5 x 5 | 304 | 308 | 9 | | | 1 |
| 6 x 5 | 4542 | 20630 | 90 | | | 7 |
| 6 x 6 | - | - | 27 | | | 46 |
| 7 x 6 | - | - | 2 | | | 2729 |
| 7 x 7 | - | - | 32224 | | | 52 |
| 8 x 7 | - | - | 113 | | | 59 |
| 8 x 8 | - | - | give up | | | 8830 |
$m と $n を１ずつ交互に増やして、経路数と、全経路探索に掛かった時間と、 １つの経路探索に掛かった時間を調べてみました。４x４の盤面では、正解はありません。 全経路探索に掛かる時間は、５x５では５分ほどですが、６x５では５時間４０分ほどになってしまいます。 これほどの割合で、時間が増えるとは思ってもいませんでした。この割合で時間が増えるとすると、６x６では ..... 。という訳で、６x６以上の盤面での全経路探索は諦めました。
１つだけ解を求める探索の方は、頑張って (別に自分でやったのではないが) チェス本来の８x８の大きさまでやってみました。事前に多少の当たり外れがあることは予想していましたが、 これほど極端に現れるとは驚きです。７x６の盤面ではわずか２秒しか掛かりませんが、 ７x７の盤面では９時間弱も掛かってしまいます。それでいて、８x７の盤面では２分弱です。 ８x８の盤面では、４８時間経過しても終了せず、降参しました。ここでプログラムを以下のように少し変更して、 １つの経路探索の結果を見てみます。変更するのは、while の部分です。
search ([$start]);
sub search {
my $ref = shift;
my $c_p = $ref->[0];
my @before = gather($ref);
foreach my $n_p (@{$jump{$c_p}}) {
next if grep /$n_p/, @before;
if (@before == ($m * $n - 1)) {
print join(" => ", @before), " => $n_p\n";
exit;
} else {
search([$n_p, $ref]);
}
}
}
元のプログラムでは %jump のリストは末尾から探索されますが、 こちら再帰版のプログラムでは先頭から探索されます。また、再帰版は純粋な深さ優先探索のため、 効率の面でも優ります (ただし、全経路探索の場合は、変わりません)。 先ほどの表の最後に、再帰版の経路探索に掛かった時間を追加しておきます。 今度は８x８の盤面まで探索することができましたが、 相変わらずのランダムな結果です。結論として、１つの深さ優先探索結果だけでは、 プログラムの実行速度を論ずることができない、ということでしょうか。
最後に８x８の盤面で、短時間に探索できるプログラムを紹介しましょう。 前の表では、"降参" と "147分" でしたが、次のプログラムでは果たして ..... 。 プログラムの解説はしませんので、考えてみてください。でも、インチキだと言わないで下さいね。
use strict;
my @areas = ([ grep /^[1-4][1-3]$/, 11 .. 43 ], [ grep /^[5-8][1-3]$/, 51 .. 83 ],
[ grep /^[1-4][4-8]$/, 14 .. 48 ], [ grep /^[5-8][4-8]$/, 54 .. 88 ]);
my @patt = ("[1-4][1-3]", "[5-8][1-3]", "[1-4][4-8]", "[5-8][4-8]");
search(0, 12, 'dummy', '11');
sub search {
my ($no, $elms, $jump, $before) = @_;
my $c_p = substr($before, -2);
if ($jump eq 'dummy') {
my %jump;
foreach ($c_p, @{$areas[$no]}) {
my ($i, $j) = split //, $_;
@{$jump{$_}} = grep /^$patt[$no]$/, (($i - 2) . ($j - 1), ($i - 2) . ($j + 1),
($i - 1) . ($j - 2), ($i - 1) . ($j + 2),
($i + 1) . ($j - 2), ($i + 1) . ($j + 2),
($i + 2) . ($j - 1), ($i + 2) . ($j + 1));
}
$jump = \%jump;
}
foreach my $n_p (@{$jump->{$c_p}}) {
next if $before =~ /\b$n_p\b/;
if ($before =~ tr/:// != ($elms - 2)) {
search($no, $elms, $jump, $before . ':'. $n_p);
} else {
if ($before =~ tr/:// == 62) {
my $count = 0;
foreach my $pos (split(/:/, $before), $n_p) {
$count++;
if ($count % 10 && $count != 64) { print "$pos => "; }
elsif ($count % 10 && $count == 64) { print "$pos\n"; }
else { print "$pos =>\n"; }
}
exit;
} else {
search($no + 1, $elms + @{$areas[$no + 1]}, 'dummy', $before . ':' . $n_p);
}
}
}
}(2005/05/10)