立体ペントミノ・ソルバー

はじめに

この記事

で紹介したのは平面でのペントミノ・ソルバーでした。
ピースの要素を立方体にすることで、3x4x5 のような立体ペントミノが得られるので、本記事では立体ペントミノにも対応したソルバーを示します。

ソースコード

Ruby です。

実行

$ ruby solver-3D.rb  --size 3x4x5

3x4x5 だけでなく 5x6x2 や 3x10x2 も指定できます。
Wikipedia に示されているようにそれぞれ 3,940、260, 12通りの解を表示します。
サイズを指定しなければ２次元（6x10）の解を表示します。

立体の表示

キャラクターベースで３次元表示は難しいので、下図のように表示しています。画面垂直方向に５段積み重なっている様子を脳内でイメージしてください。

+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+   +---+-------+
| I | X | L |   | i | Y | l |   | i | Z | F |   | i | z | n |   | i | P     |
+---+   +---+   +---+   |   |   +---+---+   |   +---+   |   |   +---+       |
|           |   |       |   |   |           |   | t |   |   |   | V |       |
+---+   +---+   +---+   |   |   +---+   +---+   |   |   |   |   |   +---+   |
| U |   |   |   | T |   |   |   | t |   | N |   |   |   |   |   |   | z |   |
|   +---+   |   +---+   |   |   +---+---+   |   |   +---+---+   |   +---+---+
|           |   | W |   |   |   | w     |   |   |   | w     |   |           |
+-----------+   +---+---+---+   +-------+---+   +---+-------+   +-----------+

アルゴリズム

ソースコードを参照ください

考え方は、先の記事：「ペントミノ・ソルバーのアルゴリズム」 と基本的に同じです。以下に高速化のために考慮＆工夫したことを示します。

ビット演算による高速化

盤面（平面、直方体）を配列で表すのではなく、60(or 64)bit のビット列で表すことで、ピースの place や check がビット演算一発で行えます。
盤面上の「空白を探す」という処理も、ビットパターンでは 0 のビット位置を探すことでループを回すことなく計算できます。CやC++であればCPUのビット演算命令を利用できさらに高速に計算できます。

ビット演算による高速化

  def find_space()
    # lowest zero-bit position
    return BITPOS[  ~@bits & ( @bits + 1 ) ]
  end

  def unplace( fig )
    @bits &= ~fig.bits
  end

  def place( fig )
    @bits |= fig.bits
  end

  def check( fig )
    (@bits & fig.bits ) == 0
  end

全ての位置でのピースパターンの準備

各ピースが取り得る位置・姿勢は数十～数百通りありますが無限ではありません。それらを予めビットパターンで持っておくことで、配置の度にピース座標列を計算する必要がなくなります。

全ピースパターンの準備

    # grid上 位置毎に配置可能な全ての fig を計算
    @figs_at = Array.new( @@grid.size ) { |bp|
      ox, oy, oz = @@grid.bp2pt[bp]
      @org_pts.map{ |pts|
        pts.map{ |x,y,z| [ x + ox, y + oy, z + oz ] }
      }.select{ |pts|
        # Grid に収まり、穴に干渉しない場合のみ
        pts.all?{ |pt| @@grid.is_inside?( *pt ) } &&
          ( @@grid.pts2bit( pts ) & @@grid.bits ) == 0
      }.map{ |pts|
        Fig.new( self, pts )
      }
    }

対称解の排除

対称性を考慮しないと、平面ペントミノでは４倍、立体では８倍の解がみつかってしまいます。
この対策として、先の記事では 'F' の姿勢を制限しました。平面のペントミノであればこれでいいのですが立体では単純には行きません。

そこで立体では「ピースの位置を制限する」ことで対称解を排除しています。
具体的には、盤面の対称性がなくなるまで anchor piece を配置し、その後残りのピースについて全ての配置を試す、ということをしています。

