たまにはパズル: 6×6領域の同形4分割(1)
年末に同僚からこんなパズルを出題されました。
正方形を6×6に並べた領域がある。
これを同じ形の4つの領域に分割する方法をすべて示しなさい。
冬休みの宿題として楽しく解くことができました。どういう風に考えてプログラムを作ったか、その流れを振り返りつつ解説してみようと思います。
問題の定式化
このような領域を
┏┯┯┯┯┯┓ ┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨ ┗┷┷┷┷┷┛
例えばこのように分割すればいいのでしょう。
┏━━┳━━┓ ┃┏━┛┏┓┃ ┃┗━┓┃┃┃ ┣┓┏╋┛┗┫ ┃┃┃┗━┓┃ ┃┗┛┏━┛┃ ┗━━┻━━┛
この図は書くにはホネが折れるので、もう少し楽な表現方法を考えます。こんなでいいでしょう。
444333 433323 444323 141222 141112 111222
数字ひとつが正方形に対応し、同じ数字は同じ領域に属するという意味です。
いろいろ条件が足りないですが、パズルとして成立するように補います。「同じ形」というのは回転できるのは当然ですが、鏡像も同じと考えていいでしょう。飛び地やどこにも属さない余りは許されないと考えてよさそうです。
ひとつの解が見つかれば、当然それ全体を回転したり鏡像を取ったりすればまたそれも解になります。対称性を利用して計算量を減らしたりできそうです。
解法の方針を考える
さて、解法を考えます。年末の大そうじをしながら、買物に出かける道々の自転車の上、おふろでのんびりしている間、リラックスしてぼんやりと思いをめぐらしていました。こういう時間が意外と大切だと思っています。
この手の問題は、最終的には何らかの全数探索(しらみつぶし)に行きつきます。重複なくすべての可能性を検査するには、何をどんな順番で当たっていければいいのかと考えます。
普通まず最初は、紙と鉛筆を使って手で解いてみます。その中から規則性を見つけてアルゴリズムにしていきます。今回は年末年始でなかなかパソコン前に長時間座ってもいられなかったので、頭の中だけでいろいろ思考実験をくり返しました。
最初に行けそうだなと考えたのはこんな方法です。3×3の正方形4つに分割する解はすぐ見つかります。そこからでっぱらしたりひっこめたりすると、上に挙げた解に似たものがいくつか見つかります。回転対称を利用して組織的に計算できそうです。
計算機にやらせるなら、3×3に分割完了した状態から変化させるより、空白からスタートする方がよいでしょう。角は必ずどれかひとつの領域に入りますから、それを少しずつ大きくしながら、対称性を考えて他の領域にぶつからないようにのばしていきます。
1....2 11...2 111..2 111112 111112 ...... .....2 .....2 411.22 411122 ...... ...... .....2 4...22 441222 ...... ...... 4..... 44...2 444322 ...... 4..... 4..... 44.332 443332 4....3 4...33 4..333 433333 433333
対称形を維持して置いていくので、領域1を拡張できる場所がある場合は必ず他の領域も同様に拡張できます。空白がなくなれば完成。どの空白を選ぶかで順序づけすれば全数探索ができます。なかなかよさそうですが、回転対称以外の解は出てきません。そういう解があるかもしれません(実際ありました)。
他に方法はないでしょうか。6×6領域を4分割するのだから、1領域の面積は9です。面積が9になるような図形を4つ複製して、それを並べて正方形を作れれば解になります。
高校生のころCを勉強した本「Cー言語とプログラミング(米田信夫)」には、ペントミノパズルを解くという例題が載っていました。ペントミノは12種類のピースをすきまなく6×10の長方形の盤面に並べます。今回のお題は同じ形のピース4個をすきまなく6×6の正方形の盤面に並べます。同じ構造をしていますね。
ちなみに、正方形5個で作る形なのでpent(5)-omino→ペントミノ。今回は9個ですが何て言うのでしょうね。5:ペントミノ、6:ヘキソミノ、7:ヘプトミノかセプトミノかな、8:オクトミノ、9だとノナミノでしょうか? Wikipediaで調べると、ノノミノと言うそうです。
米田先生の本に出ていたペントミノの解法は、再帰呼出しによるバックトラックでした。 ペントミノパズルのバックトラック探索を疑似コードで書くとこうなります。
procedure backtrack(board, pieces) if pieces = empty then output_solution(board) else p ← first(pieces) for f in all_possible_rotations_and_reflections(p) for l in all_possible_locations(board, f) if can_place(board, f, l) then backtrack(place(board, f, l), rest(pieces))
この再帰手続きに初期値として空っぽの盤面と12種類のペントミノを渡すとパズルを解きます。こんな感じ。
backtrack(empty_board, all_pentominos)
このアルゴリズムは、ピースをひとつ手に取り、置ける場所があればとりあえず置いてみて、次のピースを取る。置ける場所がなければ手に持っている回転したり裏返したりして試す。それもダメだったら、ひとつ前に戻ってさっき置いたピースを外して他の場所に置いてみる……という動作をします。運よく(?)全部置ければ正解です。
今回の問題の場合、boardとして6×6の領域、piecesとして1種類のノノミノ4つを入れればよいですね。これをすべてのノノミノに対してくり返します。
for nono in (all_nonominos) backtrack(empty_6x6_board, [nono, nono, nono, nono])
バックトラッキング法はコードも簡単だし、あまり遅いようなら枝刈りの工夫を加えることもできるでしょう。今回はこれでいきましょう。
解法の実装を考える
さて、上の疑似コードをそのまま実装してもいいですが、たたでさえ時間のかかる全数探索なので何か工夫したいところです。
盤面のデータ構造が最初に問題になります。6×6の2次元配列の各要素に1〜4までの領域番号を入れていくのはどうか。空の部分は0でも入れておけばいいでしょう。can_placeではノノミノの9つの正方形がどの位置にあたるか計算して、全部が0ならば置ける、でよさそうです。米田先生の本では後置インクリメントと&&ショートカット演算子という、Cの特徴を生かしたコードになっていました(本の現物が手元になく引用できないのが残念)。
もっと楽はできないでしょうか。can_placeの判定が一番多くくり返される部分です。ここを高速にしたい。空いているか、空いていないか。その判定を複数まとめてやりたい。こういうときはビット演算の出番です。
盤面の各位置が空いていれば0、埋まっていれば1としたビット列を作ります。これから置こうとしている位置のビット列とandを取って0かどうかでcan_placeの判定が行えます。どの位置がどの領域に入っているかは別の変数で覚えてもよいでしょう。解が見つかってoutputするときまではその情報は必要ありません。
盤面が6×6なので36ビットの論理演算になります。惜しい! 4ビット足りない。……いやいや、待て待て。このPCって64ビットCPUじゃなかったっけ。64ビットあれば8×8まで行ける! 盤面外の判定もあらかじめビットを立てておけば、複雑な条件分枝をコーディングする必要はありません。
実装方針が決まった
ここまでをまとめるとこうなります。
10日間くらい、すき間の時間があるとぼんやりとこの問題について考えていました。お仕事だと、ここで「試作」とか「設計」をしますが、趣味のトイプログラムなので、今回はここからいきなりコーディングに入りました。実際にはここまで頭の中だけで考えたので、Wikipediaを調べたりはしていません。この記事を書くために調べましたが、たくさんの情報が出てきて勉強になりました。コードを書き出す前にもっと調べていればよかった。前にも書き出す前に調べればとか言ったことがあります。もっと検索活用しないと。
ちょっと長くなったので続きます。次回はコードを書きながらこんな工夫したよ、というあたりを書いてみようと思います。
