フリップ・イット

今回取り上げるパズルは、フリップ・イットです。オリジナルとは少し異なっていますが、ルールは次の通りです。

３つのスタート図は、JavaScript が有効で version 1.1 以降あれば、実際に動かして遊べるようになっています。 (空き升目とそのとなりの升目を除く) 升目をマウスでクリックすると、石の升目は空き升目に移動し、中間の升目は反転します。パズルの右に、次節の解法プログラムで求めた最短手数を表示しています。解法プログラムを見る前に挑戦してみてください。

プログラム

use strict;
my $n = 5;
my (%head, %tail, @result);

foreach (0 .. ($n % 2 ? int($n / 2) : $n / 2 - 1)) {
  my $start = "B" x $n;
  substr($start, $_, 1, "_");
  (my $goal = $start) =~ s/B/W/g;
  my @board = ([$start, $n]);
  %head = ($start => 0);
  %tail = ($goal => 0);

OUT: while (@board) {
    my ($board, $p_pos) = @{shift(@board)};
    (my $r_board = $board) =~ tr/BW/WB/;
    my $c_pos = index($board, '_');
    my @n_pos = grep { $_ < ($c_pos - 1) or $_ > ($c_pos + 1) } 0 .. ($n - 1);
    foreach my $n_pos (@n_pos) {
      next if $p_pos == $n_pos;
      my $temp = $board;
      my $i = $c_pos < $n_pos ? $c_pos + 1 : $n_pos + 1;
      my $len = abs($c_pos - $n_pos) - 1;
      my $rev = substr($temp, $i, $len);
      $rev =~ y/BW/WB/;
      substr($temp, $i, $len, $rev);
      substr($temp, $c_pos, 1) = substr($temp, $n_pos, 1, "_");
      if (grep /$temp/, keys %tail) {
        push @result, [gather($board), gather($temp)];
        last OUT;
      } else {
        next if grep /$temp/, keys %head;
        $head{$temp} = $board;
        push @board, [$temp, $c_pos];
        $temp =~ tr/BW/WB/;
        if (grep /$temp/, keys %head) {
          push @result, [gather($temp), gather($r_board)];
          last OUT;
        } else {
          $tail{$temp} = $r_board;
        }
      }
    }
  }
}

sub gather {
  my $board = shift; my @work;
  if (grep /$board/, keys %head) {
    while ($board) {
      unshift @work, $board;
      $board = $head{$board};
    }
  } else {
    while ($board) {
      push @work, $board;
      $board = $tail{$board};
    }
  }
  return @work;
}

my $max = 0;
foreach (@result) {
  $max = @$_ if $max < @$_;
}

foreach my $i (0 .. ($max - 1)) {
  my $line = "";
  foreach my $j (0 .. $#result) {
    if ($i < @{$result[$j]}) {
      $line .= "    ${$result[$j]}[$i]";
      $line =~ s/    // if $j == 0;
    } else {
      $line = $line . "    " . " " x $n;
      $line =~ s/    // if $j == 0;
    }
  }
  print "$line\n";
}

プログラムの解説

今回のパズルでは、盤面を単純な文字列で扱います。黒石を 'B' で、白石を 'W' で、空き升目を '_' で表します。盤面は、'_BBBB' や 'BW_BB' のような文字列となります。プログラムの最初で指定している $n は、盤面の大きさです。石の数は、$n よりも１つ少なくなります。正解があるのは、盤面の大きさが５、石の数が４以上です。

今回のパズルは、ゴールの盤面が決まっています。通常はスタートの盤面からパズルを解きますが、ゴールの盤面が決まっている場合は、ゴールの盤面からスタートの盤面を目指しても同様に解くこともできます。しかし、単にゴールから探索して解を得たとしても、スタートから探索するのと同じで意味がありません。双方向から探索して、途中で繋ぎ合わせることができたらどうでしょうか。まずは、スタートとゴールの盤面から２手目までを進めた盤面を見てみましょう。

スタート図

スタートから１手

スタートから２手

●

--->

●

○

●

--->

●

○

●

○

--->

●

○

●

--->

●

○

●

--->

●

○

--->

●

○

●

○

--->

●

○

ゴール図

ゴールから１手

ゴールから２手

○

--->

○

●

○

--->

○

●

○

●

--->

○

●

○

--->

○

●

○

--->

○

●

--->

○

●

○

●

--->

○

●

スタート図から１手進めると、３つの盤面を生成することができます。１手目の盤面からは、それぞれ１つから２つの２手目の盤面を生成することができます。ゴールからの盤面の生成も同様です。ゴールから生成した盤面をよく見てみると、スタート図から生成した盤面の ● と ○ を入れ替えたものと同じであることがわかります。すなわち、スタート図から得られた盤面の ● と ○ を入れ替えれば、ゴール図からの盤面を生成したことになります。

今回のパズルでは、盤面データの管理は単純なハッシュを利用しています。スター図からの盤面は %head に、ゴール図からの盤面は %tail に格納します。ハッシュのキーには生成した盤面を、値には生成元の盤面を格納しておきます。%tail への登録は、単に %head で生成したものを B と W を入れ替えるだけで済みます。２手進めたときのハッシュは、次のようになります。

２つのハッシュでは、生成した盤面から最初の盤面までたどるのほ容易です。 %head ハッシュから新しい盤面を生成したら、まず %tail ハッシュのキーを調べます。生成した盤面が %tail ハッシュのキーにある場合は、２つのハッシュの経路を繋ぎ合わせれば、正解を得ることができます。%tail キーに生成した盤面がない場合は、%head ハッシュのキーを調べます。生成した盤面がすでにハッシュのキーに登録してあるときには、短い手数かまたは同じ手数で生成済みなので登録をスキップします。%tail への登録は、単に B と W を入れ替えるだけです。

ここで、現在の盤面から次の盤面を生成する仕組みを説明しましょう。以下は、その部分のコードです。

次の盤面を生成するには、２つの作業が必要です。１つ目は、中間の石を反転することです。盤面文字列全体の石を反転するのは簡単ですが、一部だけ反転するのには少し工夫が必要です。ここでは盤面文字列から反転する部分文字列を取り出して、部分文字列を反転して、元の盤面文字列を置き換える、という方法で行っています。２つ目は、現在の空き升目と次の移動先の石とを入れ替えることです。引数４つの substr と左辺値としての substr を使用すると、一度に入れ替えることができます。

今回の探索では、while ループを使用しています。条件部は、探索途中のボードを格納した配列 @board です。探索の開始時には、スタートの盤面だけが入っています。探索を開始すると、スタートの盤面を @board から取り出して、１手目の盤面をすべて生成して @board に格納します。２手目以降も同じような方法で生成して、最短手順の解が見つかったら、そこで while ループを終了させます。

以上が今回のパズルの探索の仕組みです。今回のパズルを実行すると、以下のような結果になります。