點燈遊戲簡介

一層大樓共有n imes n個房間，每個房間都有一盞燈和一個按鈕。按動一個房間的按鈕後，這個房間和周圍四個相鄰的房間的燈的狀態全部都會改變（由暗變為亮或者亮變為暗）。目標是通過按按鈕把所有的燈都點亮（默認情況下全暗）。

點燈遊戲規律

我們不難發現以下規律

1. 按偶數次按鈕相當於沒有按。

2. 無論按按鈕順序如何結果總是一樣的。

因此我們有以下結論

1. 對於盤面上的每一個按鈕，我們只需要考慮其按開或關的狀態。

2. 每一個按鈕的狀態都是互相獨立的，不需要考慮按按鈕的順序。

點燈遊戲演算法

概覽

1. 完全窮舉法， O(2^{n^2})

2. 首行窮舉法， O(2^n)

3. 完全方程法， O(n^6)

4. 首行方程法， O(n^3)

點燈遊戲演算法詳解

1.完全窮舉法， O(2^{n^2})

對於每一個按鈕只有開和關兩種狀態。而一旦所有按鈕的狀態都確定了，燈的狀態也就確定了。因此，我們只需要把所有按鈕的所有可能的狀態列舉出來，算出對應燈的狀態並判斷所有燈是否都點亮了即可。

不難發現，一個按鈕的狀態是 2 種，因此x個按鈕的狀態就是 2^x 種。一個 n imes n 的房間一共有 n imes n 個按鈕，因此就有 2^{n imes n} 種狀態。這種演算法的複雜度就是 O(2^{n^2}) 。

舉個例子，下面是一種房間按鈕的狀態和對應燈的狀態（ 代表開，□代表關，●代表亮，○代表暗）：

□ □ ● ● ● ● ●
□ □ □ ● ● ● ● ●
□ □ □ ● ● ○ ● ●
□ □ □ ● ● ● ● ●
□ □ ● ● ● ● ●

下面是另一個例子：

□ □ □ ○ ○ ○ ○ ○
□ □ □ □ ○ ○ ○ ○ ○
□ □ ○ ○ ● ○ ○
□ □ □ ○ ○ ○ ○ ○
□ □ ○ ○ ○ ○ ○

這是合併後的結果（ 5 imes 5 下的解）：

□ □ ● ● ● ● ●
□ □ ● ● ● ● ●
□ □ ● ● ● ● ●
□ ● ● ● ● ●
□ □ □ ● ● ● ● ●

有些情況下，即使按了按鈕，全部燈的狀態也可能不變：

□ □ ○ ○ ○ ○ ○
□ □ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○
□ □ ○ ○ ○ ○ ○
□ □ ○ ○ ○ ○ ○

因此，解可能不是唯一的（對於解的存在性，唯一性及解的個數，將在演算法3中討論）：

□ □ □ ● ● ● ● ●
□ ● ● ● ● ●
□ □ ● ● ● ● ●
□ □ ● ● ● ● ●
□ □ ● ● ● ● ●

2.首行窮舉法， O(2^n)

完全窮舉法的時間複雜度太高，當 n=6 時，房間的狀態已高達 2^{36}=68719476736 種。在遊玩的過程中我們會去嘗試點亮儘可能多的燈。很多狀態（例如只按 1 或 2 個按鈕）顯然無法滿足我們的要求而可以快速排除。

為了使得儘可能多的燈被點亮，假設我們已經決定了第一行按鈕的狀態，此時只有第一行和第二行的燈被改變了。由於只有第一行或第二行按鈕會改變第一行燈的狀態，為了使得第一行的燈全亮，由於第一行按鈕狀態已經確定，我們只能去按第二行的按鈕，此時第二行按鈕開的狀態和第一行燈滅的狀態是相反的（為了讓第一行燈亮，我們必須去按第二行對應列的按鈕），此時第二行的按鈕狀態也被確定了。

由於第二行按鈕狀態確定了，為了使第二行燈全亮，第三行按鈕的狀態也被確定了。以此類推，整個房間的按鈕都被第一行按鈕的狀態確定了，而房間里除了最後一行的燈也都是全亮的。

