The Fool In The Valleyの雑記帳

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

箱入り娘を解く その5

プログラムを実行

プログラムができたので実行させてみました。
最初の課題はオーソドックスな(1)の左の配置を初期状態とするものです。プログラムの中では、それを右のように数字で取り扱います。

下は得られた解法のステップを盤面を2次元arrayの形で表現して一覧できるようにしたものです。計算時間は2.56秒で、92手で解けています。

下はそれを拡大したもので、スクロールすると盤面の変化を一手ずつ確認することができます。

0 ****************
[[2 1 1 3]
[2 1 1 3]
[4 6 6 5]
[4 7 7 5]
[7 0 0 7]]
1 ****************
[[2 1 1 3]
[2 1 1 3]
[4 6 6 5]
[4 0 7 5]
[7 7 0 7]]
2 ****************
[[2 1 1 3]
[2 1 1 3]
[4 6 6 5]
[4 0 7 5]
[7 7 7 0]]
3 ****************
[[2 1 1 3]
[2 1 1 3]
[4 6 6 0]
[4 0 7 5]
[7 7 7 5]]
4 ****************
[[2 1 1 3]
[2 1 1 3]
[4 0 6 6]
[4 0 7 5]
[7 7 7 5]]
5 ****************
[[2 1 1 3]
[2 1 1 3]
[0 4 6 6]
[0 4 7 5]
[7 7 7 5]]
6 ****************
[[2 1 1 3]
[2 1 1 3]
[7 4 6 6]
[0 4 7 5]
[0 7 7 5]]
7 ****************
[[2 1 1 3]
[2 1 1 3]
[7 4 6 6]
[0 4 7 5]
[7 0 7 5]]
8 ****************
[[2 1 1 3]
[2 1 1 3]
[7 0 6 6]
[0 4 7 5]
[7 4 7 5]]
9 ****************
[[2 1 1 3]
[2 1 1 3]
[7 6 6 0]
[0 4 7 5]
[7 4 7 5]]
10 ****************
[[2 1 1 3]
[2 1 1 3]
[0 6 6 0]
[7 4 7 5]
[7 4 7 5]]
11 ****************
[[2 1 1 3]
[2 1 1 3]
[6 6 0 0]
[7 4 7 5]
[7 4 7 5]]
12 ****************
[[2 1 1 3]
[2 1 1 3]
[6 6 7 0]
[7 4 0 5]
[7 4 7 5]]
13 ****************
[[2 1 1 3]
[2 1 1 3]
[6 6 0 7]
[7 4 0 5]
[7 4 7 5]]
14 ****************
[[2 1 1 3]
[2 1 1 3]
[6 6 7 7]
[7 4 0 5]
[7 4 0 5]]
15 ****************
[[2 1 1 3]
[2 1 1 3]
[6 6 7 7]
[7 0 4 5]
[7 0 4 5]]
16 ****************
[[2 1 1 3]
[2 1 1 3]
[6 6 7 7]
[0 7 4 5]
[7 0 4 5]]
17 ****************
[[2 1 1 3]
[2 1 1 3]
[6 6 7 7]
[0 0 4 5]
[7 7 4 5]]
18 ****************
[[2 1 1 3]
[2 1 1 3]
[0 0 7 7]
[6 6 4 5]
[7 7 4 5]]
19 ****************
[[2 1 1 3]
[2 1 1 3]
[7 0 0 7]
[6 6 4 5]
[7 7 4 5]]
20 ****************
[[2 1 1 3]
[2 1 1 3]
[7 7 0 0]
[6 6 4 5]
[7 7 4 5]]
21 ****************
[[2 1 1 3]
[2 1 1 3]
[7 7 4 0]
[6 6 4 5]
[7 7 0 5]]
22 ****************
[[2 1 1 3]
[2 1 1 3]
[7 7 4 5]
[6 6 4 5]
[7 7 0 0]]
23 ****************
[[2 1 1 3]
[2 1 1 3]
[7 7 4 5]
[6 6 4 5]
[7 0 0 7]]
24 ****************
[[2 1 1 3]
[2 1 1 3]
[7 7 4 5]
[6 6 4 5]
[0 0 7 7]]
25 ****************
[[2 1 1 3]
[2 1 1 3]
[7 7 4 5]
[0 0 4 5]
[6 6 7 7]]
26 ****************
[[2 1 1 3]
[2 1 1 3]
[0 7 4 5]
[7 0 4 5]
[6 6 7 7]]
27 ****************
[[2 1 1 3]
[2 1 1 3]
[7 0 4 5]
[7 0 4 5]
[6 6 7 7]]
28 ****************
[[2 1 1 3]
[2 1 1 3]
[7 4 0 5]
[7 4 0 5]
[6 6 7 7]]
29 ****************
[[2 1 1 3]
[2 1 1 3]
[7 4 5 0]
[7 4 5 0]
[6 6 7 7]]
30 ****************
[[2 1 1 0]
[2 1 1 0]
[7 4 5 3]
[7 4 5 3]
[6 6 7 7]]
31 ****************
[[2 0 1 1]
[2 0 1 1]
[7 4 5 3]
[7 4 5 3]
[6 6 7 7]]
32 ****************
[[0 2 1 1]
[0 2 1 1]
[7 4 5 3]
[7 4 5 3]
[6 6 7 7]]
33 ****************
[[7 2 1 1]
[0 2 1 1]
[0 4 5 3]
[7 4 5 3]
[6 6 7 7]]
34 ****************
[[7 2 1 1]
[7 2 1 1]
[0 4 5 3]
[0 4 5 3]
[6 6 7 7]]
35 ****************
[[7 2 1 1]
[7 2 1 1]
[4 0 5 3]
[4 0 5 3]
[6 6 7 7]]
36 ****************
[[7 0 1 1]
[7 0 1 1]
[4 2 5 3]
[4 2 5 3]
[6 6 7 7]]
37 ****************
[[7 1 1 0]
[7 1 1 0]
[4 2 5 3]
[4 2 5 3]
[6 6 7 7]]
38 ****************
[[7 1 1 3]
[7 1 1 3]
[4 2 5 0]
[4 2 5 0]
[6 6 7 7]]
39 ****************
[[7 1 1 3]
[7 1 1 3]
[4 2 0 5]
[4 2 0 5]
[6 6 7 7]]
40 ****************
[[7 1 1 3]
[7 1 1 3]
[4 2 7 5]
[4 2 0 5]
[6 6 0 7]]
41 ****************
[[7 1 1 3]
[7 1 1 3]
[4 2 7 5]
[4 2 0 5]
[6 6 7 0]]
42 ****************
[[7 1 1 3]
[7 1 1 3]
[4 2 7 5]
[4 2 7 5]
[6 6 0 0]]
43 ****************
[[7 1 1 3]
[7 1 1 3]
[4 2 7 5]
[4 2 7 5]
[0 0 6 6]]
44 ****************
[[7 1 1 3]
[7 1 1 3]
[0 2 7 5]
[4 2 7 5]
[4 0 6 6]]
45 ****************
[[7 1 1 3]
[7 1 1 3]
[0 0 7 5]
[4 2 7 5]
[4 2 6 6]]
46 ****************
[[7 1 1 3]
[7 1 1 3]
[7 0 0 5]
[4 2 7 5]
[4 2 6 6]]
47 ****************
[[7 0 0 3]
[7 1 1 3]
[7 1 1 5]
[4 2 7 5]
[4 2 6 6]]
48 ****************
[[0 0 7 3]
[7 1 1 3]
[7 1 1 5]
[4 2 7 5]
[4 2 6 6]]
49 ****************
[[7 0 7 3]
[0 1 1 3]
[7 1 1 5]
[4 2 7 5]
[4 2 6 6]]
50 ****************
[[0 7 7 3]
[0 1 1 3]
[7 1 1 5]
[4 2 7 5]
[4 2 6 6]]
51 ****************
[[7 7 7 3]
[0 1 1 3]
[0 1 1 5]
[4 2 7 5]
[4 2 6 6]]
52 ****************
[[7 7 7 3]
[4 1 1 3]
[4 1 1 5]
[0 2 7 5]
[0 2 6 6]]
53 ****************
[[7 7 7 3]
[4 1 1 3]
[4 1 1 5]
[2 0 7 5]
[2 0 6 6]]
54 ****************
[[7 7 7 3]
[4 1 1 3]
[4 1 1 5]
[2 7 0 5]
[2 0 6 6]]
55 ****************
[[7 7 7 3]
[4 1 1 3]
[4 1 1 5]
[2 0 0 5]
[2 7 6 6]]
56 ****************
[[7 7 7 3]
[4 0 0 3]
[4 1 1 5]
[2 1 1 5]
[2 7 6 6]]
57 ****************
[[7 0 7 3]
[4 7 0 3]
[4 1 1 5]
[2 1 1 5]
[2 7 6 6]]
58 ****************
[[7 7 0 3]
[4 7 0 3]
[4 1 1 5]
[2 1 1 5]
[2 7 6 6]]
59 ****************
[[7 7 3 0]
[4 7 3 0]
[4 1 1 5]
[2 1 1 5]
[2 7 6 6]]
60 ****************
[[7 7 3 5]
[4 7 3 5]
[4 1 1 0]
[2 1 1 0]
[2 7 6 6]]
61 ****************
[[7 7 3 5]
[4 7 3 5]
[4 0 1 1]
[2 0 1 1]
[2 7 6 6]]
62 ****************
[[7 7 3 5]
[4 0 3 5]
[4 7 1 1]
[2 0 1 1]
[2 7 6 6]]
63 ****************
[[7 0 3 5]
[4 7 3 5]
[4 7 1 1]
[2 0 1 1]
[2 7 6 6]]
64 ****************
[[0 7 3 5]
[4 7 3 5]
[4 7 1 1]
[2 0 1 1]
[2 7 6 6]]
65 ****************
[[4 7 3 5]
[4 7 3 5]
[0 7 1 1]
[2 0 1 1]
[2 7 6 6]]
66 ****************
[[4 7 3 5]
[4 7 3 5]
[2 7 1 1]
[2 0 1 1]
[0 7 6 6]]
67 ****************
[[4 7 3 5]
[4 7 3 5]
[2 7 1 1]
[2 0 1 1]
[7 0 6 6]]
68 ****************
[[4 7 3 5]
[4 7 3 5]
[2 0 1 1]
[2 0 1 1]
[7 7 6 6]]
69 ****************
[[4 7 3 5]
[4 7 3 5]
[2 1 1 0]
[2 1 1 0]
[7 7 6 6]]
70 ****************
[[4 7 3 0]
[4 7 3 0]
[2 1 1 5]
[2 1 1 5]
[7 7 6 6]]
71 ****************
[[4 7 0 3]
[4 7 0 3]
[2 1 1 5]
[2 1 1 5]
[7 7 6 6]]
72 ****************
[[4 0 7 3]
[4 7 0 3]
[2 1 1 5]
[2 1 1 5]
[7 7 6 6]]
73 ****************
[[4 0 7 3]
[4 0 7 3]
[2 1 1 5]
[2 1 1 5]
[7 7 6 6]]
74 ****************
[[0 4 7 3]
[0 4 7 3]
[2 1 1 5]
[2 1 1 5]
[7 7 6 6]]
75 ****************
[[2 4 7 3]
[2 4 7 3]
[0 1 1 5]
[0 1 1 5]
[7 7 6 6]]
76 ****************
[[2 4 7 3]
[2 4 7 3]
[1 1 0 5]
[1 1 0 5]
[7 7 6 6]]
77 ****************
[[2 4 7 3]
[2 4 0 3]
[1 1 0 5]
[1 1 7 5]
[7 7 6 6]]
78 ****************
[[2 4 0 3]
[2 4 0 3]
[1 1 7 5]
[1 1 7 5]
[7 7 6 6]]
79 ****************
[[2 4 3 0]
[2 4 3 0]
[1 1 7 5]
[1 1 7 5]
[7 7 6 6]]
80 ****************
[[2 4 3 5]
[2 4 3 5]
[1 1 7 0]
[1 1 7 0]
[7 7 6 6]]
81 ****************
[[2 4 3 5]
[2 4 3 5]
[1 1 0 7]
[1 1 7 0]
[7 7 6 6]]
82 ****************
[[2 4 3 5]
[2 4 3 5]
[1 1 7 7]
[1 1 0 0]
[7 7 6 6]]
83 ****************
[[2 4 3 5]
[2 4 3 5]
[1 1 7 7]
[1 1 6 6]
[7 7 0 0]]
84 ****************
[[2 4 3 5]
[2 4 3 5]
[1 1 7 7]
[1 1 6 6]
[7 0 0 7]]
85 ****************
[[2 4 3 5]
[2 4 3 5]
[1 1 7 7]
[1 1 6 6]
[0 0 7 7]]
86 ****************
[[2 4 3 5]
[2 4 3 5]
[0 0 7 7]
[1 1 6 6]
[1 1 7 7]]
87 ****************
[[2 4 3 5]
[2 4 3 5]
[7 0 0 7]
[1 1 6 6]
[1 1 7 7]]
88 ****************
[[2 4 3 5]
[2 4 3 5]
[7 7 0 0]
[1 1 6 6]
[1 1 7 7]]
89 ****************
[[2 4 3 5]
[2 4 3 5]
[7 7 6 6]
[1 1 0 0]
[1 1 7 7]]
90 ****************
[[2 4 3 5]
[2 4 3 5]
[7 7 6 6]
[1 1 7 0]
[1 1 0 7]]
91 ****************
[[2 4 3 5]
[2 4 3 5]
[7 7 6 6]
[1 1 0 7]
[1 1 0 7]]
92 ****************
[[2 4 3 5]
[2 4 3 5]
[7 7 6 6]
[0 1 1 7]
[0 1 1 7]]

