「Rush Hour」とは？

ご存じない方のために簡単に説明しとく。
6x6マスの盤上に、車に見立てた2マス或いは3マス分のコマを縦横に配置し、1ヵ所しか無い出口から自車を送り出すシンプルなスライディングブロックパズルのこと。

ラッシュアワー (パズル)

各コマは「車」なので、長辺に沿った方向にしか動かせないのがこのパズルのミソ。
一見すると不可能に思えるような配置でも、試行錯誤する内にスルッと抜け出せた時の感覚は何とも形容しがたいモノがある。
考案したのは、世界的なパズルコレクターにしてパズル作家として知られた故・芦ヶ原伸之氏。流石の完成度と言えよう。

遊んでみよう

製品版はThinkFun社から販売されており、国内向けには代理店が取扱っている模様。
スマホ向けのアプリとして「Unblock Me」等のタイトルでも配信されているので、是非遊んでみて欲しい。

ちなみに自分が遊んでみたアプリの第一問はこんな感じ。

まぁハッキリ言っていきなり難しい。最短20手で解けるが、人手でそれを導き出すのは至難。
何回か現れる「ポイント」をクリアしないと、同一局面をグルグルと繰り返して徒に手数が増えるという状況に陥りがちだ。
確かにパズルとしては面白いのだが、最短手数が提示されているが故のストレスに耐えきれなくなり、禁断のソルバー開発へと踏み出すこととなった。

方針を決める

同一局面の繰返しが多いことから、盤面のコマの配置をキーとした辞書式のデータを作成しながら探索を進めることを考える。
難解な問題ほど邪魔になるよう多くのコマが配置される傾向があるが、その分コマ同士が邪魔しあって取り得る状態が少なくなることが見て取れる。
長手数の問題で全探索を行なっても状態数が爆発することは無いのでは、という予測は成り立つ。

次に盤面の状態をどのように保持するかだが、辞書のキーとする際にはシーケンシャルな文字列にする必要がある。
二次元のデータを都度変換するのも面倒なので、始めから文字列の状態で保持しておく方が良さそうだ。境界判定も面倒だしどのみちゴールも設定する必要があるので、6x6に外枠も加えて8x8の盤面を設定し各マスの状態を1文字(char)で表現することを考える。

各コマについては互いを区別すると同時にコマのサイズ・向きの情報も必要となる。それぞれをバラバラに保持しても良いが、管理が面倒だ。
盤面上には、サイズ2の車なら最大18、サイズ3の車なら最大12を配置可能だがコレは実際的ではない。ギッシリ埋めてしまうとコマの動く余地が無くなり単なる障害物と変わらなくなる。サイズ2なら各ラインに2台配置で最大12、サイズ3なら各ラインに1台配置で最大６を想定すれば十分だろう。英字なら26種あるからサイズ毎に予め割り当てを決めておけば十分足りる。大文字・小文字を区別すれば向きの縦横も表せる。

自車は基本横向きサイズ2だが、英字割り当てだけ別枠にしてやれば縦向きやサイズ3を許容しても問題は無いだろう。
サイズ2とサイズ3の割当数は上の考察から概ね2:1が良さそうだ。

とりまとめると以下。

英字の割り当ては サイズ2 を A~Q（17種、うち自車は A）、サイズ3 を R~Z（9種、うち自車は Z）
横向きが 小文字、縦向きが 大文字
外枠は *（アスタリスク）、ゴールは @（アットマーク）

実装例

例によって使い慣れた Perl で書いてみた。

use strict;
use warnings;

# 大文字は上下方向、小文字は左右方向
# 脱出対象は、車長2の場合はa、車長3の場合はz
# a~q(A~Q)は車長2、r~z(R~Z)は車長3
# 壁・障害物は*、ゴールは@
my $problemField = join('',(
  '********',
  '*  rrr *',
  '*   bbC*',
  '*ddEF C*',
  '@GSEFaa*',
  '*GS ** *',
  '**Shhii*',
  '********',
));

