金【プログラミング】プログラマー旅行へ行く（３）〜丹念亭パズルをプログラミング課題として捉える〜

こんにちは、プログラマーパパ🥷🏻です。

前回は丹念亭パズルの経路をプログラミングで探索し解の１つを見つけました。

丹念亭パズル

見つかった経路を簡単に視覚化してみました（数字（ID）の振り方は前回記事を参照）

経過を追っていくことで１６１回の操作後に小人の積み木が右下へ来ているのがわかります。

今回は解の１つを見つけただけでより操作回数の少ない解は存在するかもしれません。

最小の操作回数を探すのはより難しい問題として定義できそうですね🤔

プログラマーパパ🥷🏻がパズルからプログラミングの問題を作る場合こんな感じの出題になります。

1. パズルを探索問題として解くように設計を考えましょう（ここが意外と難しい）
2. 実際にプログラムが稼働することを確認し解の１つを見つけましょう（１ができてないと２は動かない）
3. 評価関数を工夫しましょう（単純なケース、ヒューリスティクスを工夫した場合）
4. （発展問題）最小操作回数を求め、それが最小であることを証明しましょう

ちなみに4 番はプログラマーパパ🥷🏻も解けてないです😅

では、そろそろ🧒🏻の勉強へ戻ることにします

（付録）１６１回操作でゴールへ辿り着く途中の譜面

[0]-2-up--
0,0,1,↑,*
0,0,1,2,2
3,4,5,6,7
8,8,5,6,9

[1]-7-up--
0,0,1,2,2
0,0,1,*,↑
3,4,5,6,7
8,8,5,6,9

[2]-7-left--
0,0,1,2,2
0,0,1,←,7
3,4,5,6,*
8,8,5,6,9

[3]-9-up--
0,0,1,2,2
0,0,1,7,*
3,4,5,6,↑
8,8,5,6,9

[4]-9-up--
0,0,1,2,2
0,0,1,7,↑
3,4,5,6,9
8,8,5,6,*

[5]-6-right--
0,0,1,2,2
0,0,1,7,9
3,4,5,6,→
8,8,5,6,*

[6]-5-right--
0,0,1,2,2
0,0,1,7,9
3,4,5,→,6
8,8,5,*,6

[7]-1-down--
0,0,1,2,2
0,0,1,7,9
3,4,↓,5,6
8,8,*,5,6

[8]-1-down--
0,0,*,2,2
0,0,1,7,9
3,4,1,5,6
8,8,↓,5,6

[9]-7-left--
0,0,*,2,2
0,0,←,7,9
3,4,1,5,6
8,8,1,5,6

[10]-9-left--
0,0,*,2,2
0,0,7,←,9
3,4,1,5,6
8,8,1,5,6

[11]-6-up--
0,0,*,2,2
0,0,7,9,↑
3,4,1,5,6
8,8,1,5,6

[12]-2-left--
0,0,←,2,2
0,0,7,9,6
3,4,1,5,6
8,8,1,5,*

[13]-6-up--
0,0,2,2,↑
0,0,7,9,6
3,4,1,5,6
8,8,1,5,*

[14]-5-right--
0,0,2,2,6
0,0,7,9,6
3,4,1,5,→
8,8,1,5,*

[15]-1-right--
0,0,2,2,6
0,0,7,9,6
3,4,1,→,5
8,8,1,*,5

[16]-4-right--
0,0,2,2,6
0,0,7,9,6
3,4,→,1,5
8,8,*,1,5

[17]-4-down--
0,0,2,2,6
0,0,7,9,6
3,*,4,1,5
8,8,↓,1,5

[18]-3-right--
0,0,2,2,6
0,0,7,9,6
3,→,*,1,5
8,8,4,1,5

[19]-3-right--
0,0,2,2,6
0,0,7,9,6
*,3,→,1,5
8,8,4,1,5

[20]-0-down--
0,0,2,2,6
0,0,7,9,6
↓,*,3,1,5
8,8,4,1,5

[21]-2-left--
*,←,2,2,6
0,0,7,9,6
0,0,3,1,5
8,8,4,1,5

[22]-2-left--
←,2,2,*,6
0,0,7,9,6
0,0,3,1,5
8,8,4,1,5

[23]-9-up--
2,2,*,↑,6
0,0,7,9,6
0,0,3,1,5
8,8,4,1,5

