on_off パズル

著名なパズル作家の芦ケ原伸之氏の著作に、「パズルの宣教師」(ニコリ刊) があります。この本の中では、たくさんのパズルが紹介されています。その中から、178 頁に紹介されている on-off パズルを取り上げます。

本では大きなカードに「電灯の絵」が描かれていますが、画像を作るのは苦手なので省略しました。このパズルは、スタート図上段の no を完成図の on にする最短手順を求めることです。

プログラム

use strict;
my $start = '--noOfF_';
my @goal = ('--OnofF_', '--onOFf_');
my %movelist = ( 0 => [1, 4], 1 => [0, 2, 5], 2 => [1, 3, 6], 3 => [2, 7],
                 4 => [0, 5], 5 => [1, 4, 6], 6 => [2, 5, 7], 7 => [3, 6]);
my @search = ([$start, 8]);       # 8 はダミー
my %board = ($start => undef);

while (@search) {
  my $ref = shift @search;
  my ($board, $p_pos) = @$ref;    #            $p_pos, $pos, $n_pos
  my $pos = index($board, '_');   # 開き升目の 前、    現在、次     の位置
  foreach my $n_pos (@{$movelist{$pos}}) {
    next if $n_pos == $p_pos;
    next if $pos >= 4 and $n_pos <=3 and substr($board, $n_pos, 1) eq '-';
    my $work = $board; my $m_pos = 0;
    if (substr($work, $n_pos, 1) eq '-') {
      if ($n_pos > $pos) { $work =~ s/_--/--_/; $m_pos++; }
      else               { $work =~ s/--_/_--/; $m_pos--; }
    } else {
      substr($work, $pos, 1) = substr($work, $n_pos, 1, '_');
    }
    next if grep /$work/, keys %board;
    if (grep /$work/, @goal) {
      my @result = ($board, $work);
      my $tmp = $board;
      while ($board{$tmp}) {
        $tmp = $board{$tmp};
        unshift @result, $tmp;
      }
      my ($line1, $line2);
      for (my $i = 0; $i <= $#result; $i++) {
        if ($i == $#result) {
          $line1 = $line1 . substr($result[$i], 0, 4);
          $line2 = $line2 . substr($result[$i], 4);
          print "$line1\n$line2\n\n";
        } elsif ($i % 8 == 7) {
          $line1 = $line1 . substr($result[$i], 0, 4) . '  ->';
          $line2 = $line2 . substr($result[$i], 4);
          print "$line1\n$line2\n\n";
          $line1 = $line2 = '';
        } else {
          $line1 = $line1 . substr($result[$i], 0, 4) . '  ->  ';
          $line2 = $line2 . substr($result[$i], 4) . '      ';
        }
      }
      if (@goal == 2) { @goal = grep ! /$work/, @goal; }
      else { exit; }
      print "\n\n";
    } else {
      $board{$work} = $board;
      push @search, [$work, $pos + $m_pos];
    }
  }
}

プログラムの解説

on_off パズルの特徴

今回の on_off パズルは、15 パズルの系統に属します。15 パズルは、4 x 4 の盤面に１から 15 までの整数をランダムに配置して、数字の書かれたカードを空き升目に移動しながら、数字順に並べるものです。いくつか、例を挙げます。

15 パズルでは、ランダムに配置したすべての盤面から完成図 (A) に至るわけではありません。完成図から 14 と 15 を入れ替えた (B) 図は、完成図に至ることのできない不可能な配置です。(A) から生成したすべての盤面 (16! / 2) は、(当たり前だが) 完成図に至ることができます。(B) から生成したすべての盤面 (16! / 2) は、(これも当たり前だが) 完成図に至ることはできません。ここで、(C) 図のように 14 と 15 を * で置き換えてみましょう。１から 15 までをランダムに配置した盤面は、(A) または (B) 図のいずれかに至りますので、(C) 図はすべての配置が可能ということになります。

今回の on_off パズルは、一見して完成が不可能と思われるかもしれません。 15 パズルと同様に、他の４枚のカードを元のままにして、上段の n と o を入れ替えることはできません。しかしながら (C) 図と同じように、o と f がそれぞれ２つずつあります。この同じ文字を入れ替えることで、完成図に至ることができるのです。このことを、一方の文字を大文字にすることで示してみましょう。

