點燈遊戲：簡單的遊戲能否很美？

• 2016-06-05，第一稿
• 2016-06-19，第二稿

專門把視頻鏈接放這裡：

LightOut_matrix http://www.tudou.com/programs/view/FCc0ctBc5m4/

==================

幾周前，坐地鐵時看zhihu，被推薦了這2篇文章：

點燈遊戲：遲到8年的美麗，用數學繪製的「二維碼」！ - 看！你身邊有一隻數學！ - 知乎專欄

Flip Game（又名翻轉遊戲、點燈遊戲、滅燈遊戲）的遊戲技巧是什麼？ - 趣味數學

覺得是很有趣……入門又簡單，小盆友就可以玩……又可以一下變得很難，比如當N變得很大，N=100, 1000，2000……並且還有許多的衍生問題……最重要的，很明顯地有現成的理論來解決，所以就花了一些時間研究一下，覺得……果然很有趣~~~

================== 先做一個簡單介紹的分界線 ============================

這裡有一個介紹：點燈遊戲_百度百科

wikipedia : Lights Out (game)

這裡有一個在線版，可以試玩：變色方塊 史上最難智力遊戲

國外大概在1983年就出現了這個遊戲，（對，你沒有看錯，確實是30年前），而且還申請了專利，當時大概是這樣的一個東西：

國內許多人知道這個遊戲，大概是在1995年前後？因為電腦普及後，一些遊戲里出現？？

簡單地說，一個NxN的棋盤（比如5x5），在每一個單元格上點一下，「這個格子」+「上下左右四個格子」，都會改變狀態（亮變暗，或者暗變亮），（超出邊界的忽略）。

比如，對於下圖中的N=5，點擊最左側的紅點，會使得黃色5個格子由暗變亮，再點擊中間一幅圖的紅點，自身與周圍的幾個點，由亮變暗，或由暗變亮。

要解決的第一個問題，就是對於N，能否從「全滅」的狀態，通過點擊，達到「全亮」的狀態。

答案自然是有的：

按照藍色格子依次點擊一遍即可得到「全亮」的結果

隨之產生了一系列問題，比如：

• 對於任意的N，是否總是有解？
• 如果初始狀態，棋盤上已經有些燈被點亮，能否把變成全亮，或者全滅？
• 怎樣能求出一個解？複雜度多少？（也就是需要多少的計算量）

• 如果不止一個解，有多少個？ 和N有什麼關係？ 如何求出最優解？（點擊數量最少）

這些都已經有定論，我們暫時不展開。

解決這些問題的數學理論，一般屬於大學數學一年級的範圍，矩陣高斯消元法，加上一些離散數學的基本知識。一般一個大學二年級的學生，應該可以都可以看懂。

對於比較複雜的引申問題，比如解的數量，需要用到 斐波那契多項式的一些知識（對，就是那個兩隻兔子越生越多的那個東西）。

開頭提到的兩篇文章里有不少，提到了一些演算法，數量級是O((N^2)^3)=O(N^6)，

（也有提到O(N^4.7xxx)的演算法，不過貌似沒有給出具體實現）。

尤其是對於N比較大的情況，比如N>1000，以當前的普通家用PC性能，就不夠啦。

一個問題的解決啊，當然要靠編程技巧，但是也要考慮到演算法學習的進程~！

這個問題有一個O(N^3)的解法，所以用現在的家用PC，（甚至不藉助多核），對於N<100，1秒之內找到答案（註：不是最優解），對於N=1000左右，1-2分鐘左右可以找到解。

在這個問題的宣傳上，那篇文章還有了一些偏差，你們會不會負責啊？？？我跟你講，你們這樣子啊，是不行的！我今天算是得罪你們一下~

（「遲到8年的美麗」一文的作者在初三的時候,也就是大概2006年,就自己考慮了許多的問題，並且動手做了不少工作，確實很聰明很難得……）

這個問題早在1997-1998年就被人研究過，也就是大概18年前。

並且，研究的很透徹（比如：何時有解？何時解不唯一？不唯一時，解有多少個？各種遊戲的變種等等），並非像「遲到8年的美麗」一文文章里所說得那麼晚。