[24]-9-left--
2,2,←,9,6
0,0,7,*,6
0,0,3,1,5
8,8,4,1,5

[25]-6-left--
2,2,9,←,6
0,0,7,*,6
0,0,3,1,5
8,8,4,1,5

[26]-5-up--
2,2,9,6,*
0,0,7,6,↑
0,0,3,1,5
8,8,4,1,5

[27]-5-up--
2,2,9,6,↑
0,0,7,6,5
0,0,3,1,5
8,8,4,1,*

[28]-1-right--
2,2,9,6,5
0,0,7,6,5
0,0,3,1,→
8,8,4,1,*

[29]-3-right--
2,2,9,6,5
0,0,7,6,5
0,0,3,→,1
8,8,4,*,1

[30]-4-up--
2,2,9,6,5
0,0,7,6,5
0,0,↑,3,1
8,8,4,*,1

[31]-8-right--
2,2,9,6,5
0,0,7,6,5
0,0,4,3,1
8,8,→,*,1

[32]-8-right--
2,2,9,6,5
0,0,7,6,5
0,0,4,3,1
*,8,8,→,1

[33]-0-down--
2,2,9,6,5
0,0,7,6,5
0,0,4,3,1
↓,*,8,8,1

[34]-7-left--
2,2,9,6,5
*,←,7,6,5
0,0,4,3,1
0,0,8,8,1

[35]-9-down--
2,2,9,6,5
*,7,↓,6,5
0,0,4,3,1
0,0,8,8,1

[36]-7-left--
2,2,*,6,5
←,7,9,6,5
0,0,4,3,1
0,0,8,8,1

[37]-9-left--
2,2,*,6,5
7,←,9,6,5
0,0,4,3,1
0,0,8,8,1

[38]-6-left--
2,2,←,6,5
7,9,*,6,5
0,0,4,3,1
0,0,8,8,1

[39]-3-up--
2,2,6,*,5
7,9,6,↑,5
0,0,4,3,1
0,0,8,8,1

[40]-4-right--
2,2,6,*,5
7,9,6,3,5
0,0,4,→,1
0,0,8,8,1

[41]-6-down--
2,2,6,*,5
7,9,6,3,5
0,0,↓,4,1
0,0,8,8,1

[42]-2-right--
2,2,→,*,5
7,9,6,3,5
0,0,6,4,1
0,0,8,8,1

[43]-2-right--
*,2,2,→,5
7,9,6,3,5
0,0,6,4,1
0,0,8,8,1

[44]-9-up--
*,↑,2,2,5
7,9,6,3,5
0,0,6,4,1
0,0,8,8,1

[45]-7-up--
↑,9,2,2,5
7,*,6,3,5
0,0,6,4,1
0,0,8,8,1

[46]-0-up--
7,9,2,2,5
↑,*,6,3,5
0,0,6,4,1
0,0,8,8,1

[47]-8-left--
7,9,2,2,5
0,0,6,3,5
0,0,6,4,1
*,←,8,8,1

[48]-8-left--
7,9,2,2,5
0,0,6,3,5
0,0,6,4,1
←,8,8,*,1

[49]-4-down--
7,9,2,2,5
0,0,6,3,5
0,0,6,4,1
8,8,*,↓,1

[50]-4-left--
7,9,2,2,5
0,0,6,3,5
0,0,6,*,1
8,8,←,4,1

[51]-1-left--
7,9,2,2,5
0,0,6,3,5
0,0,6,←,1
8,8,4,*,1

[52]-5-down--
7,9,2,2,5
0,0,6,3,5
0,0,6,1,↓
8,8,4,1,*

[53]-5-down--
7,9,2,2,*
0,0,6,3,5
0,0,6,1,5
8,8,4,1,↓

[54]-3-right--
7,9,2,2,*
0,0,6,3,→
0,0,6,1,5
8,8,4,1,5

[55]-2-right--
7,9,2,2,→
0,0,6,*,3
0,0,6,1,5
8,8,4,1,5

[56]-6-up--
7,9,↑,2,2
0,0,6,*,3
0,0,6,1,5
8,8,4,1,5

[57]-1-up--
7,9,6,2,2
0,0,6,↑,3
0,0,*,1,5
8,8,4,1,5

