ゲーム解決アルゴリズム（Buttonia、ライトアウトバリアント）
https://stackoverflow.com/questions/1211560
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
ゲームアルゴリズムの可解性関数を作成しようとしています。基本的に、解けるかどうかによって特定のゲームに対してtrueまたはfalseを返す関数。
このゲームは、Lights-outゲームの一種であるButtonia.com（アルゴリズムはまだ実装されていません）です。基本的に、ボタンのグリッドがあり、各ボタンを押すと、隣接するボタンの状態が変更されます。現在、ランダムなゲーム構成を生成し、可能な限りヒューリスティックを適用しています。残りはブルートフォース検索によって決定されます。
これまでの私の進歩は、ゲームをモデル化する方程式系を作成することでした。各ボタンは、ダウン状態になるために奇数回状態を変更する必要があるため、方程式は次のようになります。
button_A = 1-（button_1 + button_2 + ... + button_X）％2
button_1からbutton_Xは、button_Aに影響するボタンの状態です。一部のボタンは、他のボタンに依存していない場合、すぐに解決される場合があります。残りについては、競合が発生するまで1つの構成を試し、その後バックトラックします。
現在、このアルゴリズムはゲームの小規模な構成に実用的です。 3x3ゲームから10x10のサイズまでテストしました。 6x6が実際のプレイの上限に近い場合。
この方程式は、ブルートフォースから検索空間を大幅に削減し、実用的にしています。方程式系を解くための純粋に数学的な方法があるかもしれません。
asciiのサンプル3x3ゲーム（ buttonia.com/?game=2964 から）：
||#
-o-
+#|
Legend:
o = affect only self
- = affect left and right neighbors
| = affect above and below neighbors
+ = affect left, right, above and below neighbors
# = affect all 8 surrounding neighbors
ソリューション、これらを押します：（0,0）、（2,0）、（1、2）、（0、1）、（1、1）、（2,1）
このゲームの方程式：
Button_0_0 = 1 - (0) % 2
Button_1_0 = 1 - (Button_2_0) % 2
Button_2_0 = 1 - (0) % 2
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2
Button_0_2 = 1 - (Button_1_2) % 2
Button_1_2 = 1 - (Button_0_2) % 2
Button_2_2 = 1 - (Button_1_2) % 2
潜在的な解決策：
モジュラスの必要性を回避するために数学関数を変更すると、左側の項を右側に移動し、ガウス法に必要なきちんとしたマトリックス設定を作成できます。したがって、最初の2つの方程式はそれぞれ次のように変換されます。
-1 = -1*B00 + 0*B10 + 0*B20 + 0*B01 + 0*B11 + 0*B21 + 0*B02 + 0*B12 + 0*B22
-1 = 0*B00 + -1*B10 + -1*B20 + 0*B01 + 0*B11 + 0*B21 + 0*B02 + 0*B12 + 0*B22
ここで議論された解決策：カスタム演算子によるガウス消去
近づいて。完全なソリューションを投稿する準備がほぼ整いました：バイナリネットワークの反転
解決
これは、2つの要素0と1を含むフィールドであるF 2 上の線形方程式系です。
通常の線形方程式と同じように解くことができますが、2を法とする算術演算を行う必要があります。
編集： この場合の線形代数は、実数の場合とまったく同じように機能しますが、操作を置き換える必要があります。
-
加算と減算は排他的になります。つまり、0 + 0 = 0、0 + 1 = 1、1 + 1 = 0です。
-
乗算はANDになります：0 * 0 = 0、0 * 1 = 0、1 * 1 = 1
-
分割は1つのみ可能です：0/1 = 0、1 / 1 = 1。
方程式のすべての係数と未知の可能性のある値は0または1です。
だからあなたが書いたようにモジュロは方程式の外側で平手打ちされません、それは操作で暗黙的です。
方程式系が解けない場合、方程式0 = 1が得られますが、明らかに解けません。
他のヒント
ランダムな状態で開始するのではなく、ランダムなスイッチを切り替えて開始位置を生成します。つまり、解かれた状態から開始状態に逆戻りします。そうすれば、解けるパズルだけを生成できます。
これは一次方程式のシステムにほとんど似ています（mod 2を除く）。マトリックス形式のシステムの行削減（wikipedia）。
これは時間制限の問題ではないので（1日以内にできると仮定して）、深さ制限のある幅優先の検索を行い、レベルごとに可能な移動を行ってから、各動きの後に続く各動き。
処理速度は遅くなりますが、答えがあれば必ず見つかるはずです！
方程式のシステムを構築し、可能な限りそれらを解いたと仮定しますが、一部の行は方程式の左側にすべて0で終わることになります（方程式を拡張行列として表しています） Z2リングでシステムを解こうとしたと仮定します（この特定の例の実際的な用語では、変更は1 + 1 = 0のみであり、それ以外はすべて同じです...必要な演算子はXORのみです）そして次のマトリックスになりました：
1001 1
0100 1
0011 0
0000 0
この例でわかるように、4番目の行はすべて0です。これは、答えが得られていないことを意味します。ただし、このように考えてください。すべて0の行は、その変数がソリューションに影響しないことを意味します。それは実際には単語の貧弱な選択です...それは単にそれらが任意の値を持つことができることを意味します（そして実数とは異なりすべての値は1または0を意味するのでここで幸運です...このシステムのソリューション）。
理由は次のとおりです。この時点で知っておく必要があるのは、右端の列にまだゲームの有効なソリューションが含まれているということです。たとえば、最初の行を見てみましょう。
button_0 + button_3 = 1
しかし、ボタン3は何でもかまいません（3行目はすべて0であるため）。この時点で、ボタン3は0（行3の右端の列はこの時点で0）なので、今ではそれが意味することがわかりました
button_0 + 0 = 1
したがって、button_0が1であることはわかっています。したがって、このシステムでは、button_3を直接見つけることができなくても、有効な解決策があります。
上記で生成された行列は、可解性をチェックするのに十分です。行にすべて0が含まれている場合、本質的には
nothing = nothing
または、これがなぜ機能するのかを視覚化するために、
0x = 0
これは理にかなっていますが、システムはまだ有効です。ただし、右端のビットがすべて0である 行がある場合、つまり
0000 1
それは言っているでしょう
0x = 1
これは不可能なので、このような不可能な状況を解決できないため、システムを解決できないことがわかりました。
したがって、一言で言えば、可能な限り方程式を解いてみてください。変数の一部が正確にわからない場合でも、どの時点でも不可能に遭遇しない限り、心配しないでください。先ほど述べた行は、ゲームを解くことができます。
しかし、システムへの最短ソリューションが必要な場合はどうでしょうか？ここでは、考えられるすべての解決策を検討する必要があります。 button_3には任意の値を指定できるため、列3の1は、それが見つかった行がbutton_3の影響を受けることを意味します。したがって、button_3を使用したソリューションが短くなるかどうかを確認するとします。別のマトリックスを作成しますが、今すぐbutton_3を1に設定します（以前にそれが任意のものであり、すでに0があったため、1をチェックするため）。これで、次のマトリックスが作成されます。
1001 1
0100 1
0011 0
0001 1
これをできる限り減らし、次のマトリックスになりました：
1000 0
0100 1
0010 1
0001 1
これはまだ有効な解決策ですが、解決策の方が長いことがわかります（ボタンを2回押すのではなく、3回必要です）。見つかった行をすべて0から1に設定する順列ごとにこれを行う必要があります。したがって、すべてが0であるx行がある場合、システムにはx ^ 2の解があり、すべてをチェックする必要があります。 / p>
