重複のカードでゲームを解決するための構造/アルゴリズム

Question

タワーソリティア、クライマー、またはフェアウェイソリティアの線に沿ってカードゲームを検討：表が下に他のカードをカバーするかもしれないそれぞれが直ちに利用可能であるカードのいくつかの数で構成され（再生されてからそれらを遮断） 。あなたは一つの「土台」のカードを持っている、そしてそれはあなたの土台カードの上または下に正確に一つのランクだ場合は、テーブルからカードを取り外すことができ、それはあなたの新しい基盤のカードとなり、その時点で。あなたがテーブルからカードをプレイすることができないときから描画するための交換用カードの数が限られているので、あなたは、一般的にカードの最長のシーケンスを再生したいことができます。

まず、どのように解決策を見つけること容易にするために、ボードを表しているのでしょうか？第二に、どのようなアルゴリズムあなたは最長の再生可能なシーケンスを見つけるために使用しますか？

例：

  -4a- -5-
-3-  -2- -4b-

削除されてから上にボトムブロックカード上の

カード：3と2の両方がなくなるまで、あなたが4Aを削除することはできません。最適なプレイがここに、あなたの出発のカードがエースであると仮定すると2、3、4B、5、図4（a）になります。 （あなたは2、3をプレイすることができ、その代わり4A、それは良くないです。）

私は、これは、有向グラフのいくつかの種類として表現されなければならないと仮定します。あなたは3と2から4aにと2および図4bから5までのエッジを持っていると思いますが、一方が他方の後にプレイ可能ですので、あなたも、3〜2及び図4aと5の間のエッジを持っているでしょうか？もしそうなら、彼らは順番（その後、3 3、その後2、または2）のいずれかで再生することができるという事実は、効率的な「最長パス」のアルゴリズムを使用してからあなたを防ぐグラフのサイクルを形成するのでしょうか？ （私はグラフがサイクルが含まれている場合は、グラフ内の最長パスを見つけることNP完全であると信じています。）

Answer 1

あなたは何を（その場で計算された可能性のある次の状態で）ゲームの状態のグラフとしてこれを表している場合 - それは、非常に数多くの可能性があり、ゲームの電位状態（上のストレートDFSのだという意味、ループを持っていません。まだ）開始点から。

Answer 2

ポイントは、ノード完全問題の状態空間を取り込むことになる可能最少のノードと有向非巡回グラフを構築することです。次に、あなたの通常のアルゴリズムを実行することができます。

私は、テーブルに残っているカードの構造の形状に基づいて符号化を示唆している。

一番上のカード -

状態にある第1のデータは、左端のユニークなIDである可能性があります。 （例えば図4（a）のように、それは、唯一のカード4aが存在するという意味で独特です）。形状の残りの部分は、左側に次のカードが同じ「レベル」であるか、それが1つのレベルである場合に記述する利用可能な各カード（採取する準備ができているカード）のために-1,0,1のいずれかで表すことができます。より深い以上。 （このカードがわずか2他のカードと重なり、構造は、あなたが例に与えたもののように見えるという仮定を利用している）。