スタート図は、２番目の o と f を大文字にしてあります。(a) 図は、n と o を入れ替えただけですので不可能です (尚、図には示していませんが、o と O、f と F の両方を入れ替えたものも不可能)。(b) 図では o と O が入れ替わっており、(c) 図では f と F が入れ替わっています。両方とも、完成図として到達可能です。

カードを１つ動かす

今回のプログラムでは、盤面を単純な文字列として扱います。スタートの盤面は、"--noOfF_" となります。大きなカードは -- で、空き升目は _ で表現します。"--noOfF_" から探索を開始して、"--OnofF_" または "--onOFf_" を完成図として目指します。まず最初に、カードを１つ動かして盤面を１手進める方法から説明します。

プログラムでは、実際のパズルとは少し違った発想が必要です。実際のパズルは、文字の書かれたカードが主役で、空き升目が脇役の存在になります。それに比べてプログラムでは、空き升目こそが主役です。空き升目が移動することにより、そこにあったカードが移動させられて、盤面が変遷するというふうに、考えてください。空き升目は１つしかないので、プログラムを単純化することができます。

プログラムの最初の方に定義してあるハッシュ %movelist は、空き升目が移動用に使うものです。キーが空き升目の現在の位置、値が移動先リストです。

上の図は、それぞれの升目の位置番号になります。大きなカードもハイフン２文字で表しているので、２つの位置番号を持ちます。空き升目を移動するには、まず現在の位置を index を使って取得します。次に、現在の位置からの移動先リストをハッシュ %movelist から取得します。例えばスタート図なら、現在の位置は 7、移動先リストは 3 と 6 ということになります。移動先リストについては、次の点を個別にチェックします。

移動先のチェックを通過したら、空き升目を移動させます。空き升目の移動には、２つのケースがあります。移動先が大きなカードの場合と、通常のカードの場合です。大きなカードの場合は、正規表現を使って移動します。通常のカードの場合には、substr を使って移動します。

空き升目の移動先が大きなカードの場合には、空き升目の位置が２つ移動することになります。次の段階の探索に現在の位置をそのまま渡してしまうと、移動元が含まれないことになってしまいます。そのため $m_pos に値を設定して、現在の位置を修正するようにしています。

substr は部分文字列を返す関数ですが、置換文字列を指定 (substr を左辺値として用いた場合も同じ) すると動作が変わります。置換文字列を指定しないと元の文字列はそのままですが、置換文字列を指定すると部分文字列は削除されて、そこに置換文字列が挿入されます。例えば "--noOfF_" を "--noOf_F" に変更する場合は、右辺の substr は $work を "--noOf__" に変えて F を返します。左辺の substr は、受け取った F を元の空き升目の位置に挿入して、$work を "--noOf_F" に変えます。

盤面データの管理と全体の探索

全体の探索は、while ループを使って幅優先探索を行います。while の条件部の配列 @search には、探索途中の盤面を格納しておきます。最初は、スタート盤面を格納した無名配列 ["--noOfF_", 8] (２番目の要素は空き升目の移動元、スタート盤面ではダミー) だけを格納しています。while では、shift を使って要素を１つ取り出し、その盤面から次の盤面を生成します。生成した盤面は、ハッシュ %board に登録するととともに、配列 @search の末尾に付け加えます。

while で盤面の生成を進めると、同じ配置の盤面が複数の経路で生成されます。そのため生成した盤面 $work は、まず最初に %board に未登録であることを確認します。これによって、同じ配置の盤面は最初に生成されたものだけが登録され、後から生成されたものは捨てられることになります。ハッシュ %board のキーには生成した盤面を登録し、値には生成元の盤面を登録します。３手目までを進めた段階での、%board の内容は次のようになります。

%board の構造はきわめて簡単で、キーと値のリンクリストになっています。このリンクリストをたどると、スタートからの盤面をすべて得ることができます。スタート盤面の値は undef になっているので、それを目印にループを回すことができます。

探索を進めて $work が完成図にマッチしたら、スタート図から完成図のまでのすべての盤面を @result に入れます。そして、整形して @result を表示します。完成図は、o と O を交換したものと f と F を交換したものの２つがあります。プログラムでは、２つの完成図を探索しています。o と O 交換した完成図の最短手数は 44 手で、f と F を交換したときは 48 手になります。プログラムの実行結果は、次のようになります。