Treeを横型探索するとき、nodeの数はlevelが上がると増えていくはずですが、重複する盤面のnodeを作らないようにしているので、その数が爆破することはないはずです。具体的にどのくらいになっているかを調べてみたら下の様になっていました。

node number of layer 0 is 1
node number of layer 1 is 6
node number of layer 2 is 12
node number of layer 3 is 15
node number of layer 4 is 18
node number of layer 5 is 16
node number of layer 6 is 21
node number of layer 7 is 18
node number of layer 8 is 30
node number of layer 9 is 38
node number of layer 10 is 46
node number of layer 11 is 41
node number of layer 12 is 40
node number of layer 13 is 37
node number of layer 14 is 42
node number of layer 15 is 35
node number of layer 16 is 32
node number of layer 17 is 45
node number of layer 18 is 50
node number of layer 19 is 67
node number of layer 20 is 61
node number of layer 21 is 75
node number of layer 22 is 60
node number of layer 23 is 55
node number of layer 24 is 48
node number of layer 25 is 64
node number of layer 26 is 86
node number of layer 27 is 98
node number of layer 28 is 90
node number of layer 29 is 100
node number of layer 30 is 134
node number of layer 31 is 142
node number of layer 32 is 169
node number of layer 33 is 207
node number of layer 34 is 258
node number of layer 35 is 330
node number of layer 36 is 386
node number of layer 37 is 439
node number of layer 38 is 480
node number of layer 39 is 496
node number of layer 40 is 539
node number of layer 41 is 573
node number of layer 42 is 607
node number of layer 43 is 655
node number of layer 44 is 691
node number of layer 45 is 805
node number of layer 46 is 877
node number of layer 47 is 948
node number of layer 48 is 951
node number of layer 49 is 840
node number of layer 50 is 720
node number of layer 51 is 636
node number of layer 52 is 595
node number of layer 53 is 554
node number of layer 54 is 529
node number of layer 55 is 468
node number of layer 56 is 423
node number of layer 57 is 360
node number of layer 58 is 315
node number of layer 59 is 263
node number of layer 60 is 193
node number of layer 61 is 151
node number of layer 62 is 109
node number of layer 63 is 101
node number of layer 64 is 96
node number of layer 65 is 98
node number of layer 66 is 100
node number of layer 67 is 116
node number of layer 68 is 124
node number of layer 69 is 127
node number of layer 70 is 127
node number of layer 71 is 141
node number of layer 72 is 158
node number of layer 73 is 198
node number of layer 74 is 222
node number of layer 75 is 228
node number of layer 76 is 245
node number of layer 77 is 275
node number of layer 78 is 301
node number of layer 79 is 343
node number of layer 80 is 362
node number of layer 81 is 351
node number of layer 82 is 321
node number of layer 83 is 311
node number of layer 84 is 285
node number of layer 85 is 267
node number of layer 86 is 245
node number of layer 87 is 212
node number of layer 88 is 193
node number of layer 89 is 185
node number of layer 90 is 184
node number of layer 91 is 167
node number of layer 92 is 64