# 盤面初期配置からコマ(車)一覧を取得
my %count;
my @cars = grep(!$count{$_}++, grep(/[a-z]/i, split(//, $problemField)));

# 盤面の状態辞書を初期化
my %states = (
  $problemField=>[0, '', ''],
);

my $solved = &solve(0);
&disp($solved);

exit;

sub solve {
  # 最新探索済み手数
  my $lastMove = shift;

  # 現局面を抽出
  my @fields = grep { $states{$_}->[0] == $lastMove } keys %states;
  # 次の手数の局面を生成
  foreach my $field (@fields) {
    # 現局面の状態から最後に移動した車を特定
    my $lastCar = $states{$field}->[2];

    # 車毎に移動
    foreach my $car (@cars) {
      next if ($car eq $lastCar);

      # 探索位置情報（正逆）
      my $rev = $car =~ /[a-z]/ ? -1 : -8;
      my $fwd = $rev * ($car =~ /[a-q]/i ? -2 : -3);
      my $hasSolved;

      # 探索先（正）
      $hasSolved = &move_car($car, $field, $lastMove, 0, $fwd);
      #  解けた？
      if ($hasSolved) {
        return $hasSolved;
      }

      # 探索先（逆）
      $hasSolved = &move_car($car, $field, $lastMove, $fwd + $rev, $rev);
      #  解けた？
      if ($hasSolved) {
        return $hasSolved;
      }
    }
  }

  # 解析継続
  return &solve(++$lastMove);
}

sub move_car {
  my $car = shift;
  my $orgField = shift;
  my $field = $orgField;
  my $lastMove = shift;
  my $offsetFrom = shift;
  my $offsetTo = shift;

  while (1) {
    my $pos = index($field, $car);
    my $posFrom = $pos + $offsetFrom;
    my $posTo = $pos + $offsetTo;
    return if ($posTo < 0 || $posTo > 63);

    my $target = substr($field, $posTo, 1);

    # 移動可能？
    if ($target eq ' ') {
      # 移動
      $field = substr($field, 0, $posFrom) . " " . substr($field, $posFrom + 1);
      $field = substr($field, 0, $posTo) . $car . substr($field, $posTo + 1);
      # 登録済みなら次
      next if (defined $states{$field});
      # 登録
      $states{$field} = [$lastMove + 1, $orgField, $car];
    # ゴール？
    } elsif ($car =~ /[az]/i && $target eq '@') {
      return $field;
    } else {
      last;
    }
  }
  return 0;
}

sub disp {
  my $field = shift;
  my @rows = $field =~ /.{8}/g;
  my $move = $states{$field}->[0];

  print "[$move]\n";
  for my $row (@rows) {
    print "$row\n";
  }
  print "\n";

  if ($move > 0) {
    &disp($states{$field}->[1]);
  }
}

実行結果

解けた状態から問題図まで遡ってるので、一番下から見てね。
20手目の途中まで探索して盤面辞書への登録数は3529件なので、まだまだ余裕かと。
50手超の問題とかもあるらしいので、挑戦してみたくはある。

[20]
********
*GSErrr*
*GSEFbb*
* S Fdd*
@aa    *
*   **C*
**hhiiC*
********

[19]
********
*GSErrr*
*GSEFbb*
* S Fdd*
@    aa*
*   **C*
**hhiiC*
********

[18]
********
*GSErrr*
*GSE bb*
* S Fdd*
@   Faa*
*   **C*
**hhiiC*
********

[17]
********
*G Errr*
*G E bb*
* S Fdd*
@ S Faa*
* S **C*
**hhiiC*
********

[16]
********
*G  rrr*
*G   bb*
* S Fdd*
@ SEFaa*
* SE**C*
**hhiiC*
********

[15]
********
*G  rrr*
*Gbb   *
* S Fdd*
@ SEFaa*
* SE**C*
**hhiiC*
********

[14]
********
*   rrr*
* bb   *
* S Fdd*
@GSEFaa*
*GSE**C*
**hhiiC*
********

[13]
********
*rrr   *
* bb   *
* S Fdd*
@GSEFaa*
*GSE**C*
**hhiiC*
********

[12]
********
*rrrF  *
* bbF  *
* S  dd*
@GSE aa*
*GSE**C*
**hhiiC*
********

[11]
********
*rrrF  *
* bbF  *
* S  dd*
@GSEaa *
*GSE**C*
**hhiiC*
********

[10]
********
*rrrF  *
* bbF  *
* Sdd  *
@GSEaa *
*GSE**C*
**hhiiC*
********

[9]
********
*rrrF  *
* bbF C*
* Sdd C*
@GSEaa *
*GSE** *
**hhii *
********

[8]
********
*rrrF  *
* bbF C*
* Sdd C*
@GSE aa*
*GSE** *
**hhii *
********

[7]
********
*rrrF  *
* bbF C*
* Sdd C*
@GSE aa*
*GSE** *
**hh ii*
********

[6]
********
*rrrF  *
* bbF C*
* Sdd C*
@GSE aa*
*GSE** *
** hhii*
********

[5]
********
*rrrF  *
* bbF C*
*  dd C*
@GSE aa*
*GSE** *
**Shhii*
********

[4]
********
*rrrF  *
* bbF C*
*dd   C*
@GSE aa*
*GSE** *
**Shhii*
********

[3]
********
*rrr   *
* bb  C*
*dd F C*
@GSEFaa*
*GSE** *
**Shhii*
********

[2]
********
*rrr   *
* bb  C*
*ddEF C*
@GSEFaa*
*GS ** *
**Shhii*
********

[1]
********
*  rrr *
* bb  C*
*ddEF C*
@GSEFaa*
*GS ** *
**Shhii*
********

[0]
********
*  rrr *
*   bbC*
*ddEF C*
@GSEFaa*
*GS ** *
**Shhii*
********

(2020-04-14 追記)
なんか長手数問題を研究したドキュメントがあったので、載ってた問題をやらせてみた。

On the Hardness of 6x6 Rush Hour

51手問題だったが、やはり盤面のパターンは3052種ほどしか探索しておらず、当初の予測が正しかったことが裏付けられた。

まとめ

方針決めが上手くハマった
実行時間も1秒未満に収まったので、まぁ良し
探索試行回数はもう少し減らせるかも（高速化に寄与するかは不明）
問題データの入力が面倒
パズルを解く楽しみは完全に失われたw