因此，其實我們不需要把房間里所有的按鈕可能的狀態全部列舉出來，而只需要把第一行按鈕可能的狀態列舉出來就行了。對於每一種狀態，我們只需要按照上面的步驟計算出後面 n-1 行的按鈕狀態，然後計算出最後一行燈的狀態就行了。對於房間里可能出現的別的按鈕的狀態的可能性，由於前面 n-1 行的燈不是全亮所以不需要考慮。

一行里的燈一共有 n 個，因此就有 2^n 種狀態。這種演算法的複雜度就是 O(2^n) 。

舉個例子，假設第一行按鈕的狀態是：

□ □ □

則按鈕和燈的狀態為：

□ □ □ ● ○ ● ● ○
□ □ □ □ □ ● ○ ● ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○

因此，為了讓第一行第二列和第五列的燈亮，必須按第二行第二列和第五列的按鈕：

□ □ □ ● ● ● ● ●
□ □ □ ○ ● ○ ● ●
□ □ □ □ □ ○ ● ○ ○ ●
□ □ □ □ □ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○

然後是第三行第一列和第三列的按鈕：

□ □ □ ● ● ● ● ●
□ □ □ ● ● ● ● ●
□ □ □ ● ● ● ● ●
□ □ □ □ □ ● ○ ● ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○

由於第三行的燈已經全亮了，第四行的按鈕不需要按動（全是關，□）。

第五列的按鈕如下和最終燈的結果如下：

□ □ □ ● ● ● ● ●
□ □ □ ● ● ● ● ●
□ □ □ ● ● ● ● ●
□ □ □ □ □ ● ● ● ● ●
□ □ ● ● ○ ○ ○

由於第五行的燈沒有全亮，因此第一行按鈕的狀態不是想要的結果。

下面舉另外一個例子，假設第一行按鈕的狀態是：

□ □ □

則按鈕和燈的狀態為：

□ □ □ ○ ○ ● ○ ○
□ □ □ □ □ ● ● ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○

第二行按鈕按動後：

□ □ □ ● ● ● ● ●
□ ● ● ○ ○ ○
□ □ □ □ □ ● ● ○ ● ●
□ □ □ □ □ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○

第三行按鈕按動後：

□ □ □ ● ● ● ● ●
□ ● ● ● ● ●
□ □ ● ○ ○ ○ ●
□ □ □ □ □ ○ ○ ● ● ●
□ □ □ □ □ ○ ○ ○ ○ ○

第四行按鈕按動後：

□ □ □ ● ● ● ● ●
□ ● ● ● ● ●
□ □ ● ● ● ● ●
□ □ ● ○ ○ ● ○
□ □ □ □ □ ○ ● ● ● ○

最後一行按鈕按動後和最終結果：

□ □ □ ● ● ● ● ●
□ ● ● ● ● ●
□ □ ● ● ● ● ●
□ □ ● ● ● ● ●
□ □ ● ● ● ● ●

所有的燈都被點亮了，因此第一行按鈕的狀態是我們想要的結果。這與我們演算法1中的結果是相同的。

3.完全方程法， O(n^6)

雖然演算法2已經將複雜度降到了 O(2^n) ，但是這仍舊是指數時間的複雜度。對於n>30來說，這不是一般計算機所能承受的範圍了。有沒有更快的演算法呢？下面將介紹多項式時間內的演算法。

在演算法2中我們發現，第n行的燈的狀態是由第 n-1 行、第 n 行和第 n+1 行按鈕的狀態決定的，而不是由所有的按鈕決定的。通過這點，我們將演算法的複雜度從 O(2^{n^2}) 降到了 O(2^n)。但是對於同一行內按鈕以及燈的狀態，我們還是將其視為一個整體。那麼，對於同一行內按鈕或者燈的狀態，它們之間是否有關係呢？

答案是肯定的。我們知道，一個按鈕可以決定它和它周圍4個燈的狀態，同樣的，一個燈的狀態則是由它和它周圍4個按鈕決定的。

我們假設燈的狀態是由其中兩個按鈕決定的，則具體的情況可以表示為：

□ + □ = ○
+ □ = ●
□ + = ●
+ = ○

從數學角度來說，我們這樣假設：□=0，=1，○=0，●=1。於是，上面的式子就變為了：

