パズルの解法
今回は「パズル」を題材にプログラムを作ってみましょう。どのプログラミング言語でもそうですが、上達の秘訣は実際にプログラムを作って動作を確認してみることです。ところが、いざとなると「さて何を作ろうか」と困ってしまう方もいるのではないでしょうか。
このようなときにぴったりな題材が「パズルの解法」です。なんといっても、実際にパズルが解けたときの喜びはとても大きく、プログラムを作る意欲をかきたててくれます。そこで、今回はバックトラック法を使って簡単なパズルを解いてみましょう。
●8 クイーン
最初に簡単な例題として「8 クイーン」を取り上げます。これはコンピュータに解かせるパズルの中でも特に有名な問題です。8 クイーンは 8 行 8 列のチェスの升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を次に示します。
図 : 8 クイーンの解答例
8 クイーンを解くには、基本的にはすべての置き方を試してみるしかありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあります。したがって、置き方の総数は 64 から 57 までを掛け算した 178,462,987,637,760 通りあることがわかります。これはとても大きな数ですね。
ところが、解答例を見ればおわかりのように、同じ行と列に 2 つ以上のクイーンを置くことはできません。上図の解答例を配列を使って表すと、次のようになります。
0 1 2 3 4 5 6 7 <--- 列の位置
------------------
[0 6 4 7 1 3 5 2] <--- 要素が行の位置を表す
図 : 8 クイーンの表現方法
列を配列の位置 (添字) に行番号を要素に対応させれば、各要素には 0 から 7 までの数字が重複しないで入ることになります。すなわち、0 から 7 までの順列の総数である 8! = 40320 通りの置き方を調べればよいことになります。数がぐっと減りましたね。パズルを解く場合、そのパズル固有の性質をうまく使って、調べなければならない置き方の総数を減らすように工夫することが大切です。
順列を生成するプログラムは簡単です。あとは、その順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。このように正解の可能性があるデータを作り、それが条件を満たしているかテストするという方法を「生成検定法 (generate and test)」といいます。可能性のあるデータをもれなく作るのにバックトラック法は最適です。ただし、生成するデータ数が多くなると、実行時間がとてもかかるという弱点もあるので注意してください。
●単純な生成検定法
それでは、プログラムを作りましょう。次のリストを見てください。
#
# queen.pl : 8 クイーンの解法
#
# Copyright (C) 2015-2023 Makoto Hiroi
#
use strict;
use warnings;
# 衝突のチェック
sub attack {
my ($i, $xs) = @_;
my $x = $xs->[$i++];
my $z = 1;
for (; $i < @$xs; $i++, $z++) {
my $y = $xs->[$i];
return 1 if $y + $z == $x || $y - $z == $x;
}
return 0;
}
# 安全か？
sub safe {
my $xs = shift;
for (my $i = 0; $i < @$xs; $i++) {
return 0 if attack($i, $xs);
}
1;
}
# 8 クイーンの解法
sub queen {
my ($n, $xs) = @_;
if ($n == @$xs) {
print "@$xs\n" if safe($xs);
} else {
my $temp = $xs->[$n];
for (my $i = $n; $i < @$xs; $i++) {
$xs->[$n] = $xs->[$i];
$xs->[$i] = $temp;
queen($n + 1, $xs);
$xs->[$i] = $xs->[$n];
$xs->[$n] = $temp;
}
}
}
# 実行
queen(0, [0 .. 7]);
関数 queen は配列 $xs の要素を交換して順列を生成します。順列が完成したら、8 クイーンの条件を満たしているかチェックします。関数 safe は配列の先頭の要素から順番に衝突のチェックを行います。端にあるクイーンから順番に調べるとすると、斜めの利き筋は次のように表すことができます。
1 2 3 --> 調べる方向
*-------------
| . . . . . .
| . . . -3. . 5 - 3 = 2
| . . -2. . . 5 - 2 = 3
| . -1. . . . 5 - 1 = 4
| Q . . . . . Q の位置は 5
| . +1. . . . 5 + 1 = 6
| . . +2. . . 5 + 2 = 7
| . . . +3. . 5 + 2 = 8
*-------------
図 : 衝突の検出
図を見てもらえばおわかりのように、Q が行 5 にある場合、ひとつ隣の列は 4 と 6 が利き筋に当たります。2 つ隣の列の場合は 3 と 7 が利き筋に当たります。このように単純な足し算と引き算で、利き筋を計算することができます。この処理を関数 attack で行います。
attack は配列の先頭から斜めの利き筋に当たるか調べます。引数 $i がチェックするクイーンの位置、$xs がクイーンを格納した配列、変数 $z が差分を表します。最初にチェックするクイーンを変数 $x にセットします。次に、for ループで $xs からクイーン $y を取り出し、$y + $z または $y - $z が $x と等しいかチェックします。等しい場合は衝突しているので 1 を返します。そうでなければ、次のクイーンを調べます。このとき、差分 $z を +1 することをお忘れなく。すべてのクイーンを調べたら 0 を返します。
●実行結果
これでプログラムは完成です。それでは実行してみましょう。
$ perl queen.pl 0 4 7 5 2 6 1 3 0 5 7 2 6 3 1 4 0 6 3 5 7 1 4 2 ・・・省略・・・ 7 1 4 2 0 6 3 5 7 2 0 5 1 4 6 3 7 3 0 2 5 1 6 4
8 クイーンの場合、回転解や鏡像解を含めると全部で 92 通りあります。
●プログラムの高速化
ところで、このプログラムは順列を生成してからクイーンの衝突チェックを行っているため、あまり効率的ではありません。最近のパソコンであれば、8 クイーンはこのプログラムでも短時間で解くことができますが、クイーンの個数を増やすと実行時間がかかるようになります。実際に試してみると、実行時間は次のようになりました。
表 : 8 クイーンの実行時間 (秒) 個数 : 8 : 9 : 10 ------+------+------+------ 解 : 92 : 352 : 724 queen : 0.15 : 1.23 : 12.68 実行環境 : Perl v5.34.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
クイーンの個数をひとつ増やしただけでも、実行時間はとても遅くなります。なぜかというと、失敗することがわかっている順列も生成しているからです。
たとえば、最初 (0, 0) の位置にクイーンを置くと、次のクイーンは (1, 1) の位置に置くことはできません。したがって、(0 1 X X X X X X) という配置はすべて失敗することがわかるわけですが、順列を発生させてからチェックする方法では、このような無駄を省くことができません。そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。
#
# queen1.pl : 8 クイーンの解法
#
# Copyright (C) 2015-2023 Makoto Hiroi
#
use strict;
use warnings;
our $count = 0;
sub attack {
my ($i, $xs) = @_;
my $x = $xs->[$i--];
my $z = 1;
for (; $i >= 0; $i--, $z++) {
my $y = $xs->[$i];
return 1 if $y + $z == $x || $y - $z == $x;
}
return 0;
}
sub queen1 {
my ($n, $xs) = @_;
if ($n == @$xs) {
$count++;
} else {
my $temp = $xs->[$n];
for (my $i = $n; $i < @$xs; $i++) {
$xs->[$n] = $xs->[$i];
$xs->[$i] = $temp;
queen1($n + 1, $xs) if !attack($n, $xs);
$xs->[$i] = $xs->[$n];
$xs->[$n] = $temp;
}
}
}
queen1(0, [0 .. 7]);
print $count;
関数 queen1 でクイーンを選択するとき、関数 attack を呼び出して選択したクイーンが衝突しないかチェックします。queen1 の中で attack を呼び出すので、関数 safe は必要ありません。クイーンは配列の末尾に追加するので、関数 attack は末尾から先頭に向かってチェックしていくことに注意してください。
●実行結果 (2)
実行時間は次のようになりました。
表 : 8 クイーンの実行時間 (秒) 個数 : 8 : 9 : 10 ------+-------+-------+------- 解 : 92 : 352 : 724 queen : 0.15 : 1.23 : 12.68 queen1: 0.014 : 0.038 : 0.152 実行環境 : Perl v5.34.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
実行時間は大幅に短縮されました。このように、できるだけ早い段階でチェックを入れることで、無駄なデータをカットすることを「枝刈り」と呼びます。バックトラック法を使ってパズルを解く場合、この枝刈りのよしあしによって実行時間が大きく左右されます。
ただし、枝刈りのやり方は問題によって大きく変わります。「斜めの利き筋をチェックする」という枝刈りは、8 クイーン固有の性質を使ったやり方であり、これをそのまま他のパズルに使うことはできません。パズル固有の性質を調べて、適切な枝刈りを考えることが重要なのです。パズル自体はコンピュータに解かせるのですが、枝刈りの条件は私達が考えるわけですね。これも「パズルの解法」のおもしろさのひとつといえるでしょう。解を求めるだけではなく、いかに効率の良い条件を見つけて実行時間を短縮するか、ということでも楽しむことができるわけです。
なお、n 行 n 列の盤面でクイーンの配置を求める問題を "N Queens Problem" といいます。クイーンの個数が増えると queen1 でも遅くなるので、もっと高速な方法が必要になります。興味のある方は拙作のページ お気楽Ｃ言語プログラミング超入門 N Queens Problem をお読みください。
●騎士の巡歴
もう一つチェスを使ったパズルを紹介しましょう。ナイト (騎士) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
問題 : 騎士の巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求める問題を「騎士の巡歴」といいます。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。5 行 5 列の盤面でナイトの移動経路の総数を求めてみましょう。
●盤面の定義
今回は盤面を 2 次元配列で表すことにします。この場合、騎士の移動手順は 5 行 5 列の盤面に記録したほうが簡単です。騎士が訪れていないマスを 0 とし、騎士の移動手順を 1 から始めれば、移動できるマスの判定を簡単に行うことができます。また、経路の出力も盤面を表示した方が直感的でわかりやすいかもしれません。
次は盤面の構成を考えましょう。単純な 5 行 5 列の 2 次元配列にすると、騎士が盤面から飛び出さないようにするため座標の範囲チェックが必要になります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。
騎士は最大で 2 マス移動するので、壁の厚さも 2 マス用意します。したがって、盤面を表す配列は 9 行 9 列の大きさになります。壁に 0 以外の値 (1) を設定しておけば、騎士が盤面から飛び出して壁の位置に移動しようとしても、盤面の値が 0 ではないので実際に移動することはできません。これで騎士を移動したときの範囲チェックを省略することができます。
●プログラムの作成
プログラムは次のようになります。
リスト : 騎士の巡歴 (knight.pl)
#
# knight.pl : 騎士巡歴の問題
#
# Copyright (C) 2015-2023 Makoto Hiroi
#
# 大域変数
our @board; # 盤面
our $size = 5; # 大きさ
our $count = 0; # 解の総数
# ナイトの移動量
our @dx = ( 1, 2, 2, 1, -1, -2, -2, -1);
our @dy = (-2, -1, 1, 2, 2, 1, -1, -2);
# 盤面の初期化
sub init_board {
my $board_size = $size + 4;
@board = ();
for (my $y = 0; $y < $board_size; $y++) {
$board[$y] = [];
for (my $x = 0; $x < $board_size; $x++) {
if ($x < 2 || $x > 6 || $y < 2 || $y > 6) {
$board[$y][$x] = 1;
} else {
$board[$y][$x] = 0;
}
}
}
}
# 盤面の表示
sub print_board {
for (my $y = 2; $y < $size + 2; $y++) {
for (my $x = 2; $x < $size + 2; $x++) {
printf("%2d ", $board[$x][$y]);
}
print "\n";
}
print "\n";
}
# 探索
sub solver {
my ($n, $x, $y) = @_;
if ($n > $size * $size) {
$count++;
print_board();
} else {
for (my $i = 0; $i < @dx; $i++) {
my $x1 = $x + $dx[$i];
my $y1 = $y + $dy[$i];
if (!$board[$x1][$y1]) {
$board[$x1][$y1] = $n;
solver($n + 1, $x1, $y1);
$board[$x1][$y1] = 0;
}
}
}
}
init_board();
$board[2][2] = 1;
solver(2, 2, 2);
print $count, "\n";
配列 @dx は騎士の x 方向の変位、配列 @dy は y 方向の変位を表します。現在の座標にこの値を加えることで、次の座標を決定します。配列 @board は盤面を表します。関数 init_board で、壁の部分は 1 に、実際の盤面は 0 に初期化しておきます。
関数 solver は引数として手数 $n と騎士の座標 $x, $y を受け取ります。まず、$n が $size * $size (25) よりも大きくなったかチェックします。そうであれば、騎士はすべてのマスを訪れたので、print_board で盤面を出力します。
そうでなければ、次に移動するマスを選びます。for 文で @dx と @dy の要素を取り出して $x と $y の値に加え、solver を再帰呼び出しします。@board は大域変数なので、再帰呼び出しから戻ってきたら、$board[$x1][$y1] の値を 0 に戻すことをお忘れなく。あとはとくに難しいところはないと思います。
●実行結果
実行結果は次のようになります。
$ perl knight.pl 1 20 17 12 3 16 11 2 7 18 21 24 19 4 13 10 15 6 23 8 25 22 9 14 5 ・・・省略・・・ 1 10 15 20 23 16 5 22 9 14 11 2 19 24 21 6 17 4 13 8 3 12 7 18 25 304
解は全部で 304 通りあります。
●マスターマインド
パズルではありませんが、簡単な例題として「マスターマインド」を解くプログラムを作りましょう。マスターマインドは拙作のページ 関数 で作成した、0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームでした。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。
[6 2 8 1] : 正解
---------------------------------
1. [0 1 2 3] : cows 2 : bulls 0
2. [1 0 4 5] : cows 1 : bulls 0
3. [2 3 5 6] : cows 2 : bulls 0
4. [3 2 7 4] : cows 0 : bulls 1
5. [3 6 0 8] : cows 2 : bulls 0
6. [6 2 8 1] : cows 0 : bulls 4
図 : マスターマインドの動作例
今回は、私達が出した問題をコンピュータに答えてもらうことにします。それはちょっと難しいのではないか、と思った人もいるかもしれませんね。ところが、とても簡単な方法があるのです。このゲームでは、10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。コードを生成する処理は順列と同じですから、簡単にプログラムできます。
●推測アルゴリズム
次に、この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。
矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、次の例を考えてみてください。
[6 2 8 1] が正解の場合
[0 1 2 3] => bulls = 0, cows = 2
[0 1 2 3] と比較する
--------------------------------------------------------
[0 X X X] 0 から始まるコードは bulls = 1
になるので矛盾する。
・・・・
[1 0 3 4] cows = 3, bulls = 0 になるので矛盾する
・・・・
[1 0 4 5] cows = 2, bulls = 0 で矛盾しない。
--------------------------------------------------------
[1 0 4 5] => bulls = 0, cows = 1
次は、[0 1 2 3] と [1 0 4 5] に矛盾しない数字を選ぶ
図 : マスターマインドの推測アルゴリズム
[0 1 2 3] で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、[0 X X X] というコードは [0 1 2 3] と比較すると bulls が 1 となるので、矛盾していることがわかります。
次に [1 0 3 4] というコードを考えてみます。[0 1 2 3] の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、[1 0 3 4] と [0 1 2 3] と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。
次に [1 0 4 5] というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は [0 1 2 3] と [1 0 4 5] に矛盾しないコードを選択するのです。
●プログラムの作成
それでは、プログラムを作っていきましょう。まず、質問したコードとその結果を記憶する大域変数を定義します。
リスト : 大域変数の定義 # 質問したコードと結果 # [[[0,1,2,3], bulls, cows], ... ] our @query;
質問したコードとその結果は無名の配列にまとめて格納します。最初が質問したコードで、次が bulls の個数、最後が cows の個数とします。これを一組のデータとして配列に格納して、大域変数 @query にセットします。
マスターマインドを解くプログラムは次のようになります。
リスト : マスターマインドの解法
# 順列の生成
our $perm_table = permutations_list(4, [0 .. 9]);
# 解法
sub solver {
my $ans = shift;
my $cnt = 1;
@query = ();
foreach my $code (@$perm_table) {
if (check_query($code)) {
my $bulls = count_bulls($ans, $code);
my $cows = count_same_number($ans, $code) - $bulls;
push @query, [$code, $bulls, $cows];
print "$cnt : @$code : bulls = $bulls, cows = $cows\n";
last if $bulls == 4;
$cnt++;
}
}
print "おめでとう\n";
}
まず最初に、関数 permutatios_list で順列を生成して、大域変数 $perm_table にセットします。permutatios_list は生成した順列を無名の配列に格納して返します。
関数 solver の引数 $ans が正解のコードです。質問回数 $cnt を 1 に、大域変数 @query を空の配列に初期化します。あとは、大域変数 $perm_table から順列を取り出して $code にセットし、関数 check_query で今まで質問したコードと矛盾しないかチェックします。
矛盾しない場合、関数 count_bulls と count_same_number で $bulls と $cows を求めて、$code といっしょに無名の配列に格納し、それを @query に push で追加します。あとは結果を表示して、$bulls が 4 ならば last でループを脱出します。
次は、関数 check_query を作ります。
リスト : 今まで質問したコードと矛盾していないか
sub check_query {
my $code = shift;
foreach my $q (@query) {
my $bulls = count_bulls($code, $q->[0]);
my $cows = count_same_number($code, $q->[0]) - $bulls;
return 0 if $bulls != $q->[1] || $cows != $q->[2];
}
1;
}
check_query は foreach 文で @query に格納されたデータをチェックしていきます。すべてのデータで矛盾がなければ 1 を返します。引数のコード $code と質問したコード q->[0] から $bulls と $cows を求め、その結果が $q->[1] と $q->[2] に等しくなければ、$code は矛盾しています。return で 0 を返します。
●何回で当たるか
これでプログラムは完成です。それでは実際に試してみましょう。
mhiroi@mhiroi-VirtualBox:~/perl$ perl master.pl 1 : 0 1 2 3 : bulls = 0, cows = 0 2 : 4 5 6 7 : bulls = 0, cows = 2 3 : 5 4 8 9 : bulls = 0, cows = 2 4 : 6 7 9 8 : bulls = 0, cows = 4 5 : 8 9 7 6 : bulls = 2, cows = 2 6 : 9 8 7 6 : bulls = 4, cows = 0 おめでとう 1 : 0 1 2 3 : bulls = 0, cows = 2 2 : 1 0 4 5 : bulls = 0, cows = 2 3 : 2 3 5 4 : bulls = 0, cows = 2 4 : 3 4 0 6 : bulls = 1, cows = 1 5 : 3 5 6 1 : bulls = 1, cows = 1 6 : 6 5 0 2 : bulls = 0, cows = 0 7 : 7 4 3 1 : bulls = 3, cows = 0 8 : 8 4 3 1 : bulls = 3, cows = 0 9 : 9 4 3 1 : bulls = 4, cows = 0 おめでとう
肝心の質問回数ですが、5, 6 回で当たる場合が多いようです。実際に、5040 個のコードをすべて試してみたところ、平均は 5.56 回になりました。これは 参考文献 1 の結果と同じです。質問回数の最大値は 9 回で、そのときのコードは [5 2 9 3], [9 2 4 1], [9 2 5 0], [9 2 0 4] [9 4 3 1] でした。
なお、参考文献 1 には平均質問回数がこれよりも少なくなる方法が紹介されています。単純な数当てゲームだと思っていましたが、その奥はけっこう深いようです。興味のある方はいろいろ試してみてください。
●参考文献
- 田中哲郎 「数当てゲーム (MOO, マスターマインド)」, 松原仁、竹内郁雄 編 『bit 別冊 ゲームプログラミング』 pp150 - 157, 共立出版, 1997
●プログラムリスト
#
# master.pl : マスターマインドの解法
#
# Copyright (C) 2015-2023 Makoto Hiroi
#
use strict;
use warnings;
#
# 順列の生成
#
sub perm_sub {
my ($f, $i, $n, $xs) = @_;
if ($n == $i) {
$f->([@$xs[0 .. $n - 1]]);
} else {
my $temp = $xs->[$i];
for (my $j = $i; $j < @$xs; $j++) {
$xs->[$i] = $xs->[$j];
$xs->[$j] = $temp;
perm_sub($f, $i + 1, $n, $xs);
$xs->[$j] = $xs->[$i];
$xs->[$i] = $temp;
}
}
}
sub permutations {
my ($f, $n, $xs) = @_;
perm_sub($f, 0, $n, $xs);
}
sub permutations_list {
my ($n, $xs) = @_;
my $a = [];
permutations(sub {push @$a, shift}, $n, $xs);
$a;
}
# bulls を数える
sub count_bulls {
my ($xs, $ys) = @_;
my $c = 0;
for (my $i = 0; $i < @$xs; $i++) {
$c++ if $xs->[$i] == $ys->[$i];
}
$c;
}
# 同じ数字の個数を数える
sub count_same_number {
my ($xs, $ys) = @_;
my $c = 0;
foreach my $x (@$xs) {
foreach my $y (@$ys) {
$c++ if $x == $y;
}
}
$c;
}
# 質問したコードと結果
# [[[0,1,2,3], bulls, cows], ... ]
our @query;
# コードが矛盾しないか
sub check_query {
my $code = shift;
foreach my $q (@query) {
my $bulls = count_bulls($code, $q->[0]);
my $cows = count_same_number($code, $q->[0]) - $bulls;
return 0 if $bulls != $q->[1] || $cows != $q->[2];
}
1;
}
# 順列の生成
our $perm_table = permutations_list(4, [0 .. 9]);
# 解法
sub solver {
my $ans = shift;
my $cnt = 1;
@query = ();
foreach my $code (@$perm_table) {
if (check_query($code)) {
my $bulls = count_bulls($ans, $code);
my $cows = count_same_number($ans, $code) - $bulls;
push @query, [$code, $bulls, $cows];
print "$cnt : @$code : bulls = $bulls, cows = $cows\n";
last if $bulls == 4;
$cnt++;
}
}
print "おめでとう\n";
}
solver([9,8,7,6]);
solver([9,4,3,1]);
# 平均質問回数を求める
sub solver1 {
my $ans = shift;
my $cnt = 1;
@query = ();
foreach my $code (@$perm_table) {
if (check_query($code)) {
my $bulls = count_bulls($ans, $code);
my $cows = count_same_number($ans, $code) - $bulls;
push @query, [$code, $bulls, $cows];
last if $bulls == 4;
$cnt++;
}
}
$cnt
}
my $count = 0;
foreach my $code (@$perm_table) {
my $c = solver1($code);
print "@$code\n" if $c == 9;
$count += $c;
}
print $count / @$perm_table, "\n";
改訂 2023 年 3 月 19 日