| ペントミノ
|
|
|
|
|
|
|
| ■ はじめに
|
|
|
| ペントミノは正方形を5つ結合した12種類のピース（図1 a）を 10x6 の長方形に組み上げるパズルである（図1 b）。
|
図1. ペントミノパズル
(a)
┌─┐ ┌┐ ┌─┐ ┌─┐┌──┐
│┌┘┌┘└┐┌────┐└┐└┐┌┘┌┘└┐┌┘
│└┐└┐┌┘└────┘ └┐│└┐│ ││
└─┘ └┘ └┘ └┘ └┘
┌┐ ┌┐ ┌┐ ┌┐ ┌─┐ ┌┐
│└┐┌─┘└┐┌─┘│ ││┌─┘┌┘┌──┘│
│ │└───┘│┌─┘┌─┘│└──┘ └───┘
└─┘ └┘ └──┘
↓
(b)
┏━┯┯━━━━┯┯┓
┃┌┘└┬─┬─┘│┃
┃└┐┌┘┌┤┌─┘┃
┠─┴┤┌┤└┴┬─┨
┃ ┌┼┘│┌─┘┌┨
┠─┘└┐└┼──┘┃
┗━━━┷━┷━━━┛
|
|
|
| ■ 解法
|
|
|
| 深さ優先探索で各ピースを順に盤面に置いていけば解を求めることができる。ピースの置き方は回転と反転の組み合わせで最大8通りがあるので、左上点を起点とするピース形状のテーブルを作成する。ただし、対称解を排除するために非対称ピースのひとつを2方向のみとしておく。
|
| List 1. に解を求めるプログラムのアルゴリズムを示す。
|
List1. ペントミノの解を求めるプログラム
void doSearch()
{
for(各ピースについて) {
if( ピースが未使用 ) {
for(ピースの各方向について) {
if( 配置可能 ) {
盤面に置く;
if( 12個全て配置した )
解を表示
else
doSearch():
ピースを戻す;
}
}
}
}
}
|
| 上記アルゴリズムによる C++ ソースプログラムを pent.cpp に置く。
|
| PenIII@800, MEM:386, Win2K, VC++6.0 の環境で実行した結果、2339個の解を得るのに 80.20 秒を要した。
|
|
|
| ■ 高速化
|
|
|
| 盤面の左から右、上から下、の順序でピースを配置しているが、盤面を縦長にするだけで処理時間を 80.20 秒から 5.19 秒に大幅に短縮できた。これは無駄な探索が実行される頻度が少なくなるためである。図2.は L 型、T 型ピースを配置した状態だが、ピースに囲まれた部分は2マスしかなく、この時点で探索を打ち切るべきである。しかし、横長の盤面では T の右に3〜4個のピースを置くことが可能で、そのために多くの盤面を無駄に探索しなくてはいけない。それに対し、縦長の盤面では T の右にピースを置く場合の数が限られており、無駄な探索処理が大幅に減る。実際に行き詰まり局面数を数えたところ、横方向の盤面では 91,350,949 だったのが、縦方向では 5,982,169 に減っていた。トータルの処理時間は末端局面数に比例していて、1秒間に約100万の末端盤面をチェックしていることが解る。
|
図2. 盤面の方向による無駄な探索数の違い
┏┯━━┯━━━━━┓ ┏┯━━┯━┓
┃├┐┌┘ ┃ ┃├┐┌┘ ┃
┃│││ ┃ ┃│││ ┃
┃└┼┘ ┃ ┃└┼┘ ┃
┠─┘ ┃ ┠─┘ ┃
┃ ┃ ┃ ┃
┗━━━━━━━━━┛ ┃ ┃
┃ ┃
┃ ┃
┃ ┃
┗━━━━━┛
|
| さらに高速化するには、図2.の様に既に配置不能になっている盤面でそれ以上の無駄な探索を行わないようにする必要がある。ただし、そのチェックに時間をかけるとトータルではかえって時間がかかるようになってしまう場合もあるので、どのようなチェックをいつ行うかを慎重に決める必要がある。
|
|
|