こんにちは、プログラマーパパ🥷🏻です。
前回の続きになります。
秋ですね〜
勉学の秋、スポーツの秋、読書の秋、どれも🧒🏻に頑張ってほしいものですが、
プログラマーパパ的には
プログラミングの秋🍁
涼しい環境でコーヒー☕️片手にプログラムを組んでいるだけで一日中楽しく過ごせます☺️
というわけで、丹念亭パズルにプログラミングで挑もうと思います
以下、パズルを自力で解こうと思っている方はネタバレ含むので見ないようにお願いします。
【設計１】 パズルの場面を表現（状態の定義）
積み木にID を割り当てパズルの状態を表現します。
- 盤面は4 x 5
- 縦横幅ある積み木は同一ID
- 空白は*
初期状態（状態０）
本質的ではないですが、積み木が１０枚でIDが０〜９で済んでいるので状態を表すのに凸凹がなくて見やすくて良いです。
要は積み木１１枚以上でID=10 が出てくると、１行当たりの文字数に大小が出てきて見た目に美しさに欠けます
0,0,1,*,* 0,0,1,2,2 3,4,5,6,7 8,8,5,6,9
終了状態（ゴール）
ここが１つのポイント。
終了条件（小人を柵で閉じ込める）を満たすためには、下記いずれかの状態しかあり得ないという点。
おそらくパズル設計者も２つ目の終了状態に気づくかどうかを試しているのではないだろうか、と推測。
? は任意の積み木、または、空白が来ても良いことを表す。
?,?,1,?,? ?,?,1,2,2 ?,?,5,0,0 ?,?,5,0,0
または
?,?,?,?,1 ?,?,2,2,1 ?,?,5,0,0 ?,?,5,0,0
【設計２】パズル上での操作を表現（状態遷移の定義）
積み木は上下左右にしか動けないのでそれぞれの操作にIDを割り当てる
上：0 (up)
下：1 (down)
左：2 (left)
右：3 (right)
以降、操作を（積み木のID, up、down、left、right） で表現します。
積み木の上下左右移動可能かどうかを調べ、移動可能な動作をリストアップします。
初期状態からだと、（ID=2, up）のみなので下記状態を積みます。
初期状態からは他には遷移先がないので下記のみとなります（状態１）
0,0,1,2,2 0,0,1,*,* 3,4,5,6,7 8,8,5,6,9
【設計３】一度辿った状態は辿らない（無限ループの防止）
ここからが分岐が発生して候補としては下記になります
- (ID=6, up)
- (ID=7, up)
- (ID=2, down)
ここが次のポイント。
上２つはこれまでに訪れたことのない状態ですが、３つめを選ぶと初期状態へ戻ることになり永久にゴールに辿り着けません（無限ループに入る）
なので１度訪れた状態を記憶しておき、その状態は次の候補先から除くという処理が必要になります。
【設計４】 候補先の選定基準（評価関数の定義）
設計１〜３までで一応動作するプログラムにはなりますが、これだけではまだ解けませんでした（数十分で見つからない）
設計３で無限ループに陥ることはないですが、ゴールへ辿り着く筋の良い手を選べず、ゴールからは遠い候補の選択を繰り返していることになります。
ここで遷移先の状態を選択するかどうかを評価する評価関数を定義します。
単純なものとして下記を定義します
ID=0 の積み木がゴールまでとどれだけ離れているかの移動距離
それぞれの状態に対してID=0 の積み木の左上とゴール状態とで、障害物がないと仮定した場合に積み木を何回動かすか、に相当します
移動距離=5
0,0,?,?,? 0,0,?,?,? ?,?,?,?,? ?,?,?,?,?
移動距離=4
?,?,?,?,? 0,0,?,?,? 0,0,?,?,? ?,?,?,?,?
単純な評価関数ですが、これだけである程度マシな候補先を絞ることができます。
ここまでが基本的な処理となり、まとめると下記となります。
- 状態を定義
- 初期状態
- 終了状態
- 操作を定義
- 移動可能な状態をリストアップ
- 一度訪れた状態は訪れない（無限ループの防止）
- 候補先を選定する（評価関数）
ここまでで初期状態から終了状態までの経路は一応見つかりました
手元の環境では12秒の探索時間で1873 回操作の手順が見つかりました
【設計５】筋の良い手とは何か？（評価関数を改善）
直感的に4 x 5 のサイズのパズルだと1873回より少ない手数でゴールへ辿り着く方法はありそうです。
評価関数を工夫することで次にどの候補を優先して選ぶか、をある程度はコントロールできます。
ID=0 以外のID=1,2,5 のゴール状態までの距離の加算
次はID=0 の積み木以外のID=1,2,5 もゴール状態との距離を計算し、その和が小さい状態を選択していくのはどうなるか？
これだと34秒で8231回操作の手順が見つかりました（微妙ですね）
えてしてシンプルな設計の方が上手くいくということかもしれません
ID=0 とゴール状態までの距離＋状態までの操作回数
評価関数は現在状態とゴール状態の差だけで表現しなければいけないものでもありません。
パズルの探索はより短い手数でゴールへ辿り着ける手順の方が良いことが多いです。
なので、現在状態からゴールまでの距離に現在状態に至るまでの操作回数を評価関数に加算します。
直感的には現在状態からゴールに近そうなものであり、かつ、そこに至るまでの手数が少ない候補を優先します
そうすると315秒で操作回数161 回の手順が見つかりました🎉
161 回が最小の操作回数かどうかの証明はできないですが、一旦、100回と少しなので現実的に解いた感は出てきました。
プログラムにより見つかった操作手順とゴール状態を記載しておきます。
操作手順：
[(2, 'up'), (7, 'up'), (7, 'left'), (9, 'up'), (9, 'up'), (6, 'right'), (5, 'right'), (1, 'down'), (1, 'down'), (7, 'left'), (9, 'left'), (6, 'up'), (2, 'left'), (6, 'up'), (5, 'right'), (1, 'right'), (4, 'right'), (4, 'down'), (3, 'right'), (3, 'right'), (0, 'down'), (2, 'left'), (2, 'left'), (9, 'up'), (9, 'left'), (6, 'left'), (5, 'up'), (5, 'up'), (1, 'right'), (3, 'right'), (4, 'up'), (8, 'right'), (8, 'right'), (0, 'down'), (7, 'left'), (9, 'down'), (7, 'left'), (9, 'left'), (6, 'left'), (3, 'up'), (4, 'right'), (6, 'down'), (2, 'right'), (2, 'right'), (9, 'up'), (7, 'up'), (0, 'up'), (8, 'left'), (8, 'left'), (4, 'down'), (4, 'left'), (1, 'left'), (5, 'down'), (5, 'down'), (3, 'right'), (2, 'right'), (6, 'up'), (1, 'up'), (4, 'up'), (8, 'right'), (8, 'right'), (0, 'down'), (7, 'down'), (9, 'left'), (6, 'left'), (2, 'left'), (3, 'up'), (4, 'up'), (5, 'up'), (8, 'right'), (0, 'right'), (7, 'down'), (7, 'down'), (9, 'down'), (9, 'down'), (6, 'left'), (4, 'left'), (4, 'up'), (0, 'up'), (7, 'right'), (9, 'down'), (7, 'right'), (9, 'right'), (6, 'down'), (6, 'down'), (4, 'left'), (4, 'down'), (2, 'left'), (2, 'left'), (3, 'left'), (5, 'up'), (3, 'left'), (1, 'up'), (8, 'up'), (7, 'right'), (9, 'right'), (7, 'right'), (9, 'right'), (0, 'down'), (4, 'right'), (6, 'up'), (3, 'down'), (2, 'right'), (6, 'up'), (0, 'left'), (9, 'left'), (8, 'left'), (7, 'left'), (5, 'down'), (5, 'down'), (1, 'right'), (2, 'right'), (4, 'up'), (3, 'left'), (8, 'up'), (7, 'up'), (9, 'right'), (0, 'right'), (6, 'down'), (6, 'down'), (4, 'left'), (2, 'left'), (3, 'left'), (8, 'left'), (7, 'up'), (7, 'up'), (9, 'up'), (9, 'up'), (5, 'left'), (1, 'down'), (1, 'down'), (9, 'right'), (5, 'up'), (7, 'right'), (5, 'up'), (0, 'right'), (6, 'right'), (3, 'down'), (4, 'down'), (3, 'down'), (4, 'down'), (8, 'left'), (2, 'left'), (5, 'left'), (9, 'left'), (7, 'left'), (1, 'up'), (1, 'up'), (0, 'right'), (5, 'down'), (5, 'down'), (9, 'left'), (2, 'right'), (7, 'down'), (2, 'right'), (8, 'up'), (9, 'left'), (9, 'left'), (7, 'left'), (7, 'left'), (2, 'down')]
今回得られたゴール：
8,8,*,*,1
9,7,2,2,1
4,6,5,0,0
3,6,5,0,0
9,7,2,2,1
4,6,5,0,0
3,6,5,0,0
以上、プログラミングで丹念亭パズルに挑んでみました。
こういう楽しみ方もあると捉えてもらえると幸いです。
美味しいコーヒーやビーフシチューいただきながら、パズルを楽しむのもまた一興ですね☕️
次回は今回得られた結果を別の側面から見ることにします