探索方法

この記事は、ペンシルパズルAI Advent Calendar 2019 16日目の記事です。

今までは、「角のマスから1マスずつ黒白を決め、分断したら別のパターン」という再帰でプログラムを書いて、特定のサイズのへやに、へやわけのルールを満たしたまま黒マスを詰める方法を探索していました。

最近、DP法を実装できたので探索範囲が広がり、得られた結果(Googleスプレッドシート)の角のへやのタブが拡充されました。

実装に当たり@hidesugar2氏のツイートを参考にしました。引用します。
"「ある行をどのように塗れるか」は「その直前の行がどのように塗られているか」のみに依存します。なので、(何列目まで見たか,累計何マス塗ったか,直前の行の塗られ方はどうなっているか)の3状態を持ったDPで求めることが出来ます(詳細は次ツイート
5×nならある行の塗り方は(φ,1,2,3,4,5,13,14,15,24,25,35,135)の13通りですが、2マス以上塗る場合は、それらが同じ連結成分に属しているかで場合分けしておく必要があり(分断禁)、2マスで各2通り、3マスは5通りの計23通りになります。"

作成した探索プログラム(ideone)の原理を書きます。
角のへやの探索をします。上と左に壁があるものとして考えます。

A.一行ごとの塗り方(以下「状態」と呼びます)をリストアップします。
まず、一行ごとに、横nマスに入る黒マスと白マスのパターンをリストアップします。黒マスは隣接しません。黒を1,白を0とし、[1,0,1,0,0,0,1]などと付けます。
そして、黒マスどうしの斜めの連なりに注目し、どの黒マスがどの連なりに属するかの番号も付けます。
同じ[1,0,1,0,0,0,1]という塗り方でも、連なりの番号の振り方は複数あります。
[1,0,2,0,0,0,2]なら、左から3マス目と7マス目の黒マスが、同じ連なりに属します。
[1,0,2,0,0,0,3]なら、どの黒マスも別々の連なりに属します。
番号は左から振ることにします。横7マスなら、登場する最大の数字は4です。
さらに場合分けをします。連なりのうち、壁にアースされているもの(連なりの中に、壁に接している黒マスがあるもの)を全て1とします。アースされていない連なりには改めて2以上の番号を振っていきます。
[1,0,2,0,0,0,2],[2,0,1,0,0,0,1],[2,0,3,0,0,0,3]は全て別々の状態です。
今回は左端に壁があるので、左端に黒マスがあるとき、その黒マスの番号は確実に1です。それ以外は状態リストから削除します。

B.遷移行列
状態ごとに、その下の行に入りうる状態は限られます。どの状態の下にどの状態が入るか、その一覧表が遷移行列です。
状態ごとに、その下の行に黒マスを並べ、下の行がどの状態になるかを調べます。
下の行の黒マスの、左上や右上にどの連なりの黒マスがあるのかを見つつ、番号を振っていきます。
番号を最後まで振ってから、小さい順に並べ替えています。
黒マスの左上か右上が1なら、その黒マスもやはり1です。
左上と右上の番号が同じなら(その時に限り)分断禁に違反します。

C.状態の整理
状態ごとの、黒マスの個数と、最上列に入るかどうかのリストを作ります。

D.DP
(現在の行、今まで詰めた黒マスの個数、現在の最下列の状態の番号)の3状態でDPします。
先ほどの遷移行列を用いて、状態ごとに、最下列のさらに下に付け足せるか判定します。
全状態が終了したら、次の行に進み、最後の行で目的の黒マスの個数に達しているものを足し、解の総数を求めます。
また、解の具体的な構成も出来ます。最下列から黒マスの数を引いて行って上の列へと戻っていき、「現在の最下列の状態の番号」を拾っていき、すべてつなげれば完成です。

角の1x5から100x5までの解の総数を数え上げるのに数分かかります。

得られた結果より、様々な洞察が得られました。角のへやのPage 1に掲載しています。


手筋集トップへ戻る




このサイトは無料ホームページ作成.comで作成されています