0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 0

這樣的+號我們稱之為（邏輯上的）異或運算。

由於情況下，燈和它周圍開的按鈕的數量決定了燈的狀態，例如●22（第二行第二列的燈）是由12、21、22、23和32決定的，於是我們有：

12 + 21 + 22 + 23 + 32 = ●22

例如12，22和23是開，21和32是關，於是●22被開了3次。由於開兩次等同於沒開，所以●22相當於被開了1次，是亮的狀態。也可以表示為：

+ □ + + + □ = ●

於是，對於房間里所有按鈕和燈的狀態，我們可以列出n*n個式子。這裡以3*3舉例：

11 + 12 + 21 = ●11
11 + 12 + 13 + 22 = ●12
12 + 13 + 23 = ●13
11 + 21 + 22 + 31 = ●21
12 + 21 + 22 + 23 + 32 = ●22
13 + 22 + 23 + 33 = ●23
21 + 31 + 32 = ●31
22 + 31 + 32 + 33 = ●32
23 + 32 + 33 = ●33

由於我們的目標是將所有的燈點亮，因此所有的燈的狀態都是亮（●，1）。由於按鈕一共有9個，因此從數學角度來說我們得到了一個九元一次方程組：

x1 + x2 + x4 = 1
x1 + x2 + x3 + x5 = 1
x2 + x3 + x6 = 1
x1 + x4 + x5 + x7 = 1
x2 + x4 + x5 + x6 + x8 = 1
x3 + x5 + x6 + x9 = 1
x4 + x7 + x8 = 1
x5 + x7 + x8 + x9 = 1
x6 + x8 + x9 = 1

需要注意的是，這裡的+是我們剛才所說的異或運算。解這個方程組，我們就能得到所有按鈕的狀態。上面這個方程組的解是：

x1 = 1, x2 = 0, x3 = 1,
x4 = 0, x5 = 1, x6 = 0,
x7 = 1, x8 = 0, x9 = 1.

於是，所有按鈕的狀態是：

□
□ □
□

也就是 3 imes 3 房間的答案。

為了解出上面的方程，我們可以將方程式組表示成矩陣的形式，然後對矩陣進行高斯消元：

□ □ □ □ □ □ ● ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ● ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ ○ ○ ● ○ ○ ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ● ○ ○ ○ ○ ○
□ □ □ □ ○ ○ ○ ○ ● ○ ○ ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○ ● ○ ○ ○
□ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ● ○ ○
□ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ● ○
□ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ●

高斯消元的過程等同於求逆矩陣，因此：

● ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □
○ ● ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □
○ ○ ● ○ ○ ○ ○ ○ ○ □ □ □ □
○ ○ ○ ● ○ ○ ○ ○ ○ □ □ □ □ □
○ ○ ○ ○ ● ○ ○ ○ ○ □ □ □ □
○ ○ ○ ○ ○ ● ○ ○ ○ □ □ □ □ □
○ ○ ○ ○ ○ ○ ● ○ ○ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ● ○ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ● □ □ □ □

這個矩陣的每一行表示，如果需要單獨點亮一個燈，需要按哪些按鈕。因此，點亮所有燈就相當於將所有行加起來：

● ● ● ● ● ● ● ● ● □ □ □ □

也就是：

□
□ □
□

對於 5 imes 5 的房間，我們有：

□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○
□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ●

解得：

● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ● □ □ □ □ □ □ □ □ □ □
○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ ● ○ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ● ● □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ○ ○ ● □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ○ ● ○ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ● ● ● □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ □ □ □ □ □ □ □ □ □ □ □ □ □

這次我們發現，左邊的燈矩陣並不是每行都是只有一個亮的，最後兩行是全滅的。因此，右邊最後兩行按鈕按的結果仍舊是全滅，也是演算法1中的一種情況。當然，這兩行的組合也是全滅。

只有當燈矩陣的一行只有一個燈亮時（一行只有一個●，這裡有5行是這種情況），這個燈才能被單獨的打開。對於其餘的燈來說（這裡有18行是這種情況），無論怎麼按按鈕都會影響到其它的燈（這裡是會影響到最後兩個燈）。

