2

任意のペグソリティアボード構成を考えると、「ゲーム終了」の位置になる一連の動きを計算するための最も効率的な方法は何ですか。

たとえば、標準の開始位置は次のとおりです。

..***..
..***..
*******
***O***
*******
..***..
..***..

そして、「ゲーム終了」の位置は次のとおりです。

..OOO..
..OOO..
OOOOOOO
OOO*OOO
OOOOOOO
..OOO..
..OOO..

ペグソリテールについて詳しくは、ウィキペディアをご覧ください。「英語ボード」のバリエーションを検討しています。

P4 3Ghzのように、妥当なコンピューター上で、わずか数秒で任意の開始ボードを解決できると確信しています。

現在、これが私の最善の戦略です。

def solve:
    for every possible move:
        make the move.
        if we haven't seen a rotation or flip of this board before:
            solve()
            if solved: return
        undo the move.
4

2 に答える 2

3

リンク先のウィキペディアの記事には、ボードの位置が3,626,632しかないことがすでに記載されているため、最新のコンピューターでスペースを徹底的に検索するのは簡単です。

上記のアルゴリズムは正しいです。トリックは、ハッシュテーブルを使用して実行できる「このボードの回転または反転をこれまでに見たことがない」を実装することです。実際の実装では、ボードの状態が再帰呼び出しの引数として渡されるため、「移動を元に戻す」行はおそらく必要ありません。そのため、状態を格納するためにスタックを使用します。

また、「効率的」とはどういう意味かは明確ではありません。

勝利ステージにつながるすべての一連の動きを見つけたい場合は、徹底的な検索を行う必要があります。

最短のシーケンスを見つけたい場合は、分枝限定アルゴリズムを使用して、いくつかの検索ツリーを早い段階で切り取ることができます。優れた静的ヒューリスティックを思い付くことができる場合は、A*またはそのバリアントの1つを試すことができます。

于 2010-09-01T20:17:19.267 に答える
0

完了した状態から開始し、時間をさかのぼって歩きます。各動きは、ボードに追加のペグを残すホップです。

すべての時点で、複数のアンムーブを実行できる可能性があるため、ムーブのツリーを生成します。そのツリーをトラバースして（深さ優先または幅のいずれか）、開始状態に達したとき、または移動の可能性がなくなったときにブランチを停止します。元の開始状態に至ったパスのリストを出力します。

于 2010-09-02T01:38:39.520 に答える