更新時間：2022-07-02 17:07:44作者：佚名
這是一個有趣的問題。在8年前，當(dāng)我還是個初三的孩子時，我曾經(jīng)探索過這個問題。（鏈接如下：
有關(guān)“十全十美”的研究
，我的ID “仙靈魂”，當(dāng)時還是吧主）
當(dāng)時用文曲星的 計算到n=14，因為文曲星性能問題沒有繼續(xù)算下去。
在這里貼一下當(dāng)時（2006年）的一些結(jié)論。
（1）顯然，點燈游戲的解，和點下方格的次序無關(guān)，僅和點下方格的位置有關(guān)。
（2）在一個方格下累計點下兩次，和沒有點下過的效果是一樣的。所以最優(yōu)解必然只是在某些格子下點下過一次。
（3）當(dāng)?shù)?行被點下的格子確定時，若存在方案，則方案唯一。
這是因為一個格子（坐標(biāo)[a,b]）的燈是否點亮只和其初始狀態(tài)以及以下五個點：
[a-1,b][a,b-1][a,b][a,b+1][a+1,b]是否被點下有關(guān)，其中只有[a+1,b]是位于第a+1行，其它均在第a行之前。
舉例說明：如下圖所示
5×5的方格，假設(shè)紫色格一開始是暗的，我的目標(biāo)是把它點亮，而前兩行點下的位置已經(jīng)確定（如圖中的1），那么由于紫色格的狀態(tài)只與自身以及周圍4個被按下次數(shù)有關(guān)（總和應(yīng)是奇數(shù)），而綠格和紫格累計被按下2次，所以在第3行，紅色格必須被按下。
所以，當(dāng)我固定了第一行的點燈位置（共
種狀態(tài)，考慮對稱性的話能去掉接近一半的狀態(tài)），那么，剩下的步驟是確定的，點完第n行可以讓第n-1行的燈全亮，所以，我可以確保除最后一行外，所有位置的燈都能點亮，而最后一行是否恰好都被點亮，要看天意。但是暴力求解并不麻煩。
（4）因為題主說初始亮燈位置隨機，所以沒有確定的解，甚至是否一定有解也不能確定（這點待證明）心有千千結(jié)游戲規(guī)則，只能按照（3）的方法一一嘗試。但是如果初始狀態(tài)是全部燈暗，是有確定方案的。
如，5×5共有4個解，如果考慮對稱性和旋轉(zhuǎn)性，此解是唯一的。
下面是5×5的方案，可以看到，它在斜對角線有一條對稱軸：
（5）這個問題其實很棘手。即使用計算機算心有千千結(jié)游戲規(guī)則，在我目前的算法下，復(fù)雜度達(dá)到了
，隨著n的增大，復(fù)雜度指數(shù)增長，所以能算得的n也并不是太大，一般微機在一天之內(nèi)能算到n=33大約就已經(jīng)是極限了。當(dāng)然算法可能還有改進(jìn)空間。
（6）由于這個問題確實很有趣（很美~），八年后的今天，我又重啟了對這個問題的探索。
具體結(jié)果請移步
點燈游戲：遲到8年的美麗，用數(shù)學(xué)繪制的“二維碼”！ - 看！你身邊有一只數(shù)學(xué)！ - 知乎專欄
鞠躬~