タイルに使用されているレイアウトに関係なく、ゲームの開始時に、パズルを完了してゲームに勝つためのパスが少なくとも 1 つ存在することをユーザーに保証できるように、タイルを分割する良い方法はありますか? ?
明らかに、ユーザーの動きによっては、勝利から切り離される可能性があります。私は、うまくプレイすればパズルに勝てるということを常にユーザーに伝えられるようにしたいだけです。
ゲームの開始時にタイルをランダムに配置すると、ユーザーがいくつかの動きをして、それ以上動けなくなる可能性があります。パズルが少なくとも解決可能であるという知識は、プレイをより楽しくするはずです。
すべてのタイルを逆に配置します (つまり、ボードのレイアウトを真ん中から始めて、うまくいきます)。
プレーヤーをさらにからかうには、目に見える形で非常に高速に行うことができます。
ゲームを逆にプレイします。
ヒープにスライドできる場所に、ピースをペアごとにランダムに配置します。あらかじめ設定されたパターンに一致するヒープを最終的に作成するには、ピースを配置できる場所を知る方法が必要ですが、とにかくそれが必要です。
これは古い質問であることは知っていますが、自分で問題を解決しているときにこれに遭遇しました。ここでの回答はどれも完璧ではなく、いくつかは複雑な注意事項があったり、病的なレイアウトで壊れたりします。これが私の解決策です：
マークのないタイルでボードを (後方ではなく前方に) 解決します。一度に 2 つの空きタイルを削除します。削除する各ペアを「一致したペア」スタックにプッシュします。多くの場合、これだけで十分です。
行き止まり (numFreeTiles == 1) に遭遇した場合は、ジェネレーターをリセットしてください :) 私は通常行き止まりにぶつかることはなく、これまでのところ 10 回程度の最大再試行回数は 3 回であることがわかりました。私が試したレイアウト。8回リトライしたらあきらめて、残りのタイルをランダムに割り当てます。これにより、プレイヤーが失敗して 100% 解決不可能な状態になった場合でも、ボードのセットアップとシャッフル機能の両方に同じジェネレーターを使用できます。
行き止まりになったときのもう 1 つの解決策は、別の道に進むことができるまで後退することです (スタックから飛び出して、ボード上のタイルを交換します)。元のブロック タイルを削除するペアを一致させることで、別の道を進みます。
残念ながら、ボードによっては、これが永遠にループする可能性があります。後続のすべての「道路」が行き止まりであり、複数の行き止まりがある「出口のない」道路に似たペアを削除することになった場合、アルゴリズムは決して完了しません。これが当てはまるボードを設計できるかどうかはわかりませんが、そうであれば解決策はまだあります。
このより大きな問題を解決するには、考えられる各ボード状態を DAG のノードとして扱い、選択した各ペアをそのグラフのエッジにします。深さ 72 でリーフ ノードが見つかるまで、ランダムなトラバーサルを行います。下降を繰り返さないように、トラバーサルの履歴を追跡します。
私が使用したレイアウトでは、最初に試すソリューションよりも行き止まりが少ないため、すぐに頭に浮かぶのはハイブリッド ソリューションです。最初に最小限のメモリで解決してみてください (選択したペアをスタックに保存します)。最初の行き止まりに到達したら、各ノードにアクセスするときに完全なマーキング/エッジ生成を行うように低下します (可能な場合は遅延評価)。
ただし、私はグラフ理論の研究をほとんど行っていないため、DAG のランダム トラバーサル/検索の問題に対するより良い解決策があるかもしれません :)
編集：2008年10月13日の投稿で、ボードを逆に生成する私のソリューションを実際に使用できます。それでも行き止まりになる可能性があるため、同じ注意事項があります。ただし、ボードを逆に生成するには、より複雑なルールがあります。たとえば、長い行が 1 つあるレイアウトのように、最初のピースが中央にある行の少なくとも一部を開始しないと、セットアップに失敗することが保証されます。前方解決ジェネレーターで完全にランダムな (合法的な) 最初の動きを選択すると、解決可能なボードにつながる可能性が高くなります。
私が思いついた唯一のことは、一種のリバース麻雀ソリティア ゲームとして、タイルを一致するペアに配置することです。したがって、タイルの配置中のどの時点でも、ボードは実際のゲームの途中にあるように見える必要があります (つまり、タイルが他のタイルの上に 3 層浮いていない)。
タイルがリバース ゲームで一致するペアに配置されている場合、ゲームを解決するための少なくとも 1 つの前進パスが常に発生する必要があります。
他のアイデアを聞きたいです。
最良の答えはすでに押し上げられていると思います。つまり、「逆に」解くことによってセットを作成します。つまり、空白のボードから始めて、どこかにペアを追加し、解ける位置に別のペアを追加します。
「ビッグバン」アプローチ（最初にセット全体をランダムに生成する）を好む場合、非常にマッチョな開発者である場合、または今日マゾヒスティックであると感じる場合は、特定のセットから取り出すことができるすべてのペアと、それらがどのように依存するかを表すことができます有向グラフを介して互いに。
そこから、そのセットの推移閉包を取得し、目的のエンドにつながる最初のリーガルペアの少なくとも1つから少なくとも1つのパスがあるかどうかを判断するだけで済みます（タイルペアは残っていません）。
このソリューションの実装は、読者の演習として残されています：D
ゲームには 144 個のタイルがあり、144 個のタイルのそれぞれにブロック リストがあります.. (スタックの一番上のタイルには空のブロック リストがあります)
すべての有効な移動では、"current__vertical_Block_list" が空である必要があります。これは 144x144 の行列になる可能性があるため、20k のメモリと LEFT および RIGHT ブロック リスト (それぞれ 20k) が必要です。
(remaning_tiles) AND ((empty CURRENT VERTICAL BLOCK LIST) and ((empty CURRENT LEFT BLOCK LIST) OR (empty CURRENT RIGHT BLOCK LIST))) から有効な移動テーブルを生成します
有効な移動テーブルから 2 つのランダムなタイルを選び、それらを記録します (現在のテーブルの Vert、左と右) を更新し、スタックに削除されたタイルを記録します
これで、有効なゲームを構成する手のリストができました。72 の動きのそれぞれに一致するタイル タイプを割り当てます。
挑戦的なゲームの場合、各タイルがいつ利用可能になるかを追跡します。(早い早期早期後期) と (後期後期後期早期) を持つセットを見つけます。空白なので、1 EE 1 LL ブロックと 2 LE ブロックを見つけます.. 2 LE ブロックのうち、他の EARLY をブロックする EARLY を見つけます (左側のピースを右ブロックすることを除いて)
有効なゲームができたら、順序を変えてプレイします。
これが私の実装で使用したルールです。
ヒープを構築するときは、ペアのフレットごとに、次のようなセル (場所) を見つけます。
これらのルールは、ビルドが常に成功することを保証するものではありません - 最後の 2 つのフリー セルがセルフ ブロッキングのままになる場合があり、ビルドを再試行する必要があります (または少なくとも最後の数フレット)。
既存のゲームのほとんどは、最初のフレット (「最初の行」) を真ん中のどこかに置くことを制限しているようです。これは、非常に長い列の端にフレットがなく、最後のプレーヤーが移動するまでフレットがない場合に、より便利な構成を考え出します。ただし、「中間」は構成によって異なります。
幸運を ：）
PS 解決可能なヒープを 1 ターンで構築するアルゴリズムを見つけた場合は、お知らせください。
ソリティア？推測ですが、これを判断するには、コンピューターがゲームに勝つ (またはそれに近い) 必要があると思います。
もう 1 つのオプションは、いくつかのプリセット レイアウトを用意することです (勝利を可能にし、現在のレベルに混ぜ合わせることができます。
ある程度、4 つのタイルの 1 つが別の X の下の X レイヤー以下であることを確認してみてください。
私が見るほとんどのゲームには、誰かが動けなくなったときのシャッフル コマンドがあります。
私は物事を組み合わせてみて、何が最もうまくいくかを見ていきます.