グラフで書くとこういう形になります。解が得られるまでのlevelごとのnode数の最大値は951で、nodeの総数は23,273個です。数の爆発は起こらないにしても、これだけの数を人間の頭で追いかけるのはやめた方がよさそうです。

Webで検索するとこの初期状態から85手でできると書かれているサイトがあるのですが、そのサイトでは、下図(あ)のように一つのタイルを連続的にかぎ型に動かす場合を1手と数えています。私の解法では、それを(い)のように2手と数えているのでその差が出ているようです。


任意の盤面に対応できることを確認するために、別の例として、下の(2)のように置いた盤面からスタートさせてみました。

その結果は以下の通りです。計算時間は2.33秒で、66手で解けています。小さな7のタイルを利用して大きな2,3,4,5のタイルを上部に持っていくのが解法の筋でもあるので、7が最初から上部にあると手数が少なくて済むのでしょう。

0 ****************
[[1 1 7 7]
[1 1 2 4]
[3 5 2 4]
[3 5 6 6]
[0 7 7 0]]
1 ****************
[[1 1 7 7]
[1 1 2 4]
[3 5 2 4]
[3 5 6 6]
[7 0 7 0]]
2 ****************
[[1 1 7 7]
[1 1 2 4]
[3 5 2 4]
[3 5 6 6]
[7 7 0 0]]
3 ****************
[[1 1 7 7]
[1 1 2 4]
[3 5 2 4]
[3 5 0 0]
[7 7 6 6]]
4 ****************
[[1 1 7 7]
[1 1 0 4]
[3 5 2 4]
[3 5 2 0]
[7 7 6 6]]
5 ****************
[[1 1 0 7]
[1 1 7 4]
[3 5 2 4]
[3 5 2 0]
[7 7 6 6]]
6 ****************
[[1 1 0 7]
[1 1 7 0]
[3 5 2 4]
[3 5 2 4]
[7 7 6 6]]
7 ****************
[[1 1 0 7]
[1 1 0 7]
[3 5 2 4]
[3 5 2 4]
[7 7 6 6]]
8 ****************
[[0 1 1 7]
[0 1 1 7]
[3 5 2 4]
[3 5 2 4]
[7 7 6 6]]
9 ****************
[[3 1 1 7]
[3 1 1 7]
[0 5 2 4]
[0 5 2 4]
[7 7 6 6]]
10 ****************
[[3 1 1 7]
[3 1 1 7]
[5 0 2 4]
[5 0 2 4]
[7 7 6 6]]
11 ****************
[[3 1 1 7]
[3 1 1 7]
[5 7 2 4]
[5 0 2 4]
[7 0 6 6]]
12 ****************
[[3 1 1 7]
[3 1 1 7]
[5 7 2 4]
[5 0 2 4]
[0 7 6 6]]
13 ****************
[[3 1 1 7]
[3 1 1 7]
[5 7 2 4]
[5 7 2 4]
[0 0 6 6]]
14 ****************
[[3 1 1 7]
[3 1 1 7]
[0 7 2 4]
[5 7 2 4]
[5 0 6 6]]
15 ****************
[[3 1 1 7]
[3 1 1 7]
[0 7 2 4]
[5 7 2 4]
[5 6 6 0]]
16 ****************
[[3 1 1 7]
[3 1 1 7]
[5 7 2 4]
[5 7 2 4]
[0 6 6 0]]
17 ****************
[[3 1 1 7]
[3 1 1 7]
[5 7 2 0]
[5 7 2 4]
[0 6 6 4]]
18 ****************
[[3 1 1 7]
[3 1 1 7]
[5 7 2 0]
[5 7 2 4]
[6 6 0 4]]
19 ****************
[[3 1 1 7]
[3 1 1 7]
[5 7 0 0]
[5 7 2 4]
[6 6 2 4]]
20 ****************
[[3 1 1 7]
[3 1 1 7]
[5 0 0 7]
[5 7 2 4]
[6 6 2 4]]
21 ****************
[[3 0 0 7]
[3 1 1 7]
[5 1 1 7]
[5 7 2 4]
[6 6 2 4]]
22 ****************
[[3 7 0 0]
[3 1 1 7]
[5 1 1 7]
[5 7 2 4]
[6 6 2 4]]
23 ****************
[[3 7 0 7]
[3 1 1 0]
[5 1 1 7]
[5 7 2 4]
[6 6 2 4]]
24 ****************
[[3 7 7 0]
[3 1 1 0]
[5 1 1 7]
[5 7 2 4]
[6 6 2 4]]
25 ****************
[[3 7 7 7]
[3 1 1 0]
[5 1 1 0]
[5 7 2 4]
[6 6 2 4]]
26 ****************
[[3 7 7 7]
[3 1 1 4]
[5 1 1 4]
[5 7 2 0]
[6 6 2 0]]
27 ****************
[[3 7 7 7]
[3 1 1 4]
[5 1 1 4]
[5 7 0 2]
[6 6 0 2]]
28 ****************
[[3 7 7 7]
[3 1 1 4]
[5 1 1 4]
[5 0 7 2]
[6 6 0 2]]
29 ****************
[[3 7 7 7]
[3 1 1 4]
[5 1 1 4]
[5 0 0 2]
[6 6 7 2]]
30 ****************
[[3 7 7 7]
[3 0 0 4]
[5 1 1 4]
[5 1 1 2]
[6 6 7 2]]
31 ****************
[[3 0 7 7]
[3 7 0 4]
[5 1 1 4]
[5 1 1 2]
[6 6 7 2]]
32 ****************
[[3 0 7 7]
[3 0 7 4]
[5 1 1 4]
[5 1 1 2]
[6 6 7 2]]
33 ****************
[[0 3 7 7]
[0 3 7 4]
[5 1 1 4]
[5 1 1 2]
[6 6 7 2]]
34 ****************
[[5 3 7 7]
[5 3 7 4]
[0 1 1 4]
[0 1 1 2]
[6 6 7 2]]
35 ****************
[[5 3 7 7]
[5 3 7 4]
[1 1 0 4]
[1 1 0 2]
[6 6 7 2]]
36 ****************
[[5 3 7 7]
[5 3 0 4]
[1 1 7 4]
[1 1 0 2]
[6 6 7 2]]
37 ****************
[[5 3 0 7]
[5 3 7 4]
[1 1 7 4]
[1 1 0 2]
[6 6 7 2]]
38 ****************
[[5 3 7 0]
[5 3 7 4]
[1 1 7 4]
[1 1 0 2]
[6 6 7 2]]
39 ****************
[[5 3 7 4]
[5 3 7 4]
[1 1 7 0]
[1 1 0 2]
[6 6 7 2]]
40 ****************
[[5 3 7 4]
[5 3 7 4]
[1 1 7 2]
[1 1 0 2]
[6 6 7 0]]
41 ****************
[[5 3 7 4]
[5 3 7 4]
[1 1 7 2]
[1 1 0 2]
[6 6 0 7]]
42 ****************
[[5 3 7 4]
[5 3 7 4]
[1 1 0 2]
[1 1 0 2]
[6 6 7 7]]
43 ****************
[[5 3 7 4]
[5 3 7 4]
[0 1 1 2]
[0 1 1 2]
[6 6 7 7]]
44 ****************
[[0 3 7 4]
[0 3 7 4]
[5 1 1 2]
[5 1 1 2]
[6 6 7 7]]
45 ****************
[[3 0 7 4]
[3 0 7 4]
[5 1 1 2]
[5 1 1 2]
[6 6 7 7]]
46 ****************
[[3 7 0 4]
[3 0 7 4]
[5 1 1 2]
[5 1 1 2]
[6 6 7 7]]
47 ****************
[[3 7 0 4]
[3 7 0 4]
[5 1 1 2]
[5 1 1 2]
[6 6 7 7]]
48 ****************
[[3 7 4 0]
[3 7 4 0]
[5 1 1 2]
[5 1 1 2]
[6 6 7 7]]
49 ****************
[[3 7 4 2]
[3 7 4 2]
[5 1 1 0]
[5 1 1 0]
[6 6 7 7]]
50 ****************
[[3 7 4 2]
[3 7 4 2]
[5 0 1 1]
[5 0 1 1]
[6 6 7 7]]
51 ****************
[[3 7 4 2]
[3 0 4 2]
[5 0 1 1]
[5 7 1 1]
[6 6 7 7]]
52 ****************
[[3 0 4 2]
[3 0 4 2]
[5 7 1 1]
[5 7 1 1]
[6 6 7 7]]
53 ****************
[[0 3 4 2]
[0 3 4 2]
[5 7 1 1]
[5 7 1 1]
[6 6 7 7]]
54 ****************
[[5 3 4 2]
[5 3 4 2]
[0 7 1 1]
[0 7 1 1]
[6 6 7 7]]
55 ****************
[[5 3 4 2]
[5 3 4 2]
[7 0 1 1]
[0 7 1 1]
[6 6 7 7]]
56 ****************
[[5 3 4 2]
[5 3 4 2]
[7 7 1 1]
[0 0 1 1]
[6 6 7 7]]
57 ****************
[[5 3 4 2]
[5 3 4 2]
[7 7 1 1]
[6 6 1 1]
[0 0 7 7]]
58 ****************
[[5 3 4 2]
[5 3 4 2]
[7 7 1 1]
[6 6 1 1]
[7 0 0 7]]
59 ****************
[[5 3 4 2]
[5 3 4 2]
[7 7 1 1]
[6 6 1 1]
[7 7 0 0]]
60 ****************
[[5 3 4 2]
[5 3 4 2]
[7 7 0 0]
[6 6 1 1]
[7 7 1 1]]
61 ****************
[[5 3 4 2]
[5 3 4 2]
[7 0 0 7]
[6 6 1 1]
[7 7 1 1]]
62 ****************
[[5 3 4 2]
[5 3 4 2]
[0 0 7 7]
[6 6 1 1]
[7 7 1 1]]
63 ****************
[[5 3 4 2]
[5 3 4 2]
[6 6 7 7]
[0 0 1 1]
[7 7 1 1]]
64 ****************
[[5 3 4 2]
[5 3 4 2]
[6 6 7 7]
[7 0 1 1]
[0 7 1 1]]
65 ****************
[[5 3 4 2]
[5 3 4 2]
[6 6 7 7]
[7 0 1 1]
[7 0 1 1]]
66 ****************
[[5 3 4 2]
[5 3 4 2]
[6 6 7 7]
[7 1 1 0]
[7 1 1 0]]

