いよいよ超難問#11982へのアプローチをする段階となりました。
DR1の結果をみると、#1941より難しいが解は存在するのではないかという感じがします。
一方では、いままで幾多の人が挑戦して解が得られていないので、解は存在しないのではないかという見方もあります。
従って、上記の両面の可能性を念頭に、
(1)もし解が存在しない場合、存在しないことが明確なアルゴリズムで示せること
(2)解が存在する場合、その解を求める
という方針ですすめることとした。
(解の探索アルゴリズム)
(1)の要請から、非常に単純なアルゴリズムを採用する。即ち、
FreeCellの基本ルール(カード1枚を対象にしたルールの範囲(注1))を、初期局面より、順次適用することにより、すべての局面を展開して最終局面にたどり着けるかどうかを調べる。
注1:複数枚のカードを一括して扱うルールはすべて基本ルールの組み合わせにすぎない
もし、最終局面にたどりつけなければ、解が存在しないという結論を導いたことになる。
最後までたどりつけた場合、逆順(親)にたどっていくことにより、解答手順が判明する。
すべての局面をメモリに常駐するのは困難と思われるので、DR1で採用したクラス分けの概念を使ってM(0),M(1),...M(52)の順に求めていくことにする。
M(m)の定義
M(m):
初期局面からFreeCellの基本ルールを繰り返し適用することによって導くことのできる局面のうち自由度mを持つものの集合
自由度mとは、初期局面とm枚のカードが不一致となる局面((52−m)枚は一致している)
狭義の意味では、M*(m)のseedとなる集合を意味する
M*(m):M(m)の最大集合
狭義のM(m)のすべて局面にFreeCllの基本ルールを繰り返し適用し、飽和状態になったもの。
M*(m)を求める関数をtransitという。
M+(m):M(m+1)のseed集合
M*(m)の各局面に1度だけ基本ルールを適用してえられるM(m+1)である(=seed集合)。
M+(m)を求める関数をtransformという。
M(0):自由度0であり初期局面である。これはM*(0)でもある。
実際のアルゴリズムは
M*(0) −>transform −> M+(0) =M(1)
M(1) −>transit −> M*(1) −> tranform −> M+(1)=M(2)
M(2) −>transit −> M*(2) −> tranform −> M+(2)=M(3)
以下同様となる。
Home |
Up |
Back |
Next |