平面：6x10 の場合であれば、'X' の位置を盤面の左上（1/4の領域）に制限することになります。6x10 は簡単な場合であり、anchor piece は 'X' だけで済みます。
5x12 の場合だと 'X' がちょうど左右中央に配置される場合があり、このとき盤面としては左右の対称性が残ります。これを排除するために次の 'F' の配置を左側だけに制限します。なのでこの場合は anchor piece は 'X' と 'F' になります。

枝狩り：閉塞領域のチェック

平面だけの場合だけですが、以下のようなチェックを行っています。

下の図では、'U' の配置は可能ですが、その後が続かないことは明らかです。

+---------------+-------+
| .   .   .   . | U     |
|               |   +---+
| .   .   .   . |   | . |
|               |   +---+
| .   .   .   . |       |
|               +-------+
| .   .   .   .   .   . |
|

下図も後が続きません。連続する空白が５で割り切れないからです。

+-----------+---+-------------------------------------------+
| .   .   . | N | .   .   .   .   .   .   .   .   .   .   . |
|           |   +---+                                       |
| .   .   . |       | .   .   .   .   .   .   .   .   .   . |
|           +---+   |                                       |
| .   .   .   . |   | .   .   .   .   .   .   .   .   .   . |
|               |   |                                       |
| .   .   .   . |   | .   .   .   .   .   .   .   .   .   . |
+---------------+---+---------------------------------------+

このようなピースの配置を予め排除しておくことで、特に横長の盤面で効果があります。

ピースの配置が進んだときに他のピースとの位置関係で閉塞領域ができてしまうので、それをチェックするとさらに高速化が期待できます。ただし、これは閉塞領域のチェックにかかるコストと効果のトレードオフになります。今回は実装していません。

解の表示

ピースが敷き詰められていく状況はビットパターンで持っているので、それだけではどのピースがどこに配置されているかは判別できません。ビットパターンと別に２次元や３次元の配列を用意してそこにピースのIDを書き込むというのは無駄な処理になります。
そこで、solve() に ブロックを渡し、解が見つかったらブロックを yield で呼び出しています。ピースが配置される度に solve() が入れ子で call され、解が見つかると最後の solve() のブロックから最初の solve()ブロックが実行されます。
最初の solve() のブロックというのは以下のようになっていて、配置されたピースの情報（figs）が渡ってきます。これを使って解を表示しています。

solve( nil_fig, @grid.symms ) { |cond, figs|
  if cond == :done
    @solutions += 1
    last_solution = figs
  end
  if @o[:every] != 0 && ( @solutions % @o[:every] == 0 || @solutions == 1 )
    show_solution( figs )
  end
}

ピースの順番

平面では 'X' を最初に配置するのが一番効率が良いようです。
立体（3x4x5）では 'I' をに最初に配置するのが効果的です。'I' は長さが５なので、配置できる場所は限定されます。そのため、他のピースを配置してからでは失敗する確率が高く、最初に配置してしまうのが良さそうなことは直感的にも理解できます。

その他

ごちゃごちゃとオプション機能を実装しています。
ヘルプを参照ください

$ ruby solver-3D.rb --help
  Size  Solutions   Size   Solutions   Size  Solutions   Size  Solutions
  ----- ---------   ------ ---------   ----- ---------   ------ ---------
  6x10    2,339     5x4x3   3,940      8x8h       65     7x9h      150
  5x12    1,010     6x5x2     264      8x8    16,146     7x9    62,024
  4x15      368     10x3x2     12      4x16h      47     3x21       56
  3x20        2                        4x16    2,451

    -s, --size WxHxD                 6x10x1(default)
                                     8x8h, 7x9h : with a hole in the middle
    -e, --every N                    display a solution every N times.
                                     (nothing when N=0)
    -i, --interactive
    -n, --[no-]wind-up
    -p, --print                      print piece ID
    -3, --3D                         equivalent -s3x4x5
        --step                       show step-by-step
        --debug

参考