「全部翻轉」（Light Out）遊戲的任何算法？

要麼作爲廣度優先搜索（深度優先確定，如果您保留以前看過的狀態的日誌並拒絕重新訪問它們，並且您不關心尋找最佳解決方案）還是來以一種樂觀的啓發式方式，讓你使用A *。我能想到的一個非常糟糕的啓發式是「需要翻轉以贏得難題的圈數，除以5」。我不確定是否有更好的;我有興趣聽取關於這個人的輸入（請注意，它必須是樂觀的，也就是啓發式不能過計算所需的移動次數。）

走進更多的細節，因爲有點傻這是一個很大的話題，除此之外，如果你知道如何進行廣度優先搜索或A *，這非常簡單。

來源

2011-08-27 07:03:42 Jeremy

我還不知道A *如何解決這個遊戲（我還沒有完全研究過A *），BFS似乎是可能的，但是......從哪裏開始？在25x25的網格中，可能無法將手機內存適合所有情況。 –

@ W.N。是的，直線BFS將無法做到25x25，至少不夠優雅。如果你能想到更有用的啓發式，A *是可行的。如果沒有一個（也許合理的啓發式會解決一個放鬆的問題？例如，嘗試解決這個遊戲的一個版本，當你翻轉一個方塊時，它和它周圍的四個方塊翻轉，但只有當它們是錯誤的顏色）。如果即使這樣做不夠好，你也必須特別考慮這個問題，並且看看你可以用來解決這個問題的特定技巧。 – Jeremy

有一個衆所周知的方法來解決這個問題。設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，所以它比實數上的聯立方程式更容易一些。例如，爲了擺脫第二個方程中的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。
將E_1添加到其中有x_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]))

您一次給它一個行的初始狀態。它會返回您需要按下以關閉所有燈光的開關。

這可以在我的筆記本電腦上用不到半秒的時間解決50x50問題。

來源

2014-03-08 10:09:12

「全部翻轉」（Light Out）遊戲的任何算法？

回答

相關問題