值得一提的是，1998年的主流電腦，應該是類似奔騰II 233Hz，32M內存，售價要接近1萬人民幣，（對，你沒有看錯，可以去百度「1998年電腦主流配置」），現在你手裡拿著的蘋果三星華為小米等隨便一個手機，比這種電腦不知道高到哪裡去了~~~

• 這個網頁基本搜集了許多相關的信息: Lights Out Mathematics
• 兩篇主要論文在這裡：

• [AF] Turning Lights Out with Linear Algebra, by M. Anderson and T. Feil (1998). Math Magazine, vol. 71, no. 4,October 1998, pp. 300-303.

• [GTK2] CharacterizingSwitch-Setting Problems, by John Goldwasser, WilliamF. Klostermeyer, and George E. Trapp (1997). Linear and Multilinear Algebra,vol. 43, pp. 121-135.

好，我們先來看結果吧。

注意：以下對於每一個N，只是找到一個解，可以把「全滅」變成「全亮」

在N<1000的情況里，有幾乎42%的情況有不止一個解，而且解的數量很多，是指數級，通過窮舉是不太可能的。還沒有找到更好的方法來找到最優解。

下面這張圖片列出了對於N<=135時解的數量（如果N沒有列出，就表示只有唯一的解）：

比如對於N=123，因為解的數量實在太多，excel的精度都不夠了。跟不要說N>1000時的情況了。

================== 多圖警告的分界線 ============================

• 對於比較小的N，看上去大概是這個效果，就不一張一張列舉了：

• 選幾個有趣的來看看，比如N=24

• 再看N=44，中間是不是有些類似？？

• 自然少不了對稱性的美，比如N=175，181，303

• 當然，也有不那麼對稱的，比如N=383

• 隨著N的增大，圖片也越來越大，不得不縮小了尺寸再發出來。比如 N=415,487,508

• N越來越大，可以放大到局部再看看，比如N=1423，整體上看，是這樣

放大之後，左上角是這樣：

• 繼續增大，這次是N=3001，全部看是這樣：

中心部分放大之後是這樣

N<800的所有答案，去掉不對稱的情況（否則看著會太閃），製作成了一個視頻：

LightOut_matrix http://www.tudou.com/programs/view/FCc0ctBc5m4/

（請原諒視頻質量被壓縮成了渣，不太會使用土豆……）

對於這個有趣的問題，這幾天我也沒有做什麼別的，大概三件事：

一個，做了一些思考，查了一些資料，相互印證，確定了許多結論都是18年前就有定論的。

第二個，做了一些試驗，寫了一個複雜度為O(N^3)的程序，對於比較大的N，比如N=1000、2000、5000啊，也能找到了幾個解。

第三個，就是把N<1000全部找了一個解，選出其中對稱的部分，做了上面一個視頻。

很慚愧，就做了一點微小的工作，謝謝大家。

(關於數學、演算法的分析、結論等等，先忽略掉，如果有興趣的人多，我再花時間寫……)

--------------

補充1：

電腦CPU是 Intel Xeon E3-1230 V2 @ 3.30GHz，演算法沒有暫時支持多核。

N=10000，只有唯一解，用了9.65小時，

N=10005，只有唯一解，用了7.5小時。

============== 2016-06-19 更新的分界線 （多圖警告） ==============

首先換了標題畫面，因為找到了一些更有趣的圖形。

對程序稍微做了一些改進，包括兩點：

1. 對於某些N，比如N=30,N=33，之前的方法找到的往往不是（左右）對稱的，於是改進了一下，嘗試尋找一個（左右）對稱的解：

2. 對於許多的的N，可能有許多個解把這些解嘗試都變成圖片（只要找到了第一個解，基於計算結果再找到其他的就容易多了，速度很快。）

於是得到一些有趣的結果，（與之前可能有重複），比如：

N=16

N=24

N=30

N=33

N=74，有沒有覺得中間有一隻耷拉著眼睛的動物？？

還有一些對稱性很好的圖形：

N=103

N=120

N=132

因為有了左右對稱的條件，所以常常會有類似臉的圖案

N=309，大圖看上去是這樣：

其實裡面藏著小貓臉

N=309，大圖看上去是這樣：

中間偏上有：

對於N>1000的情況，基本上看大圖就是好像茫茫一片噪點，彷彿這樣：

