The Fool In The Valleyの雑記帳

-- 好奇心いっぱいのおじいちゃんが綴るよしなし事 --

箱入り娘を解く その3

データ構造

その2で探索の方針が決まったので、それをPythonで実装するためのデータ構造、関数について考えます。

◆ 盤面

その1で述べたように、盤面は5×4のマスで考えると統一的に処理できるので、多次元配列を扱うことができる、numpyのndarray(N-dimensional array)を使って表すことにします。ndarrayを使うと、盤面の初期状態を下の図の(A)とすると、それは

numpy.array( [ 
[2,1,1,3], 
[2,1,1,3], 
[4,6,6,5], 
[4,7,7,5], 
[7,0,0,7]  ] )
=numpy.array( [ [2,1,1,3], [2,1,1,3], [4,6,6,5], [4,7,7,5], [7,0,0,7] ] )

という形で書き表すことができます。

◆ 盤面パターンの集合

パズルを解くために盤面の状態の遷移をTreeで表現し、個々の状態をnodeに対応させるようにしますが、そのとき、すべてのnodeは異なっていなければなりません。そこで盤面の状態の集合を管理しておく必要があります。Pythonのset型は、中に含む要素を重複しないように管理するので、これを使うとすでに登録されているパターンかどうかを判定して、重複するパターンなら排除する、異なるパターンなら追加する、ということが容易にできます。
ここでset型の要素として登録するのは、タイルの形状のみに着目した情報であり、同一形状のタイルを区別する必要はありません。下の図で(1)、(2)、(3)はパズル的にはどれも等価だからです。

そこで、盤面がたとえば(A)の状態のときは、2で3,4,5を代表させて(B)のように単純化し、それを(C)のように5×4の枡目のデータで表すようにします。

その5×4のndarrayを比較するために、numpyのflatten関数を使って1次元に変換し、さらにそれを20字の文字列に変換することにします。
その結果、set型の要素としては下記の様な20字の文字列を登録していきます。

{'CBBCCBBCCGGCCHHCHAAH'}

例としてlevel 2までTreeを展開するとnodeが19個できます。

その時に登録されている盤面は、具体的には次のような異なる19の要素の集合になります。

{ 
'CBBCCBBCCGGCCHACHHHA', 'CBBCCBBCCGGCCAHCHHHA', 'CBBCCBBCAGGCCHHCCAHH', 
'CBBCCBBCCGGCCAHCHAHH', 'CBBCCBBCCGGCCHACHHAH', 'CBBCCBBCCGGCCHHCHHAA', 
'CBBCCBBCCGGACHHCHHAC', 'CBBCCBBCCGGCCHHCAAHH', 'CBBCCBBCCGGACHHCHAHC', 
'CBBCCBBCCGGCCAHCHHAH', 'CBBCCBBCCGGCCAACHHHH', 'CBBCCBBCCGGCCAHCAHHH', 
'CBBCCBBCCGGCCHHCHAHA', 'CBBCCBBCCGGCCHACHAHH', 'CBBCCBBCCGGCCHHCAHAH', 
'CBBCCBBCCGGCCHHCAHHA', 'CBBCCBBCCGGCCHACAHHH', 'CBBCCBBCAGGCCHHCCHAH',
'CBBCCBBCCGGCCHHCHAAH'
} 

◆ 盤面の親子関係

子の盤面からは親の盤面が一意に決まります。その関係を使うと、解が得られたときに、順に親の盤面をたどると初期の盤面までさかのぼることができます。下の図はその様子を示したもので、node kの盤面でパズルが解けたとき、その親の盤面j、その親の盤面iと辿って、最終的にTreeのなかでrootの盤面までのパスを辿ることができ、その逆のパスが解法の手順になるわけです。

こうした情報を保存するために、親の盤面parent_boardから子の盤面child_boardが生成されたとき、その情報をタプル(parent_board, child_board)で保存し、それをparent_child_link= [ ]というリストにappendして追加するようにしておきます。そうすると、下のような手順で解法の手順を得ることができます。

    node = final_board       # final_board: 解が得られた盤面
    solution_path.append(node)   # solution_path : 解法のステップの順で並べた盤面のリスト
    for cn in reversed(parent_child_link):
        if numpy.all(cn[1] == node):
            solution_path.append(cn[0])
            node = cn[0]

◆ 横型探索の順番管理

横型探索を行うためには、nodeを走査する順に並べて管理しておく必要があります。
それはPythonの標準ライブラリcollectionsモジュールの deque 型を使うと取り扱いが容易です。下の図はその様子を示したもので、走査する順にnodeを並べたdequeの先頭からnodeを一つpopで取り出し、そのnodeをparent nodeとするchild nodeを作ってそれらをdequeの最後にappendで追加していく様子を示しています。


タイルの移動

ある盤面をparent nodeとした時に、スペースを使ってタイルを動かすことによって生成されるすべての盤面がchild nodeとなりますが、それを得るには、5×4の枡目の中にあるスペースを意味する0の位置が分からなければなりません。numpyのwhereという関数は条件式に合うをndarrayを返すので、

y, x = numpy.where(board == 0)

によって、2つのスペースが5×4の行列において、y[0] x[0] と y[1] x[1]の位置にあることがわかります。

その2つのスペースの種類は下に示すように、(a)1×1が離れて2つある、(b)2×1が一つ、(c)1×2が一つの3つの場合があります。

その配置と形状によって上下左右にあるどのタイルをどれだけ動かせるかが異なるので、それを判定する関数を定義して、すべての妥当な、つまり重複の無いchild nodeを作成するようにします。


箱入り娘を解く その2 ⇐ ⇒ 箱入り娘を解く その4