[58]-4-up--
7,9,6,2,2
0,0,6,1,3
0,0,↑,1,5
8,8,4,*,5

[59]-8-right--
7,9,6,2,2
0,0,6,1,3
0,0,4,1,5
8,8,→,*,5

[60]-8-right--
7,9,6,2,2
0,0,6,1,3
0,0,4,1,5
*,8,8,→,5

[61]-0-down--
7,9,6,2,2
0,0,6,1,3
0,0,4,1,5
↓,*,8,8,5

[62]-7-down--
7,9,6,2,2
↓,*,6,1,3
0,0,4,1,5
0,0,8,8,5

[63]-9-left--
←,9,6,2,2
7,*,6,1,3
0,0,4,1,5
0,0,8,8,5

[64]-6-left--
9,←,6,2,2
7,*,6,1,3
0,0,4,1,5
0,0,8,8,5

[65]-2-left--
9,6,←,2,2
7,6,*,1,3
0,0,4,1,5
0,0,8,8,5

[66]-3-up--
9,6,2,2,↑
7,6,*,1,3
0,0,4,1,5
0,0,8,8,5

[67]-4-up--
9,6,2,2,3
7,6,↑,1,*
0,0,4,1,5
0,0,8,8,5

[68]-5-up--
9,6,2,2,3
7,6,4,1,↑
0,0,*,1,5
0,0,8,8,5

[69]-8-right--
9,6,2,2,3
7,6,4,1,5
0,0,*,1,5
0,0,8,8,→

[70]-0-right--
9,6,2,2,3
7,6,4,1,5
0,0,→,1,5
0,0,*,8,8

[71]-7-down--
9,6,2,2,3
7,6,4,1,5
↓,0,0,1,5
*,0,0,8,8

[72]-7-down--
9,6,2,2,3
*,6,4,1,5
7,0,0,1,5
↓,0,0,8,8

[73]-9-down--
9,6,2,2,3
↓,6,4,1,5
*,0,0,1,5
7,0,0,8,8

[74]-9-down--
*,6,2,2,3
9,6,4,1,5
↓,0,0,1,5
7,0,0,8,8

[75]-6-left--
←,6,2,2,3
*,6,4,1,5
9,0,0,1,5
7,0,0,8,8

[76]-4-left--
6,*,2,2,3
6,←,4,1,5
9,0,0,1,5
7,0,0,8,8

[77]-4-up--
6,↑,2,2,3
6,4,*,1,5
9,0,0,1,5
7,0,0,8,8

[78]-0-up--
6,4,2,2,3
6,↑,*,1,5
9,0,0,1,5
7,0,0,8,8

[79]-7-right--
6,4,2,2,3
6,0,0,1,5
9,0,0,1,5
7,→,*,8,8

[80]-9-down--
6,4,2,2,3
6,0,0,1,5
9,0,0,1,5
↓,7,*,8,8

[81]-7-right--
6,4,2,2,3
6,0,0,1,5
*,0,0,1,5
9,7,→,8,8

[82]-9-right--
6,4,2,2,3
6,0,0,1,5
*,0,0,1,5
9,→,7,8,8

[83]-6-down--
6,4,2,2,3
6,0,0,1,5
↓,0,0,1,5
*,9,7,8,8

[84]-6-down--
*,4,2,2,3
6,0,0,1,5
6,0,0,1,5
↓,9,7,8,8

[85]-4-left--
←,4,2,2,3
*,0,0,1,5
6,0,0,1,5
6,9,7,8,8

[86]-4-down--
4,*,2,2,3
↓,0,0,1,5
6,0,0,1,5
6,9,7,8,8

[87]-2-left--
*,←,2,2,3
4,0,0,1,5
6,0,0,1,5
6,9,7,8,8

[88]-2-left--
←,2,2,*,3
4,0,0,1,5
6,0,0,1,5
6,9,7,8,8

[89]-3-left--
2,2,*,←,3
4,0,0,1,5
6,0,0,1,5
6,9,7,8,8

[90]-5-up--
2,2,*,3,↑
4,0,0,1,5
6,0,0,1,5
6,9,7,8,8

[91]-3-left--
2,2,←,3,5
4,0,0,1,5
6,0,0,1,*
6,9,7,8,8

