「嫉妬深い夫の問題」は「川渡りの問題」と呼ばれる古典的なパズルの一種です。このパズルにはたくさんのバリエーションがありますが、その中で 「農夫と山羊と狼とキャベツの問題」 や「宣教師と人食い人」という危険な名前のパズルが有名です。それでは問題です。
二組の夫婦が川を渡ることになりました。ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも妻が他の男といることを許しません。なお、四人ともボートをこぐことができます。この条件で、二組の夫婦が川を渡る最短手順を考えてください。
この問題は「農夫と山羊と狼とキャベツの問題」よりも簡単です。気分転換や息抜きにちょっと考えてみてください。これでは簡単すぎて面白くないという方は、夫婦を三組に増やしてみてください。ぐっと難しくなりますよ。
それではプログラムを作ります。今回は「幅優先探索」で解いてみましょう。使用するプログラミング言語は Perl です。最初にグローバル変数を定義します。次のリストを見てください。
リスト：グローバル変数の定義
# データの定義
$Ha = 0x01; # 夫 a
$Hb = 0x02; # 夫 b
$Wa = 0x04; # 妻 a
$Wb = 0x08; # 妻 b
$Bo = 0x10; # ボート
$ALL = 0x1f;
$MENS = 0x03;
$SIZE = 5;
# ボートに乗る組み合わせ
@boat_comb = (
$Bo | $Ha | $Wa,
$Bo | $Hb | $Wb,
$Bo | $Ha,
$Bo | $Hb,
$Bo | $Ha | $Hb,
$Bo | $Wa,
$Bo | $Wb,
$Bo | $Wa | $Wb
);
@state = (); # 局面
@prev = (); # 前の局面
@buffer = (); # 生成した局面を格納するバッファ
%check = {}; # 同一局面チェック用ハッシュ
今回のプログラムは二組の夫婦とボートをビットで定義して、局面を整数値で表すことにします。局面は 0 - 4 ビットで右岸の状態、5 - 9 ビットで左岸の状態を表します。ボートに乗る組み合わせは、二人（二組の夫婦、男性二人、女性二人）で乗る場合と一人で乗る場合があるので、合計で 8 通りになります。これを配列 @board で定義します。
配列 @state は局面を格納し、配列 @prev は 1 手前の局面の番号を格納します。配列 @buffer は新しい局面を生成するときに使用するバッファで、%check は同一局面をチェックするためのハッシュです。Perl は文字列と数値の自動変換が行われるので、局面を数値で表しても同一局面のチェックにハッシュを利用することができます。
次は、局面が安全な状態かチェックする関数 check_state を作ります。
リスト：安全な状態かチェックする
sub check_state {
my $s = shift;
my $i, $j;
for( $i = $Wa, $j = $Ha; $i <= $Wb; $i <<= 1, $j <<= 1 ){
if( $s & $i ){
return 0 if !($s & $j) and ($s & $MENS);
}
}
1;
}
関数 check_state は岸が安全な状態かチェックします。引数 $s が岸の状態、変数 $i が女性、変数 $j が男性を表します。$s & $i が真の場合は岸に女性がいる状態です。自分の夫がいっしょにいれば問題ありませんが、自分の夫がいなくて他の男性がいる場合は安全ではありません。これを !($s & $j) and ($s & $MENS) でチェックしています。安全でない場合は 0 を返します。
次は新しい局面を生成する関数 make_new_state を作ります。
リスト：新しい局面を生成する
sub make_new_state {
my $s = shift;
my $left = $s >> $SIZE;
my $right = $s & $ALL;
my $n1, $n2;
# バッファの初期化
@buffer = ();
foreach $p (@boat_comb) {
if( ($left & $p) == $p ){
# 左岸からの移動
$n1 = $left & ~$p;
if( &check_state( $n1 ) ){
$n2 = $right | $p;
if( &check_state( $n2 ) ){
push( @buffer, ($n1 << $SIZE) | $n2 );
}
}
} elsif( ($right & $p) == $p ){
# 右岸からの移動
$n1 = $right & ~$p;
if( &check_state( $n1 ) ){
$n2 = $left | $p;
if( &check_state( $n2 ) ){
push( @buffer, ($n2 << $SIZE) | $n1 );
}
}
}
}
}
関数 make_new_state は局面 $s から新しい局面を生成して @buffer にセットします。最初に、局面 $s から左岸と右岸の状態を取り出して変数 $left と $right にセットします。次に、配列 @boat_comb からボートに乗る組み合わせを取り出して変数 $p にセットします。(岸の状態 & $p) の値が $p と等しければ、その人達をボートに乗せることができます。
それから、新しい局面を生成します。移動元の岸は (岸の状態 & ~$p) で、移動先の岸は (岸の状態 | $p) で新しい状態を求めることができます。これらの状態を関数 check_state でチェックします。安全な状態であれば、((左岸の状態 << $SIZE) | 右岸の状態) を計算して @buffer にセットします。これで新しい局面を全て生成することができます。
最後に、幅優先探索でパズルを解く関数 solve を作ります。
リスト：幅優先探索
sub solve {
my $front = 0;
my $rear = 1;
$state[0] = $ALL << $SIZE;
$prev[0] = -1;
while( $front < $rear ){
&make_new_state( $state[$front] );
foreach $ns (@buffer) {
$state[$rear] = $ns;
$prev[$rear] = $front;
if( $ns == $ALL ){
&print_answer( $rear );
print "総数 $rear\n";
return;
}
if( !$check{$ns} ){
$rear++;
$check{$ns} = 1;
}
}
$front++;
}
}
最初に、@state と @prev に初期値をセットします。このプログラムでは左岸から右岸へ渡ることにします。$front と $rear はキューを管理する変数です。$front の位置にあるデータを取り出して新しい状態を生成し、$rear の位置に書き込みます。$front と $rear が等しい値になると、キューは空の状態になるので探索を終了します。この場合は、解を見つけることができなかったということになります。
次に、make_new_state で新しい局面を生成して、@buffer から新しい局面 $ns を取り出して $state[$rear] にセットします。$ns == $ALL であれば解けたので、関数 print_answer で手順を表示して終了します。そうでなければ、ハッシュ %check で同一局面があるかチェックします。同一局面がなければ、新しい局面 $ns をキューとハッシュに登録します。
あとは特に難しいところはないでしょう。詳細は プログラムリスト１ をお読みくださいませ。
それでは実行結果を示します。
0: [Ha Hb Wa Wb Boat ] [] 1: [Hb Wb ] [Ha Wa Boat ] 2: [Ha Hb Wb Boat ] [Wa ] 3: [Wb ] [Ha Hb Wa Boat ] 4: [Hb Wb Boat ] [Ha Wa ] 5: [] [Ha Hb Wa Wb Boat ]
5 手で解くことができました。実はこの問題、プログラムを作らなくても簡単に解くことができます。最初にボートに乗るとき、1 人では意味が無いので必ず 2 人で乗ることになります。まず最初（1 回目）に Ha と Wa が渡ることにします。すると、2 回目は Ha が戻ることになります。Wa が戻ると左岸で Hb と一緒になるからです。3 回目は Ha と Hb が渡ります。Hb と Wb が渡ると右岸で Wa と Hb が一緒になってしまいます。この段階で左岸には Wb が残っているので、4 回目で Hb が戻って、5 回目で一緒に渡ればいいわけです。
ちなみに、このパズルは条件を「夫婦でない男女が二人きりになってはいけない」に変更すると、最初に Ha と Hb が渡っても解くことができます。
0: [Ha Wa Hb Wb Boat] [] 1: [Wa Wb] [Ha Hb Boat] 2: [Ha Wa Wb Boat] [Hb] 3: [Wb] [Ha Wa Hb Boat] 4: [Hb Wb Boat] [Ha Wa] 5: [Ha Wa Hb Wb Boat]
最初に Ha と Hb が渡って Ha が戻ってきても、2: のように左岸では Wa が居るので、Ha と Wb の 2 人きりにはなりません。この場合も 5 回で解くことができます。
実は、条件が何もない場合でも、最短手数は 5 回かかります。ボートには 2 人しか乗ることができないので、1 往復で 1 人しか運ぶことができません。2 往復で 2 人を送り込み、最後に 2 人が渡る手順が最短手数となります。3 組の夫婦の場合、何も条件がないと 4 往復＋ 1 回の 9 回が最短手数になりますが、残念ながら 9 回で解くことはできません。最短手数が何回になるか、息抜きや気分転換に考えてみてください。
#
# h2.pl : 嫉妬深い夫の問題（幅優先探索）
#
# Copyright (C) 2005 Makoto Hiroi
#
# データの定義
$Ha = 0x01;
$Hb = 0x02;
$Wa = 0x04;
$Wb = 0x08;
$Bo = 0x10;
$ALL = 0x1f;
$MENS = 0x03;
$SIZE = 5;
# ボートに乗る組み合わせ
@boat_comb = (
$Bo | $Ha | $Wa,
$Bo | $Hb | $Wb,
$Bo | $Ha,
$Bo | $Hb,
$Bo | $Ha | $Hb,
$Bo | $Wa,
$Bo | $Wb,
$Bo | $Wa | $Wb
);
@symbol = ('Ha', 'Hb', 'Wa', 'Wb', 'Boat');
@state = (); # 局面
@prev = (); # 前の局面
@buffer = (); # 生成した局面を格納するバッファ
%check = {}; # 同一局面チェック用ハッシュ
# 安全な状態かチェックする
sub check_state {
my $s = shift;
my $i, $j;
for( $i = $Wa, $j = $Ha; $i <= $Wb; $i <<= 1, $j <<= 1 ){
if( $s & $i ){
return 0 if !($s & $j) and ($s & $MENS);
}
}
1;
}
# 新しい状態を生成して @buffer にセット
sub make_new_state {
my $s = shift;
my $left = $s >> $SIZE;
my $right = $s & $ALL;
my $n1, $n2;
# バッファの初期化
@buffer = ();
foreach $p (@boat_comb) {
if( ($left & $p) == $p ){
# 左岸からの移動
$n1 = $left & ~$p;
if( &check_state( $n1 ) ){
$n2 = $right | $p;
if( &check_state( $n2 ) ){
push( @buffer, ($n1 << $SIZE) | $n2 );
}
}
} elsif( ($right & $p) == $p ){
# 右岸からの移動
$n1 = $right & ~$p;
if( &check_state( $n1 ) ){
$n2 = $left | $p;
if( &check_state( $n2 ) ){
push( @buffer, ($n2 << $SIZE) | $n1 );
}
}
}
}
}
# 局面の表示
sub print_state {
my $s = shift;
my $i, $j;
print '[';
for( $i = 0, $j = $Ha; $i < $SIZE; $i++, $j <<= 1 ){
printf( "%s ", $symbol[$i] ) if $s & $j;
}
print ']';
}
sub print_answer {
my $n = shift;
print_answer( $prev[$n] ) if $n > 0;
&print_state( $state[$n] >> $SIZE );
&print_state( $state[$n] );
print "\n";
}
# 幅優先探索で解を求める
sub solve {
my $front = 0;
my $rear = 1;
$state[0] = $ALL << $SIZE;
$prev[0] = -1;
while( $front < $rear ){
&make_new_state( $state[$front] );
foreach $ns (@buffer) {
$state[$rear] = $ns;
$prev[$rear] = $front;
if( $ns == $ALL ){
&print_answer( $rear );
print "総数 $rear\n";
return;
}
if( !$check{$ns} ){
$rear++;
$check{$ns} = 1;
}
}
$front++;
}
}
# 実行
&solve;
今度は夫婦を三組に増やしてみましょう。
三組の夫婦が川を渡ることになりました。ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも妻が他の男といることを許しません。なお、六人ともボートをこぐことができます。この条件で、三組の夫婦が川を渡る最短手順を考えてください。
それではプログラムを作りましょう。「二組の嫉妬深い夫の問題」のプログラムを改造すると簡単です。最初にデータを変更します。次のリストを見てください。
リスト：データの定義 # データの定義 $Ha = 0x01; $Hb = 0x02; $Hc = 0x04; $Wa = 0x08; $Wb = 0x10; $Wc = 0x20; $Bo = 0x40; $ALL = 0x7f; $MENS = 0x07; $SIZE = 7;
リスト：ボートに乗る組み合わせ
# 手順表示用
@symbol = ('Ha', 'Hb', 'Hc', 'Wa', 'Wb', 'Wc', 'Boat');
# ボートに乗る組み合わせ
@boat_comb = (
$Bo | $Ha | $Wa, $Bo | $Hb | $Wb, $Bo | $Hc | $Wc,
$Bo | $Ha, $Bo | $Hb, $Bo | $Hc,
$Bo | $Ha | $Hb, $Bo | $Ha | $Hc, $Bo | $Hb | $Hc,
$Bo | $Wa, $Bo | $Wb, $Bo | $Wc,
$Bo | $Wa | $Wb, $Bo | $Wa | $Wc, $Bo | $Wb | $Wc
);
三組の夫婦を (Ha, Wa), (Hb, Wb), (Hc, Wc) とし、ビットで定義します。ボートに乗る組み合わせは全部で 15 通りになります。あとは、関数 check_state 修正するだけです。
リスト：安全な状態かチェックする
sub check_state {
my $s = shift;
my $i, $j;
for( $i = $Wa, $j = $Ha; $i <= $Wc; $i <<= 1, $j <<= 1 ){
if( $s & $i ){
return 0 if !($s & $j) and ($s & $MENS);
}
}
1;
}
check_state は 3 人の女性 (Wa, Wb, Wc) が安全な状態かチェックするように修正します。具体的には $i <= $Wb を $i <= $Wc に変更するだけです。プログラムの修正はこれだけです。
それでは実行結果を示します。最短手数は 11 手で、次のようになります。
0: [Ha Hb Hc Wa Wb Wc Boat ] [] 1: [Hb Hc Wb Wc ] [Ha Wa Boat ] 2: [Ha Hb Hc Wb Wc Boat ] [Wa ] 3: [Ha Hb Hc ] [Wa Wb Wc Boat ] 4: [Ha Hb Hc Wa Boat ] [Wb Wc ] 5: [Ha Wa ] [Hb Hc Wb Wc Boat ] 6: [Ha Hb Wa Wb Boat ] [Hc Wc ] 7: [Wa Wb ] [Ha Hb Hc Wc Boat ] 8: [Wa Wb Wc Boat ] [Ha Hb Hc ] 9: [Wc ] [Ha Hb Hc Wa Wb Boat ] 10: [Hc Wc Boat ] [Ha Hb Wa Wb ] 11: [] [Ha Hb Hc Wa Wb Wc Boat ]
ちなみに、この問題は「ボートをこぐことができる女性が 1 人しかいない」という条件でも解くことができます。ボートをこぐことができる女性を Wa とすると、最短手順は次のようになります。
0: [Ha Hb Hc Wa Wb Wc Boat ] [] 1: [Ha Hc Wa Wc ] [Hb Wb Boat ] 2: [Ha Hb Hc Wa Wc Boat ] [Wb ] 3: [Ha Hb Hc ] [Wa Wb Wc Boat ] 4: [Ha Hb Hc Wa Boat ] [Wb Wc ] 5: [Ha Wa ] [Hb Hc Wb Wc Boat ] 6: [Ha Hb Wa Wb Boat ] [Hc Wc ] 7: [Hb Wb ] [Ha Hc Wa Wc Boat ] 8: [Hb Hc Wb Wc Boat ] [Ha Wa ] 9: [Wb Wc ] [Ha Hb Hc Wa Boat ] 10: [Wa Wb Wc Boat ] [Ha Hb Hc ] 11: [Wc ] [Ha Hb Hc Wa Wb Boat ] 12: [Hc Wc Boat ] [Ha Hb Wa Wb ] 13: [] [Ha Hb Hc Wa Wb Wc Boat ]
最短手数は 13 手になります。なお、三組の嫉妬深い夫の問題は xyzzy Lisp Programming パズルに挑戦！ と 続・嫉妬深い夫の問題 で取り上げたことがあります。Lisp に興味のある方は読んでみてください。
ところで、夫婦が四組に増えると、二人乗りのボートで川を渡ることはできません。三人乗りのボートにするか、川の中に小島がひとつあれば二人乗りのボートでも渡ることができます。次は四組の嫉妬深い夫の問題に挑戦してみましょう。
それでは、夫婦を四組に増やします。
四組の夫婦が川を渡ることになりました。川の中には小島がひとつあり、何人でもそこに立つことができます。ただし、ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも小島でも、妻が他の男といることを許しません。なお、八人ともボートをこぐことができます。この条件で、四組の夫婦が川を渡る最短手順を考えてください。
この問題は川の中にある小島を利用しないと解くことができません。三組の夫婦であれば、小島を利用しなくても 11 回で解くことができます。すぐに思い付く手順は、最初に一組の夫婦を小島に移し、それから三組の夫婦を対岸に渡し、最後に小島にいる夫婦をつれてくる、というものです。この手順では岸と小島の往復に 4 回ずつかかるので、手数は合計で 19 回になります。手順の一例を示します。
左岸 小島 右岸
0 : [Ha Hb Hc Hd Wa Wb Wc Wd Boat] [] []
1 : [Ha Hb Hc Wa Wb Wc] [Hd Wd Boat] []
2 : [Ha Hb Hc Hd Wa Wb Wc Boat] [Wd] []
3 : [Hb Hc Hd Wb Wc] [Wd] [Ha Wa Boat]
4 : [Ha Hb Hc Hd Wb Wc Boat] [Wd] [Wa]
5 : [Hb Hc Wb Wc] [Ha Hd Wd Boat] [Wa]
6 : [Ha Hb Hc Wb Wc Boat] [Hd Wd] [Wa]
7 : [Ha Hb Hc] [Hd Wd] [Wa Wb Wc Boat]
8 : [Ha Hb Hc Wa Boat] [Hd Wd] [Wb Wc]
9 : [Ha Wa] [Hd Wd] [Hb Hc Wb Wc Boat]
10 : [Ha Hc Wa Wc Boat] [Hd Wd] [Hb Wb]
11 : [Wa Wc] [Hd Wd] [Ha Hb Hc Wb Boat]
12 : [Wa Wb Wc Boat] [Hd Wd] [Ha Hb Hc Boat]
13 : [Wa] [Hd Wd] [Ha Hb Hc Wb Wc Boat]
14 : [Wa] [Ha Hd Wd Boat] [Hb Hc Wb Wc]
15 : [Wa] [Wd] [Ha Hb Hc Hd Wb Wc Boat]
16 : [Wa] [Hd Wd Boat ] [Ha Hb Hc Wb Wc]
17 : [Wa] [] [Ha Hb Hc Hd Wb Wc Wd Boat]
18 : [Ha Wa Boat] [] [Hb Hc Hd Wb Wc Wd]
19 : [] [] [Ha Hb Hc Hd Wa Wb Wc Wd Boat]
ところが、これよりも短い手順が存在します。プログラムを作って確かめてみましょう。
最初にデータを定義します。次のリストを見てください。
リスト：データの定義 # データの定義 $Ha = 0x01; $Hb = 0x02; $Hc = 0x04; $Hd = 0x08; $Wa = 0x10; $Wb = 0x20; $Wc = 0x40; $Wd = 0x80; $Bo = 0x100; $ALL = 0x1ff; $MENS = 0x0f; $SIZE = 9;
リスト：ボートに乗る組み合わせ
# 手順表示用
@symbol = ('Ha', 'Hb', 'Hc', 'Wa', 'Wb', 'Wc', 'Boat');
@boat_comb = (
$Bo | $Ha | $Wa, $Bo | $Hb | $Wb, $Bo | $Hc | $Wc, $Bo | $Hd | $Wd,
$Bo | $Ha, $Bo | $Hb, $Bo | $Hc, $Bo | $Hd,
$Bo | $Ha | $Hb, $Bo | $Ha | $Hc, $Bo | $Ha | $Hd, $Bo | $Hb | $Hc,
$Bo | $Hb | $Hd, $Bo | $Hc | $Hd,
$Bo | $Wa, $Bo | $Wb, $Bo | $Wc, $Bo | $Wd,
$Bo | $Wa | $Wb, $Bo | $Wa | $Wc, $Bo | $Wa | $Wd, $Bo | $Wb | $Wc,
$Bo | $Wb | $Wd, $Bo | $Wc | $Wd,
);
四組の夫婦を (Ha, Wa), (Hb, Wb), (Hc, Wc), (Hd, Wd) とし、ビットで定義します。ボートに乗る組み合わせは全部で 24 通りになります。状態は $SIZE (9) ビットで表すことができるので、左岸の状態を 18 - 26 ビットで、小島の状態を 9 - 17 ビットで、右岸の状態を 0 - 8 ビットで表すことにします。
次は関数 make_new_state を修正します。
リスト：新しい局面を生成する
sub make_new_state {
my $s = shift;
my $left = $s >> ($SIZE * 2);
my $middle = ($s >> $SIZE) & $ALL;
my $right = $s & $ALL;
my $n1, $n2;
@buffer = ();
foreach $p (@boat_comb) {
if( ($left & $p) == $p ){
# 左岸からの移動
$n1 = $left & ~$p;
if( &check_state( $n1 ) ){
$n2 = $middle | $p;
if( &check_state( $n2 ) ){
&set_new_state( $n1, $n2, $right );
}
$n2 = $right | $p;
if( &check_state( $n2 ) ){
&set_new_state( $n1, $middle, $n2 );
}
}
} elsif( ($middle & $p) == $p ){
# 小島からの移動
$n1 = $middle & ~$p;
if( &check_state( $n1 ) ){
$n2 = $left | $p;
if( &check_state( $n2 ) ){
&set_new_state( $n2, $n1, $right );
}
$n2 = $right | $p;
if( &check_state( $n2 ) ){
&set_new_state( $left, $n1, $n2 );
}
}
} elsif( ($right & $p) == $p ){
# 右岸からの移動
$n1 = $right & ~$p;
if( &check_state( $n1 ) ){
$n2 = $left | $p;
if( &check_state( $n2 ) ){
&set_new_state( $n2, $middle, $n1 );
}
$n2 = $middle | $p;
if( &check_state( $n2 ) ){
&set_new_state( $left, $n2, $n1 );
}
}
}
}
}
リストは長くなりますが、処理内容は難しくありません。たとえば、左岸から移動する場合、小島へ行く場合と右岸へ行く場合の 2 通りがあります。したがって、生成される局面は最大で 48 通りになります。あとは、今までのように新しい状態を生成して check_state でチェックして、@buffer にセットするだけです。関数 set_new_state は引数から局面を生成して @buffer にセットします。
あとは特に難しいところはないでしょう。詳細は プログラムリスト２ をお読みくださいませ。
それでは実行結果を示します。最短手順は 16 手で、次のようになります。
左岸 小島 右岸
0: [Ha Hb Hc Hd Wa Wb Wc Wd Boat] [] []
1: [Hb Hc Hd Wb Wc Wd] [Ha Wa Boat] []
2: [Ha Hb Hc Hd Wb Wc Wd Boat] [Wa] []
3: [Ha Hc Hd Wc Wd] [Wa] [Hb Wb Boat]
4: [Ha Hb Hc Hd Wc Wd Boat] [Wa] [Wb]
5: [Hc Hd Wc Wd] [Wa] [Ha Hb Wb Boat]
6: [Ha Hc Hd Wc Wd Boat] [Wa] [Hb Wb]
7: [Ha Hd Wd] [Wa] [Hb Hc Wb Wc Boat]
8: [Ha Hd Wd] [Wa Wb Boat] [Hb Hc Wc]
9: [Ha Hd Wa Wd Boat] [Wb] [Hb Hc Wc]
10: [Hd Wd] [Wb] [Ha Hb Hc Wa Wc Boat]
11: [Hb Hd Wd Boat] [Wb] [Ha Hc Wa Wc]
12: [Wd] [Wb] [Ha Hb Hc Hd Wa Wc Boat]
13: [Wd] [Hb Wb Boat] [Ha Hc Hd Wa Wc]
14: [Wd] [] [Ha Hb Hc Hd Wa Wb Wc Boat]
15: [Hd Wd Boat] [] [Ha Hb Hc Wa Wb Wc]
16: [] [] [Ha Hb Hc Hd Wa Wb Wc Wd Boat]
かなり複雑な手順になりましたね。7, 8, 9 手目で、右岸から小島を経由して左岸へ移動するところがポイントでしょう。一組の夫婦を小島に退避するよりも、女性を一人だけ小島に退避させた方が短い手数になるとはちょっと驚きました。
#
# h4.pl : 嫉妬深い夫の問題（幅優先探索）
#
# Copyright (C) 2005 Makoto Hiroi
#
# データの定義
$Ha = 0x01;
$Hb = 0x02;
$Hc = 0x04;
$Hd = 0x08;
$Wa = 0x10;
$Wb = 0x20;
$Wc = 0x40;
$Wd = 0x80;
$Bo = 0x100;
$ALL = 0x1ff;
$MENS = 0x0f;
$SIZE = 9;
# ボートに乗る組み合わせ
@boat_comb = (
$Bo | $Ha | $Wa,
$Bo | $Hb | $Wb,
$Bo | $Hc | $Wc,
$Bo | $Hd | $Wd,
$Bo | $Ha,
$Bo | $Hb,
$Bo | $Hc,
$Bo | $Hd,
$Bo | $Ha | $Hb,
$Bo | $Ha | $Hc,
$Bo | $Ha | $Hd,
$Bo | $Hb | $Hc,
$Bo | $Hb | $Hd,
$Bo | $Hc | $Hd,
$Bo | $Wa,
$Bo | $Wb,
$Bo | $Wc,
$Bo | $Wd,
$Bo | $Wa | $Wb,
$Bo | $Wa | $Wc,
$Bo | $Wa | $Wd,
$Bo | $Wb | $Wc,
$Bo | $Wb | $Wd,
$Bo | $Wc | $Wd,
);
@symbol = ('Ha', 'Hb', 'Hc', 'Hd', 'Wa', 'Wb', 'Wc', 'Wd', 'Boat');
@state = (); # 局面
@prev = (); # 前の局面
@buffer = (); # 生成した局面を格納するバッファ
%check = {}; # 同一局面チェック用ハッシュ
# 安全な状態かチェックする
sub check_state {
my $s = shift;
my $i, $j;
for( $i = $Wa, $j = $Ha; $i <= $Wd; $i <<= 1, $j <<= 1 ){
if( $s & $i ){
return 0 if !($s & $j) and ($s & $MENS);
}
}
1;
}
# 新しい state を @buffer にセット
sub set_new_state {
my ($l, $m, $r) = @_;
push( @buffer, ($l << ($SIZE * 2)) | ($m << $SIZE) | $r );
}
# 新しい状態を生成して @buffer にセット
sub make_new_state {
my $s = shift;
my $left = $s >> ($SIZE * 2);
my $middle = ($s >> $SIZE) & $ALL;
my $right = $s & $ALL;
my $n1, $n2;
# バッファの初期化
@buffer = ();
foreach $p (@boat_comb) {
if( ($left & $p) == $p ){
# 左岸からの移動
$n1 = $left & ~$p;
if( &check_state( $n1 ) ){
$n2 = $middle | $p;
if( &check_state( $n2 ) ){
&set_new_state( $n1, $n2, $right );
}
$n2 = $right | $p;
if( &check_state( $n2 ) ){
&set_new_state( $n1, $middle, $n2 );
}
}
} elsif( ($middle & $p) == $p ){
# 小島からの移動
$n1 = $middle & ~$p;
if( &check_state( $n1 ) ){
$n2 = $left | $p;
if( &check_state( $n2 ) ){
&set_new_state( $n2, $n1, $right );
}
$n2 = $right | $p;
if( &check_state( $n2 ) ){
&set_new_state( $left, $n1, $n2 );
}
}
} elsif( ($right & $p) == $p ){
# 右岸からの移動
$n1 = $right & ~$p;
if( &check_state( $n1 ) ){
$n2 = $left | $p;
if( &check_state( $n2 ) ){
&set_new_state( $n2, $middle, $n1 );
}
$n2 = $middle | $p;
if( &check_state( $n2 ) ){
&set_new_state( $left, $n2, $n1 );
}
}
}
}
}
# 局面の表示
sub print_state {
my $s = shift;
my $i, $j;
print '[';
for( $i = 0, $j = $Ha; $i < $SIZE; $i++, $j <<= 1 ){
printf( "%s ", $symbol[$i] ) if $s & $j;
}
print ']';
}
sub print_answer {
my $n = shift;
print_answer( $prev[$n] ) if $n > 0;
&print_state( $state[$n] >> ($SIZE * 2) );
&print_state( $state[$n] >> $SIZE );
&print_state( $state[$n] );
print "\n";
}
# 幅優先探索で解を求める
sub solve {
my $front = 0;
my $rear = 1;
$state[0] = $ALL << ($SIZE * 2);
$prev[0] = -1;
while( $front < $rear ){
&make_new_state( $state[$front] );
foreach $ns (@buffer) {
$state[$rear] = $ns;
$prev[$rear] = $front;
if( $ns == $ALL ){
&print_answer( $rear );
print "総数 $rear\n";
return;
}
if( !$check{$ns} ){
$rear++;
$check{$ns} = 1;
}
}
$front++;
}
}
# 実行
&solve;