偶爾有幾個有趣的：

N=1024

N=1087

N=1983的左下角

有趣的是，有幾個圖案確實很與二維碼有些神似，如果用手機去掃，確實會停頓一下（識別演算法嘗試工作）。當然，是掃不出什麼來的。

N=1735

N=1759

有些情況下， 解實在是太多了，比如N=0123，居然有（2^80）個解，加上『左右對稱』的限制條件之後，還有（2^40）個解，比地球上的沙子還多。（其中包括其他的對稱）

只選擇了其中幾個解，做成了一個gif來看看：

（知乎是不是不支持上傳gif？先上傳到github）

https://github.com/StrongZhu/LightOut/blob/master/gif/matrix.N_0123.gif

=========================================================

同一句話，往往可以從不同的角度去理解，得到不同的。

一個問題的解決啊，當然要靠演算法技巧，但是也要考慮到編程學習的進程~！

又稍微改進了一下程序，還使用多核的全部性能，把性能大概提高了10多倍，

現在大概能達到下面的結果：

N=1000 ： < 5秒，（之前要50秒）

N=2000 ： ~ 24秒

N=5000 ： ~ 5分鐘，（之前要1小時20分）

N=10000 ： ~ 30分鐘，（之前要9.6小時）

其實還有一種特殊的編程技巧，保守估計可以再加速20倍。

不想實現，主要是因為我懶…………呵呵

=================== 扯兩句演算法 ===================

• 「全滅」到「全亮」，對於任意的N，一定有解。
  還可以擴展到更一般的形式（如果沒有理解錯）：
  不要求這是一個NxN的方塊，可以是任何形式，只要滿足兩個規則就一定有解：
  1、（自反）按下某個單元，這個單元會改變狀態；
  2、（對稱）如果「按下單元A，會使得單元B改變狀態」，那麼一定也要能「按下單元B，單元A的狀態也改變」
  對於「已經有些單元被點亮，通過點擊達到「全亮」的情況，就不一定有解了。

• 基本思想是（GF2上，只有0,1，只有加、減、乘）高斯消元法，很只管的解法（把每個單元看做一個變數，一共有N^2個變數）的複雜度是O((N^2)^3) = O(N^6)，
• 要換個思路，先（利用分塊矩陣的性質）做一些預處理再做高斯消元法，
  才能使得時間複雜度變成O(N^3)。
• 之前的文章提到了通過矩陣快速乘法來加速，可以降低一些複雜度，但沒找到現成的解法，更主要的是，也沒想清楚怎麼能夠通過「快速矩陣乘法」，來加速「A*X=b」的高斯消元法……
• 矩陣快速乘法，過去50年有人不斷在研究，甚至這幾年也有突破，
  1969, N^2.81, strassen,
  1979, N^2.79
  1981, N^2.55
  1987, N^2.38, CW
  2014, N^2.372
  下界是N^2，越來越近。
• gf2上的高斯消元法運用面很廣，比如大整數分解、加密、模式識別，於是有人做了專門的硬體愛提高速度……居然，還有人一群人寫了演算法（遺傳演算法的變種）來尋找「矩陣快速乘法」，2015年的事，他們計算的N，大概是10^12這個量級。
  一半以上沒看懂。。。。。。
  有興趣的可以搜索："A Vector Implementation of Gaussian Elimination over GF(2): Exploring the Design-Space of Strassens Algorithm as a Case Study"

=================== github 地址 的分界線 ===================

把一些結果上傳到了github，

包括一些高清的圖片啊，一些解的txt版啊，

還有一個簡單的python程序，可以用來驗證這些解是否正確，

地址是：

https://github.com/StrongZhu/LightOut

對於這個有趣的問題，這2周我也沒有做什麼別的，大概三件事：

一個，加上「左右對稱」的條件，找到了更多的對稱解，本來想更新一下視頻，但是太懶了……（有興趣做視頻的，我可以提供原始圖片。。。）

第二個，增加了功能，對於某些N，把「所有可能的解」（如果不是『非常多』）全部繪製出來。

第三個，思考了一下編程技術，實現了一些，大幅度提高了運算速度，也為上面兩件事提供了基礎。

很慚愧，還是只做了一點微小的工作，謝謝大家。

推薦閱讀：