#−1,#−2の局面



かくしの局面としてwindow 95/NTに存在するこの局面は、非常に作為的なパターンであり、一目見て解が存在しないだろうなと誰もが思うものです。

しかし、解が存在しない事を明に証明したレポートはみあたりません。
(他のパターンで解の存在しない例の証明については前述の通り)

さて、この#−1,#−2の局面のDR1を求めるとどうなるでしょうか?


最後まで計算していくと、ともに無限大(実は−log2(0) )となります。つまり、途中の局面までしか存在できないのです。言い換えると、


#−1,#−2の局面は解が存在しない


ということが証明(?)されてしまうのです。
解の存在しないパターンを論じた論文「An unsolvable instanceofFreeCell」に例示されている局面について同様にDR1もとめると、やはり無限大になります。
(DR1の定義から当然の結果ですが)

では、逆は成り立つであろうか? 解の存在しない局面のDR1は、すべて無限大になるであろうか?

残念ながら、これは成り立ちません。
理論的には、個々の局面の存在は可能でも、局面から次の局面へ遷移させる手順が存在しないため解が存在しない場合が考えられます。(具体例は解っていませんが)


DR1で判定できる解の存在しない局面というのは、かなり粗いレベルかもしれません。まだ、解のない局面の例が少ないのでこれからの調査結果を待ちましょう。


面白そうな 2,3 の局面のDR1計算の詳細データ

mの値

#1

#1941
#11982
#−1
#−2
1 1 1 1 1
8 8 8 8 7
36 36 36 36 35
120 120 120 120 119
192 330 330 302 209
263 605 645 504 367
397 820 813 756 483
7 577 914 728 976 735
8 774 950 579 1379 874
9 1001 918 518 1624 1215
10 1299 929 482 1972 1219
11 1693 969 510 1928 1351
12 2081 1050 496 1940 1163
13 2520 1086 489 1672 1279
14 3026 1082 451 1540 1011
15 3581 1088 393 1192 967
16 4273 1049 389 883 618
17 4997 1061 387 576 503
18 5816 1095 405 336 255
19 6777 1113 433 224 223
20 7971 1196 496 90 89
21 9259 1339 622 64 63
22 10701 1524 744 16 15
23 12377 1713 875 8 7
24 14179 2025 1025 1 0
25 15985 2441 1225 0 0
26 17985 2994 1455 0 0
27 19865 3689 1749 0 0
28 21689 4611 2188 0 0
29 23573 5682 2744 0 0
30 25333 7031 3418 0 0
31 27036 8516 4236 0 0
32 28583 10149 5157 0 0
33 29959 11900 6267 0 0
34 30842 13599 7480 0 0
35 31185 15278 8747 0 0
36 30763 16446 9908 0 0
37 29545 17286 10952 0 0
38 27442 17304 11719 0 0
39 24559 16646 11948 0 0
40 20926 15154 11517 0 0
41 16985 12926 10367 0 0
42 12704 10332 8642 0 0
43 8840 7637 6552 0 0
44 5605 5176 4444 0 0
45 3243 3133 2685 0 0
46 1671 1678 1468 0 0
47 792 790 733 0 0
48 330 330 320 0 0
49 120 120 119 0 0
50 36 36 36 0 0
51 8 8 8 0 0
52 1 1 1 0 0


このデータを最初に見たとき、”そうか#11982は#1941の倍程度の難しさの問題なのか、それなら解が見つからないこともないなぁ”とよろこんだのですが、...


Home
Up
Back
Next