[92]-1-up--
2,2,3,↑,5
4,0,0,1,5
6,0,0,1,*
6,9,7,8,8

[93]-8-up--
2,2,3,1,5
4,0,0,1,5
6,0,0,↑,*
6,9,7,8,8

[94]-7-right--
2,2,3,1,5
4,0,0,1,5
6,0,0,8,8
6,9,7,→,*

[95]-9-right--
2,2,3,1,5
4,0,0,1,5
6,0,0,8,8
6,9,→,7,*

[96]-7-right--
2,2,3,1,5
4,0,0,1,5
6,0,0,8,8
6,*,9,7,→

[97]-9-right--
2,2,3,1,5
4,0,0,1,5
6,0,0,8,8
6,*,9,→,7

[98]-0-down--
2,2,3,1,5
4,0,0,1,5
6,0,0,8,8
6,↓,*,9,7

[99]-4-right--
2,2,3,1,5
4,→,*,1,5
6,0,0,8,8
6,0,0,9,7

[100]-6-up--
2,2,3,1,5
↑,4,*,1,5
6,0,0,8,8
6,0,0,9,7

[101]-3-down--
2,2,3,1,5
6,4,↓,1,5
6,0,0,8,8
*,0,0,9,7

[102]-2-right--
2,2,→,1,5
6,4,3,1,5
6,0,0,8,8
*,0,0,9,7

[103]-6-up--
↑,2,2,1,5
6,4,3,1,5
6,0,0,8,8
*,0,0,9,7

[104]-0-left--
6,2,2,1,5
6,4,3,1,5
←,0,0,8,8
*,0,0,9,7

[105]-9-left--
6,2,2,1,5
6,4,3,1,5
0,0,*,8,8
0,0,←,9,7

[106]-8-left--
6,2,2,1,5
6,4,3,1,5
0,0,←,8,8
0,0,9,*,7

[107]-7-left--
6,2,2,1,5
6,4,3,1,5
0,0,8,8,*
0,0,9,←,7

[108]-5-down--
6,2,2,1,5
6,4,3,1,5
0,0,8,8,↓
0,0,9,7,*

[109]-5-down--
6,2,2,1,*
6,4,3,1,5
0,0,8,8,5
0,0,9,7,↓

[110]-1-right--
6,2,2,1,→
6,4,3,1,*
0,0,8,8,5
0,0,9,7,5

[111]-2-right--
6,2,2,→,1
6,4,3,*,1
0,0,8,8,5
0,0,9,7,5

[112]-4-up--
6,↑,2,2,1
6,4,3,*,1
0,0,8,8,5
0,0,9,7,5

[113]-3-left--
6,4,2,2,1
6,←,3,*,1
0,0,8,8,5
0,0,9,7,5

[114]-8-up--
6,4,2,2,1
6,3,↑,*,1
0,0,8,8,5
0,0,9,7,5

[115]-7-up--
6,4,2,2,1
6,3,8,8,1
0,0,*,↑,5
0,0,9,7,5

[116]-9-right--
6,4,2,2,1
6,3,8,8,1
0,0,*,7,5
0,0,9,→,5

[117]-0-right--
6,4,2,2,1
6,3,8,8,1
0,0,→,7,5
0,0,*,9,5

[118]-6-down--
6,4,2,2,1
6,3,8,8,1
↓,0,0,7,5
*,0,0,9,5

[119]-6-down--
*,4,2,2,1
6,3,8,8,1
6,0,0,7,5
↓,0,0,9,5

[120]-4-left--
←,4,2,2,1
*,3,8,8,1
6,0,0,7,5
6,0,0,9,5

[121]-2-left--
4,←,2,2,1
*,3,8,8,1
6,0,0,7,5
6,0,0,9,5

[122]-3-left--
4,2,2,*,1
←,3,8,8,1
6,0,0,7,5
6,0,0,9,5

[123]-8-left--
4,2,2,*,1
3,←,8,8,1
6,0,0,7,5
6,0,0,9,5

[124]-7-up--
4,2,2,*,1
3,8,8,↑,1
6,0,0,7,5
6,0,0,9,5

[125]-7-up--
4,2,2,↑,1
3,8,8,7,1
6,0,0,*,5
6,0,0,9,5

[126]-9-up--
4,2,2,7,1
3,8,8,*,1
6,0,0,↑,5
6,0,0,9,5