ただし、(3)様に最初から7を全部上辺に置いてしまった場合は、動かせるタイルが無くなってすぐに行き詰ってしまいます。小回りの利く小僧さんがあちこちにいない場合はどうやってもできないのです。どのような初期盤面からでも解けるというわけではありません。

(4)のように厄介な番頭さんが邪魔をせずに、小僧さんも上下に分かれている盤面からスタートさせると、わずか13手(12手)で解けてしまいます。計算には0.13秒しかかかっていません。

0 ****************
[[7 6 6 7]
[3 1 1 4]
[3 1 1 4]
[2 7 7 5]
[2 0 0 5]]
1 ****************
[[7 6 6 7]
[3 1 1 4]
[3 1 1 4]
[2 0 7 5]
[2 7 0 5]]
2 ****************
[[7 6 6 7]
[3 1 1 4]
[3 1 1 4]
[2 0 0 5]
[2 7 7 5]]
3 ****************
[[7 6 6 7]
[3 0 0 4]
[3 1 1 4]
[2 1 1 5]
[2 7 7 5]]
4 ****************
[[7 0 0 7]
[3 6 6 4]
[3 1 1 4]
[2 1 1 5]
[2 7 7 5]]
5 ****************
[[0 7 0 7]
[3 6 6 4]
[3 1 1 4]
[2 1 1 5]
[2 7 7 5]]
6 ****************
[[3 7 0 7]
[3 6 6 4]
[0 1 1 4]
[2 1 1 5]
[2 7 7 5]]
7 ****************
[[3 7 0 7]
[3 6 6 4]
[2 1 1 4]
[2 1 1 5]
[0 7 7 5]]
8 ****************
[[3 7 7 0]
[3 6 6 4]
[2 1 1 4]
[2 1 1 5]
[0 7 7 5]]
9 ****************
[[3 7 7 4]
[3 6 6 4]
[2 1 1 0]
[2 1 1 5]
[0 7 7 5]]
10 ****************
[[3 7 7 4]
[3 6 6 4]
[2 1 1 5]
[2 1 1 5]
[0 7 7 0]]
11 ****************
[[3 7 7 4]
[3 6 6 4]
[2 1 1 5]
[2 1 1 5]
[0 7 0 7]]
12 ****************
[[3 7 7 4]
[3 6 6 4]
[2 1 1 5]
[2 1 1 5]
[7 0 0 7]]
13 ****************
[[3 7 7 4]
[3 6 6 4]
[2 0 0 5]
[2 1 1 5]
[7 1 1 7]]

他にも試してみましたが、どうやら問題なさそうです。
解法のステップを求めるプログラムは完成しましたが、数字の列を見せるだけではたいして面白くありません。なにか動いて見せて欲しいところです。最終的にはロボットを使って本物のパズルを操作させたいのですが、それは機械的な不確定要素が絡むので今のところ見通しはついていません。確実にできそうなところで、先ずはグラフィック表示させるのが面白いかなあという気になってきました。
ちょっと考えてみますか・・・・

箱入り娘を解く その4 ⇐