雖然燈矩陣的每一行並不是只有一個燈，但是將每一列相加的結果仍舊是1（亮）。因此，我們仍然可以通過將所有行相加的方法得到燈全亮時按鈕的狀態：

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● □ □ □ □ □ □ □ □ □ □

也就是：

□ □
□ □
□ □
□
□ □ □

對於 23 個燈來說，這樣的解是唯一的。然而，由於有能讓燈全滅的按鈕狀態的存在（兩種），因此將此解和全滅狀態進行組合仍舊是解。因此，這種情況下一共有 1 imes 2^2=4 種解。

從矩陣的角度來說， 5 imes 5 房間矩陣的秩為 23 ，因此這種情況解的個數就是 2^{5 imes 5-23}=4。可以證明，對於 n imes n 的矩陣來說，只要燈矩陣是單位矩陣（房間的初始狀態為燈全滅，目標燈全亮），那麼解一定存在。事實上，存在這樣的定理：

如果遊戲是對稱的（如果按下按鈕1後會改變燈2，那麼按下按鈕2會改變燈1），那麼遊戲是可解的，當且僅當燈全滅的按鈕狀態組是偶數個。這是由於遊戲是對稱的，因此燈全滅狀態的按鈕總是會使得所有燈被按偶數次。一個可解狀態燈一定被全滅狀態按鈕按了偶數次。

對於點燈遊戲來說，顯然所有的按鈕矩陣都是對稱的，因此燈全滅的按鈕狀態組一定是偶數個，因此遊戲一定是可解的。

關於用以計算出解的多餘的矩陣秩的數目，可以參考這個數列：

A159257 - OEIS?oeis.org?

oeis.org

由於高斯消元或矩陣求逆法的時間複雜度是 O(n^3) ,而我們矩陣的邊長是 n imes n ，因此該演算法的時間複雜度是 O(n^6) 。

4.首行方程法， O(n^3)

上述的演算法將時間複雜度降到了多項式時間 O(n^6) ，對於 n<=100 的房間是沒有問題了。但是對於 n>1000 乃至 n>10000 的房間卻也無能為力了。有沒有辦法進一步優化演算法呢？答案是肯定的，下面就是見證奇蹟的時刻了。

在演算法1中，我們把全部的按鈕視為整體，取得了全部燈的狀態。在演算法2中，我們將行視為整體，將時間複雜度減少到了O(2^n)。而在演算法3中，我們仍舊將按鈕視為整體（在方程中，我們並沒有區分每行每列，而是將所有按鈕和燈分別編號）。由於第一行的按鈕的狀態可以決定後面所有行按鈕的狀態，那麼我們是否能將第一行按鈕看作一個整體，並將其應用到我們的方程中呢？這就帶來了我們的演算法4。

還是以 3 imes 3 的房間為例，我們假設第一行的按鈕為11，12，13，那麼按照演算法2，我們可以將●11，●12，●13表示為：

●11 = 11 + 12
●12 = 11 + 12 + 13
●13 = 12 + 13

由於對於第二行的按鈕，燈暗的時候按鈕應該開，燈亮的時候按鈕應該關，因此按鈕的狀態和燈是相反的，於是我們有（這裡的-代表否運算）：

21 = -●11 = -(11 + 12)
22 = -●12 = -(11 + 12 + 13)
23 = -●13 = -(12 + 13)

緊接著，我們可以計算出第二行燈的狀態：

●21 = 11 + 21 + 22 = 11 + -(11 - 12) + -(11 - 12 - 13) = 11 + 13
●22 = 12 + 21 + 22 + 23 = 12 + -(11 + 12) + -(11 + 12 + 13) + -(12 + 13) = ●
●23 = 13 + 22 + 23 = 13 + -(11 + 12 + 13) + -(12 + 13) = 13 + 11

以及第三行按鈕的狀態：

31 = -●21 = -(13 + 11)
32 = -●22 = □
33 = -●23 = -(11 + 13)

最後一行燈的狀態：

●31 = 21 + 31 + 32 = -(11 + 12) + -(13 + 11) + □ = 12 + 13
●32 = 22 + 31 + 32 + 33 = -(11 + 12 + 13) + (13 + 11) + 0 + (11 + 13) = -(11 + 12 + 13)
●33 = 23 + 32 + 33 = -(12 + 13) + □ + -(11 + 13) = 12 + 11

