The Fool In The Valleyの雑記帳

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

箱入り娘を解く その4

プログラムの作成

方針が定まったので、プログラムを下記の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で公開することにします。

箱入り娘を解く その3 ⇐ ⇒ 箱入り娘を解く その5