かくしの局面としてwindow 95/NTに存在するこの局面は、非常に作為的なパターンであり、一目見て解が存在しないだろうなと誰もが思うものです。
しかし、解が存在しない事を明に証明したレポートはみあたりません。
(他のパターンで解の存在しない例の証明については前述の通り)
さて、この#−1,#−2の局面のDR1を求めるとどうなるでしょうか?
最後まで計算していくと、ともに無限大(実は−log2(0) )となります。つまり、途中の局面までしか存在できないのです。言い換えると、
ということが証明(?)されてしまうのです。
解の存在しないパターンを論じた論文「An unsolvable instanceofFreeCell」に例示されている局面について同様にDR1もとめると、やはり無限大になります。
(DR1の定義から当然の結果ですが)
では、逆は成り立つであろうか? 解の存在しない局面のDR1は、すべて無限大になるであろうか?
残念ながら、これは成り立ちません。
理論的には、個々の局面の存在は可能でも、局面から次の局面へ遷移させる手順が存在しないため解が存在しない場合が考えられます。(具体例は解っていませんが)
DR1で判定できる解の存在しない局面というのは、かなり粗いレベルかもしれません。まだ、解のない局面の例が少ないのでこれからの調査結果を待ちましょう。
面白そうな 2,3 の局面のDR1計算の詳細データ
mの値 |
#1 |
#1941 |
#11982 |
#−1 |
#−2 |
0 | 1 | 1 | 1 | 1 | 1 |
1 | 8 | 8 | 8 | 8 | 7 |
2 | 36 | 36 | 36 | 36 | 35 |
3 | 120 | 120 | 120 | 120 | 119 |
4 | 192 | 330 | 330 | 302 | 209 |
5 | 263 | 605 | 645 | 504 | 367 |
6 | 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 |