也就是方程：

X2 + x3 = 1
x1 + x2 + x3 = 0
x2 + x1 = 1

解得：

x1 = 1, x2 = 0, x3 = 1

因此 3 imes 3 房間的按鈕第一行為：

□

由此推算出全部按鈕為：

□
□ □
□

用矩陣方法表示時過程是這樣的，先是第一行按鈕：

11 □ □ ○ 12 □ □ ○ 13 □ □ ○

接著是第一行燈（燈是前面4個按鈕的總和）：

01 02 03
10 11 □ □ ○ 12 □ □ ○
11 □ □ ○ 12 □ □ ○ 13 □ □ ○
12 □ □ ○ 13 □ □ ○ 14
●11 □ ○ ●12 ○ ●13 □ ○

然後是第二行按鈕（和燈的狀態相反）

21 □ ● 22 ● 23 □ ●

然後是第二行燈：

11 □ □ ○ 12 □ □ ○ 13 □ □ ○
20 21 □ ● 22 ●
21 □ ● 22 ● 23 □ ●
22 ● 23 □ ● 24
●21 □ ○ ●22 □ □ □ ● ●23 □ ○

以及第三行按鈕：

31 □ ● 32 □ □ □ ○ 33 □ ●

最後是第三行燈：

21 □ ● 22 ● 23 □ ●
30 31 □ ● 32 □ □ □ ○
31 □ ● 32 □ □ □ ○ 33 □ ●
32 □ □ □ ○ 33 □ ● 34
●31 □ ○ ●32 ● ●33 □ ○

於是我們等到矩陣：

□
□
□

解得結果：

□ □
□ □ □
□ □

因此，第一行按鈕就是：

□

推算出全部按鈕為：

□
□ □
□

下面對 5 imes 5 的房間進行矩陣演示：

第一行按鈕：

11 □ □ □ □ ○ 12 □ □ □ □ ○ 13 □ □ □ □ ○ 14 □ □ □ □ ○ 15 □ □ □ □ ○

第一行燈：

00 01 02 03 04
10 11 □ □ □ □ ○ 12 □ □ □ □ ○ 13 □ □ □ □ ○ 14 □ □ □ □ ○
11 □ □ □ □ ○ 12 □ □ □ □ ○ 13 □ □ □ □ ○ 14 □ □ □ □ ○ 15 □ □ □ □ ○
12 □ □ □ □ ○ 13 □ □ □ □ ○ 14 □ □ □ □ ○ 15 □ □ □ □ ○ 16
○11 □ □ □ ○ ○12 □ □ ○ ○13 □ □ ○ ○14 □ □ ○ ○15 □ □ □ ○

第二行按鈕：

21 □ □ □ ● 22 □ □ ● 23 □ □ ● 24 □ □ ● 25 □ □ □ ●

第二行燈：

11 □ □ □ □ ○ 12 □ □ □ □ ○ 13 □ □ □ □ ○ 14 □ □ □ □ ○ 15 □ □ □ □ ○
20 21 □ □ □ ● 22 □ □ ● 23 □ □ ● 24 □ □ ●
21 □ □ □ ● 22 □ □ ● 23 □ □ ● 24 □ □ ● 25 □ □ □ ●
22 □ □ ● 23 □ □ ● 24 □ □ ● 25 □ □ □ ● 26
○21 □ □ □ ○ ○22 □ □ □ □ ● ○23 □ □ □ ● ○24 □ □ □ □ ● ○25 □ □ □ ○

第三行按鈕：

31 □ □ □ ● 32 □ □ □ □ ○ 33 □ □ □ ○ 34 □ □ □ □ ○ 35 □ □ □ ●

第三行燈：

21 □ □ □ ● 22 □ □ ● 23 □ □ ● 24 □ □ ● 25 □ □ □ ●
30 31 □ □ □ ● 32 □ □ □ □ ○ 33 □ □ □ ○ 34 □ □ □ □ ○
31 □ □ □ ● 32 □ □ □ □ ○ 33 □ □ □ ○ 34 □ □ □ □ ○ 35 □ □ □ ●
32 □ □ □ □ ○ 33 □ □ □ ○ 34 □ □ □ □ ○ 35 □ □ □ ● 36
○31 □ □ ○ ○32 □ ○ ○33 □ □ ● ○34 □ ○ ○35 □ □ ○

