パズルを解くアルゴリズム – 必要なアドバイス

次の文字が円形のパターンで配置されているとします。

    A
B       E 
  C   D

各文字は、その反対の文字のいずれかと併合して、隣接する文字を形成することができる。例えば

A,C => B,B
A,D => E,E

B,E => A,A
B,D => C,C

C,A => B,B
C,E => D,D

D,B => C,C
D,A => E,E

E,B => A,A
E,C => D,D

今度は次の文字のグリッドが与えられます:

D A C
B E A
A B E

以下の座標で:

{0,2} {1,2} {2,2}
{0,1} {1,1} {2,1}
{0,0} {1,0} {2,0}

目的は、すべての文字が A になるまで、隣接する文字をマージすることです。

考えられる解決策は次のとおりです。

1。 D {0,2}、A {1,2} = E

E E C
B E A
A B E

2。 C {2,2}、A {2,1} = B

E E B
B E B
A B E

3. E{0,2}, B{0,1} => A

A E B
A E B
A B E

4. E{1,2}, B{2,2} => A

A A A
A E B
A B E

5. E{1,1}, B{2,1} => A

A A A
A A A
A B E

6. E{1,0}, B{2,0} => A

A A A
A A A
A A A

私は3×3から10×10グリッドまで、これらのタイプの問題をプログラムで解決できるアルゴリズムに取り組んでいます。マージ方法を規定する文字数やルールは変更されません。

私は現在、うまく動作するアルゴリズムを持っていますが、完璧とはほど遠いものです。ほとんどのパズルを解くことができますが、解決するには時間がかかりすぎるか、まったく解決策を見つけることができません。各繰り返しの手順は次のとおりです。

    1. Find all instances of the letters C or D. Build a set of moves
      which will convert C or D into B or E.
    1. Score and sort the list of moves based on the following
      criteria:

      • a. Add score for each E have at least 1 adjacent B
      • b. Minus score for each E which does not have at least 1
        adjacent B and vise versa
    1. Select the top move, perform it then repeat until condition in
      step 4 is met.
    1. If all letters are composed of A, or E with 1 matching adjacent
      B then merge all E with B and complete the puzzle

私はプログラマーとゲームデザイナーですが、私はアルゴリズム、数学、またはAIで全くの背景がありません。私は「スマートな人間のプレイヤーは何をするだろう」という視点からそれに近づいてきました。

すべてのアイデアは本当に感謝されます!

[UPDATE] Improving the heuristics used to score
and rank the moves, and also implementing a backtracking search has
allowed my current algorithm to solve over 140 levels.

ゲームで動作するアルゴリズムの例を次に示します。

パフォーマンスはまだ未解決の問題です。上記のレベルは、バックトラッキングなしで解決するのに約2秒かかりました。処理時間の大半は、各反復で可能なすべての動きを計算してソートします。

ベストアンサー

非常に部分的な答え

あなたはA..Eを0..4 mod 5と考えるべきです。あなたのルールが言うところでは、隣り合った数字$ x、y
$があれば、それらを$ frac {x + y} {2} $で置き換えることができます。 (2は可逆性のmod
5です。もっと幸せになれれば、$ frac {x + y} {2} $の代わりに$ 3(x +
y)$と言うことができます。

これを行うと、あなたのすべての数字(mod-5)の合計は変化しません。したがって、和が0に等しくない限り、解は存在しません。合計は
0です。常に勝てますか?いいえ:$ 1,1、-2 $を含む3×1の四角形がある場合、それを変更するために行うことができるのは$
1,2,2 $に変えることだけです。それを行うことができますはそれを$ -1、-1,2
$に変えることで、<-1>、-2、-2 $、そして唯一の すると$ 1,1、-2
$を得ることができます。

(1)これは本質的に、合計が0であっても勝てない唯一の状況であり、(2)あなたが勝つことができるときには勝てる常に「一次元」に勝つ(配列全体をカバーするパスを構築する;例えば、上の行に沿って左から右へ、次に右から左に沿って、次に左から右へ、そして次に適用するなど)あなたの操作はこの経路に沿って「進む」)。

ピーター・テイラーがコメントで正しく指摘しているように、上記のことはあなたが勝つことができない唯一のゼロサイズの状況ではありません:もしあなたが1×5を含む5×5の矩形を持っていれば、あなたは何もありませんできる。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です