「Flip all（Light Out）」ゲームのアルゴリズムはありますか？

Question

このゲームの場合：http://www.mathsisfun.com/games/allout.html 解決機能は、元のボードをいかに乱用しても、どのような場合でも解決できます。このゲームを解決するためのアルゴリズムを教えてください。私は数日間考えようとしましたが、すべての症例を解決する手掛かりはまだ見つかりませんでした。

OK、後にいくつかの回答やコメントを読んで（と迅速な光を見てゲームを持っている）、私は私の質問を展開します。私は、グリッドのサイズを拡大する場合

は、ゲームが異なるウィル（たい25x25）？任意の可能なアルゴリズムを解決するために任意ケース、受諾可能な時間（< 2秒）で？

は、各ノードは、ゲームの状態と状態の子供たちは、これらの状態間の遷移を表しているツリー構造を実装します。ほとんどのAI「ゲーム」の問題と同様に

Answer 1

このゲームは、より一般的にはLights Outとして知られていて、いくつかの標準的ではあるが高度な数学に基づいた数多くの洗練されたソリューションを備えています。私はここでそれらをすべて説明するつもりはありませんが、Googleの方が少し簡単な手順から線形代数やグループ理論に変わるすべての種類の説明を見つけることができます。いくつかのリンク：

http://www.hamusutaa.com/pilot/solution.html

http://www.ripon.edu/academics/macs/summation/2010/articles/M.%20Madsen%20-%20Lights%20Out.pdf

http://people.math.sfu.ca/~jtmulhol/math302/notes/24-Lights-Out.pdf

編集：再：あなたの2番目の質問。私が投稿した第2のリンクに提示されたアルゴリズムは、n×nのボードをO（n^6）時間で解くことができます。つまり、25×25ボードを素早く解くことができます。

Answer 2

は、一般的なアプローチがあります。

これは、幅優先検索（見た過去の状態のログを保存して再訪することを拒否し、最適な解決策を見つけるのを気にしない場合は深度優先）あなたがA *を使うことを可能にする楽観的なヒューリスティックを持っています。私が考えることができる非常にひどいヒューリスティックは、「5で割ったパズルに勝つために反転させる必要のあるサークルの数」です。よりよいものがあるかどうかはわかりません。私はこれに関する人の意見を聞くことに興味があります（楽観的でなければならないことに注意してください。つまり、ヒューリスティックは決して必要な動きの数を決して計算できません）。

詳細については少し愚かです。これは大きな話題ですが、それ以外にも幅優先検索やA *のやり方がわかっているのなら、それはかなりシンプルです。

Answer 3

この問題を解決するためのよく知られた方法があります。 x_1、...、x_nをn番目のボタンを解の一部として押したかどうかに応じた変数をa_1、...、a_nを初期状態とする。

のは、あなたは3x3の問題を解決しているとしましょう、と変数は次のように設定されています

x_1 x_2 x_3 
x_4 x_5 x_6 
x_7 x_8 x_9 

と、この初期状態は次のとおりです。

a_1 a_2 a_3 
a_4 a_5 a_6 
a_7 a_8 a_9 

さて、あなたはいくつかを書き留めることができます解が満足しなければならない式（2を法とする算術）。基本的にスイッチが特定のライトをトグルさせるルールをエンコードしています。

a_1 = x_1 + x_2 + x_4 
a_2 = x_1 + x_2 + x_3 + x_5 
... 
a_5 = x_2 + x_4 + x_5 + x_6 + x_8 
... 
a_9 = x_6 + x_8 + x_9 

これで、この連立方程式の集合をガウス消去法で解くことができます。 2を法とする算術演算をしているので、実数よりも連立方程式よりも実際には簡単です。たとえば、2番目の方程式でx_1を取り除くには、最初の方程式を単純に追加します。

a_1 + a_2 = (x_1 + x_2 + x_4) + (x_1 + x_2 + x_3 + x_5) = x_3 + x_4 + x_5 

は具体的には、ここではガウス消去アルゴリズムは、算術モジュロ2である：

• それでX_1と式を選択してください。名前はE_1です。
• 他の名前のない方程式にx_1を付けてE_1を追加します。
• x_2、x_3、....、x_nに対して繰り返します。

ここで、E_nはx_nのみを含む式です。これから得たx_nの値を元の方程式に代入することができます。 E_ {n-1}、...、E_1について繰り返す。

全体として、これはO（n^3）操作の問題を解決します。

ここにいくつかのコードがあります。

class Unsolvable(Exception): 
    pass 

def switches(vs): 
    n, m = len(vs), len(vs[0]) 
    eqs = [] 
    for i in xrange(n): 
     for j in xrange(m): 
      eq = set() 
      for d in xrange(-1, 2): 
       if 0 <= i+d < n: eq.add((i+d)*m+j) 
       if d != 0 and 0 <= j+d < m: eq.add(i*m+j+d) 
      eqs.append([vs[i][j], eq]) 

    N = len(eqs) 
    for i in xrange(N): 
     for j in xrange(i, N): 
      if i in eqs[j][1]: 
       eqs[i], eqs[j] = eqs[j], eqs[i] 
       break 
     else: 
      raise Unsolvable() 
     for j in xrange(i+1, N): 
      if i in eqs[j][1]: 
       eqs[j][0] ^= eqs[i][0] 
       eqs[j][1] ^= eqs[i][1] 

    for i in xrange(N-1, -1, -1): 
     for j in xrange(i): 
      if i in eqs[j][1]: 
       eqs[j][0] ^= eqs[i][0] 
       eqs[j][1] ^= eqs[i][1] 
    return [(i//m,i%m) for i, eq in enumerate(eqs) if eq[0]] 

print switches(([1, 0, 0], [0, 1, 0], [0, 0, 1], [0, 0, 0])) 

一度に1行ずつ初期状態にします。これは、すべてのライトをオフにするために押す必要のあるスイッチを返します。

これは私のラップトップで0.5秒未満で50x50の問題を解決します。