第四行按鈕：

41 □ □ ● 42 □ ● 43 □ □ ○ 44 □ ● 45 □ □ ●

第四行燈：

31 □ □ □ ● 32 □ □ □ □ ○ 33 □ □ □ ○ 34 □ □ □ □ ○ 35 □ □ □ ●
40 41 □ □ ● 42 □ ● 43 □ □ ○ 44 □ ●
41 □ □ ● 42 □ ● 43 □ □ ○ 44 □ ● 45 □ □ ●
42 □ ● 43 □ □ ○ 44 □ ● 45 □ □ ● 46
○41 □ □ □ □ ● ○42 □ □ □ □ ○ ○43 □ □ □ □ ○ ○44 □ □ □ □ ○ ○45 □ □ □ □ ●

第五行按鈕：

51 □ □ □ □ ○ 52 □ □ □ □ ● 53 □ □ □ □ ● 54 □ □ □ □ ● 55 □ □ □ □ ○

第五行燈：

41 □ □ ● 42 □ ● 43 □ □ ○ 44 □ ● 45 □ □ ●
50 51 □ □ □ □ ○ 52 □ □ □ □ ● 53 □ □ □ □ ● 54 □ □ □ □ ●
51 □ □ □ □ ○ 52 □ □ □ □ ● 53 □ □ □ □ ● 54 □ □ □ □ ● 55 □ □ □ □ ○
52 □ □ □ □ ● 53 □ □ □ □ ● 54 □ □ □ □ ● 55 □ □ □ □ ○ 56
○51 □ □ ○ ○52 □ □ ● ○53 □ ● ○54 □ □ ● ○55 □ □ ○

得到矩陣：

□ □
□ □ □
□ □
□ □ □
□ □

解得：

□ □ □
□ □ □
□ □ □
□ □ □ □ □ □
□ □ □ □ □ □

可以看到，這個矩陣也不是滿秩的（最後兩行為0），這與之前 25 imes 25 的矩陣的情況是一樣的。這說明解不是唯一的。當然我們也可以用矩陣求逆的方法計算出所有可能的解，這裡就不再贅述了。因此，第一行按鈕的狀態可以是：

□ □ □

最後結果是：

□ □ □
□
□ □
□ □
□ □

由第一行按鈕狀態推算出最後的矩陣方程需要遍歷所有的按鈕和燈一次一行內所有在按鈕，時間複雜度為 O(n^3) 。

計算這個 n imes n 的矩陣的解需要高斯消元，時間複雜度為 O(n^3) 。

由第一行按鈕狀態推算出全部的按鈕狀態需要也遍歷所有的按鈕和燈一次，時間複雜度也為 O(n^2) 。

綜上所述，該演算法總體的時間複雜度為 O(n^3) 。

關於燈非全暗的初始狀態

1. 完全窮舉法， O(2^{n^2})

初始狀態已經亮的燈不需要轉變狀態，就相當於如果這個燈暗則繼續保持暗的狀態，因此這個時候只需要修改一下判定最終燈狀態的條件就行。

2. 首行窮舉法， O(2^n)

因為有些燈已經亮著了，計算按按鈕後燈的狀態時只需要把初始的狀態也考慮進去就行。

3. 完全方程法， O(n^6)

如果用的是高斯消元法，我們只需要修改一下方程右邊燈的增廣矩陣就行。如果直接求矩陣的逆，那麼我們只需要把那些需要轉變狀態的燈的行（而不是所有行）相加即可。

4. 首行方程法， O(n^3)

同演算法2，在計算燈的最終狀態的時候，我們只需要把燈的初始狀態也考慮進去就行。

關於其它規則

只要滿足演算法3中的對稱性，我們依然可以使用演算法1-4的套路進行計算。

對於 n imes m 的房間，我們只需少許修改演算法，依然可以進行計算。

更多結論

關於點燈遊戲的變體以及更多有趣的數學結論可以參考這篇文章：

Lights Out Mathematics??

www.jaapsch.net


推薦閱讀：
相关文章