[127]-9-up--
4,2,2,7,1
3,8,8,↑,1
6,0,0,9,5
6,0,0,*,5

[128]-5-left--
4,2,2,7,1
3,8,8,9,1
6,0,0,←,5
6,0,0,*,5

[129]-1-down--
4,2,2,7,1
3,8,8,9,1
6,0,0,5,↓
6,0,0,5,*

[130]-1-down--
4,2,2,7,*
3,8,8,9,1
6,0,0,5,1
6,0,0,5,↓

[131]-9-right--
4,2,2,7,*
3,8,8,9,→
6,0,0,5,1
6,0,0,5,1

[132]-5-up--
4,2,2,7,*
3,8,8,↑,9
6,0,0,5,1
6,0,0,5,1

[133]-7-right--
4,2,2,7,→
3,8,8,5,9
6,0,0,5,1
6,0,0,*,1

[134]-5-up--
4,2,2,↑,7
3,8,8,5,9
6,0,0,5,1
6,0,0,*,1

[135]-0-right--
4,2,2,5,7
3,8,8,5,9
6,0,0,→,1
6,0,0,*,1

[136]-6-right--
4,2,2,5,7
3,8,8,5,9
6,→,0,0,1
6,*,0,0,1

[137]-3-down--
4,2,2,5,7
3,8,8,5,9
↓,6,0,0,1
*,6,0,0,1

[138]-4-down--
4,2,2,5,7
↓,8,8,5,9
3,6,0,0,1
*,6,0,0,1

[139]-3-down--
*,2,2,5,7
4,8,8,5,9
3,6,0,0,1
↓,6,0,0,1

[140]-4-down--
*,2,2,5,7
4,8,8,5,9
↓,6,0,0,1
3,6,0,0,1

[141]-8-left--
*,2,2,5,7
←,8,8,5,9
4,6,0,0,1
3,6,0,0,1

[142]-2-left--
←,2,2,5,7
8,8,*,5,9
4,6,0,0,1
3,6,0,0,1

[143]-5-left--
2,2,←,5,7
8,8,*,5,9
4,6,0,0,1
3,6,0,0,1

[144]-9-left--
2,2,5,*,7
8,8,5,←,9
4,6,0,0,1
3,6,0,0,1

[145]-7-left--
2,2,5,←,7
8,8,5,9,*
4,6,0,0,1
3,6,0,0,1

[146]-1-up--
2,2,5,7,*
8,8,5,9,↑
4,6,0,0,1
3,6,0,0,1

[147]-1-up--
2,2,5,7,↑
8,8,5,9,1
4,6,0,0,1
3,6,0,0,*

[148]-0-right--
2,2,5,7,1
8,8,5,9,1
4,6,0,0,→
3,6,0,0,*

[149]-5-down--
2,2,5,7,1
8,8,5,9,1
4,6,↓,0,0
3,6,*,0,0

[150]-5-down--
2,2,*,7,1
8,8,5,9,1
4,6,5,0,0
3,6,↓,0,0

[151]-9-left--
2,2,*,7,1
8,8,←,9,1
4,6,5,0,0
3,6,5,0,0

[152]-2-right--
2,2,→,7,1
8,8,9,*,1
4,6,5,0,0
3,6,5,0,0

[153]-7-down--
*,2,2,7,1
8,8,9,↓,1
4,6,5,0,0
3,6,5,0,0

[154]-2-right--
*,2,2,→,1
8,8,9,7,1
4,6,5,0,0
3,6,5,0,0

[155]-8-up--
↑,*,2,2,1
8,8,9,7,1
4,6,5,0,0
3,6,5,0,0

[156]-9-left--
8,8,2,2,1
*,←,9,7,1
4,6,5,0,0
3,6,5,0,0

[157]-9-left--
8,8,2,2,1
←,9,*,7,1
4,6,5,0,0
3,6,5,0,0

[158]-7-left--
8,8,2,2,1
9,*,←,7,1
4,6,5,0,0
3,6,5,0,0

[159]-7-left--
8,8,2,2,1
9,←,7,*,1
4,6,5,0,0
3,6,5,0,0

[160]-2-down--
8,8,2,2,1
9,7,↓,*,1
4,6,5,0,0
3,6,5,0,0