プログラムの作成
方針が定まったので、プログラムを下記の3つのモジュールに分解して作成することにします。
- main.py：初期状態を入力して実行を開始し、解法を出力するモジュール
- search.py：探索に関する関数を定義するモジュール
- board.py：盤面の変化に関する関数を定義するモジュール
それぞれのモジュールの概略設計を疑似コードで示すと以下の様になります。
厳密さは欠いていますが、プログラムの大枠を説明するものです。
main.py
import search.py 初期盤面boardを入力 search.breadth_first_search( ) #解を横型探索する 解が得られたときに解法のステップを出力
search.py
import board.py def breadth_first_search( ) 探索する順に盤面を並べるboard_queを初期化 盤面パターンの集合pattern_setを初期化 boardの親子関係を保持するparent_child_linkを初期化 解法のステップsolution_pathを初期化 while len(board_que) > 0 board_queから先頭の盤面をpop board.candidate_children_board( ) #遷移可能な子boardのリストを作る board.valid_children_board( ) #重複しない子boardだけをboard_queに追加 if 出口に娘のタイルがある break return solution_path
board.py
def candidate_children_board( ) 上方向への移動で生成される盤面を子boardのリストへ追加 下方向への移動で生成される盤面を子boardのリストへ追加 右方向への移動で生成される盤面を子boardのリストへ追加 左方向への移動で生成される盤面を子boardのリストへ追加 return 遷移可能な子boardのリスト def valid_children_board( ) for 遷移可能な子board if 子boardのパターンが新規のパターンか ? parent_child_linkに追加する pattern_setに追加 board_queの最後にその子boardを追加する 出口に娘のタイルがあるかどうかを判定する return
以上の設計に基づいて実際にコードを書いてみました。
ちょっと長いし、リファクタリングも必要なのでここでは詳細は割愛します。
そのうち整理出来たらGitHubで公開することにします。
