情報処理学会 第76回全国大会講演要旨

箱入り娘型パズルは，複数の形状のコマを持ち，特定のコマを特定の位置に移
動させることを目的とするスライディングパズルであり，サイズ4x5に固定され
たパズルの一般化である．このパズルの最適解を効率的に得るためにいくつか
のコマを分解し，2段階に分けて部分パターンへ写像することによりパターンデー
タベースを構築した．サイズ6x7のパズルについてこのパターンデータベース
を用いることで幅優先探索と比べて計算時間を約1000倍程度高速化をすること
ができた．