一迎吵、序言

繼續(xù)日常父女觀影，這周的“黑白迭代”游戲?qū)嶋H上就是“點燈游戲”的變異版针贬，我十幾年前研究過該游戲的算法击费。這篇攻略將在程序算法的基礎(chǔ)上，整理出5x5桦他、6x6蔫巩、8x8方格的人工計算方法，并做適當優(yōu)化快压。如果下周有空的話批幌，就補齊幾種程序算法并對比算法復雜度。另外嗓节，現(xiàn)場比賽時采用8X8方格，實際上根據(jù)簡單觀察做題的話皆警，往往是要嘗試很多次的拦宣。比賽的題目很多選取了采用貪心策略可以做出來的诱渤，否則最壞情況下要嘗試16次固灵，時間根本不夠袱瓮，詳見吐槽分析章節(jié)汛骂。貪心法不好用记某，那么有沒有其他辦法又快又準的做出來呢场绿？答案是有的扼仲，就是要提前計算好關(guān)聯(lián)表寺董，可以輕松解決菊值，也就是這篇攻略的主要內(nèi)容了外驱。

二育灸、題目

共有8x8個電燈及對應位置的按鈕，點擊一個按鈕后昵宇，這個按鈕對應的電燈和周圍四個相鄰的電燈的狀態(tài)全部都會改變（由暗變?yōu)榱粱蛘吡磷優(yōu)榘担┌跽浮Ｄ繕耸峭ㄟ^點擊按鈕讓所有的電燈形成要求的圖案。

ps：游戲里貌似圖案都是軸對稱圖形瓦哎，根據(jù)這點可以做優(yōu)化砸喻。

三、吐槽分析

為什么說比賽時實際上是題目放水蒋譬，要不然貪心法根本是無效的呢割岛。實際上對于8x8方格的燈陣，解是唯一的犯助。當燈陣是軸對稱時癣漆，按鈕答案也對應的是軸對程。（注：如果答案不是軸對稱也切，那么它的軸對稱答案也是正確答案并與它不同扑媚，與唯一解矛盾。）

只要選定第1行按鈕方式雷恃，都可以推算出1種n*n按鈕方式疆股，使前n-1燈陣符合要求。但是其中只有1種第1行按鈕方式倒槐，能使第n行也滿足要求旬痹。而哪種第1行按鈕方式是正確解，是取決于全盤燈陣讨越，而不是通過貪心法能確定的两残。怎么理解這段話呢？讓我們通過一個示例來說明下把跨。這是比賽時的一道題目人弓，這道題就是不能用貪心法計算的。

對于該圖中的前兩行有多種解法可以滿足要求（實際上共有16種）

實際上這16種方法只有1種是正確的着逐，而這題用貪心法往往選擇的是方法一崔赌，那么這題最終正確解法是什么呢？

是不是覺得正確解法有點神奇耸别？實際上我甚至可以輕松編出一個前七行點陣圖一模一樣健芭，但是需要第1行按鈕全點的圖形。

綜上所述秀姐，比賽題目放水慈迈，不然盲試的話，按期望值平均得嘗試8次才有可能解出省有。

下面我將帶你出坑痒留，找到1種100%能夠1次解出的方法谴麦。特別是對于軸對稱圖形，只需背幾個簡單的數(shù)字代碼就可以輕松解答狭瞎。

四细移、 5階燈謎精確求解

4.1約定及引理

約定
將第1行的按鈕按下次數(shù)分別依次記為 $b_{11}, b_{12}, b_{13}...b_{21}, b_{22}, b_{23}...b_{31}, b_{32}, b_{33}...$ ，將電燈狀態(tài)是否改變按矩陣編碼為 $l_{11}, l_{12}, l_{13}...l_{21}, l_{22}, l_{23}...l_{31}, l_{32}, l_{33}...$ 熊锭。
引理1
$b_i$ 只需記0, 1值弧轧， $l_{ij}$ 同理。
（簡證：由于偶數(shù)次效果抵消碗殷。）
引理2
每個 $l_{ij}$ 僅受該 $b_{ij}$ 按鈕及四周按鈕影響精绎，且有類似的關(guān)系式存在： $l_{22}= b_{12}+b_{21}+b_{22}+b_{23}+b_{32}$ ，其中加號為模2加锌妻，程序?qū)崿F(xiàn)可使用異或代乃。
（簡證：可以理解為燈狀態(tài)是否改變?nèi)Q于所有能影響該燈的按鈕按下次數(shù)和的奇偶性。）
引理3
根據(jù)引理2仿粹，因為 $l_{ij}$ 為固定變量搁吓，所以當 $b_{(i-1)1}, b_{(i-1)2}, b_{(i-1)3}...b_{i1}, b_{i2}, b_{i3}...$ 確定后， $b_{(i+1)1}, b_{(i+1)2}, b_{(i+1)3}...$ 唯一確定吭历。
推論當 $b_{11}, b_{12}, b_{13}...$ 確定后堕仔，所有 $b_{ij}$ 均唯一確定。

4.2 公式推導

以下為繁瑣的公式推導晌区，沒有耐心看的可以直接跳到4.3看結(jié)論摩骨。

$l_{11}=b_{11}+b_{12}+b_{21} \implies b_{21}=b_{11}+b_{12}+l_{11}$
$l_{12}=b_{11}+b_{12}+b_{13}+b_{22} \implies b_{22}=b_{11}+b_{12}+b_{13}+l_{12}$
$l_{13}=b_{12}+b_{13}+b_{14}+b_{23} \implies b_{23}=b_{12}+b_{13}+b_{14}+l_{13}$

如同引理3，當 $b_{11}, b_{12}, b_{13}...$ 確定后朗若，所有 $b_{ij}$ 可表為 $b_{11}, b_{12}, b_{13}...$ 及 $l_{ij}$ 的關(guān)系式恼五。以下為方便人工計算，將其拆為兩張表分別計算哭懈，將表中將 $b_{11}, b_{12}, b_{13}...$ 簡記為 $1,2,3...$ 灾馒，加號省略， $l_{ij}$ 簡記為 $ij$ 遣总，加號以“,”代替你虹。
（注：計算過程中注意同樣的數(shù)值兩次可抵消，如 $b_{12}+b_{13}+b_{14}+b_{13}+b_{15}=b_{12}+b_{14}+b_{15}$ ）

即有
$b_{12}+b_{13}+b_{15}=l_{15}+l_{22}+l_{23}+l_{24}+l_{31}+l_{33}+l_{41}+l_{42}+l_{51}$
$b_{11}+b_{12}+b_{13}=l_{14}+l_{21}+l_{22}+l_{24}+l_{25}+l_{34}+l_{41}+l_{42}+l_{43}+l_{52}$
$b_{11}+b_{12}+b_{14}+b_{15}=l_{13}+l_{21}+l_{23}+l_{25}+l_{31}+l_{35}+l_{42}+l_{43}+l_{44}+l_{53}$
而 $b_{13}+b_{14}+b_{15}=(b_{11}+b_{12}+b_{13})+(b_{11}+b_{12}+b_{14}+b_{15})$ 彤避， $b_{11}+b_{13}+b_{14}=(b_{12}+b_{13}+b_{15})+(b_{11}+b_{12}+b_{14}+b_{15})$ ，說明該行列式非滿秩夯辖，有兩個自由變量琉预，于是不妨設(shè) $b_{11}=0, b_{12}=0$ 進行求解。
如果考慮到圖形是軸對稱圖形蒿褂，該表可進一步化簡為下表

至此為止圆米，已經(jīng)快速的找到其中一組解卒暂。

（ps1：由于有兩個自由變量，所以總共有四組解娄帖∫察簦可以依次設(shè) $b_{11}=0, b_{12}=1$ 或 $b_{11}=1, b_{12}=0$ 或 $b_{11}=1, b_{12}=1$ 即可解出其他三組解。）

（ps2：注意到 $b_{11}+b_{12}+b_{13}=l_{12}+l_{32}+l_{41}+l_{42}+l_{43}+l_{52}$
$b_{11}+b_{12}+b_{14}+b_{15}=l_{13}+l_{23}+l_{43}+l_{53}$
$b_{13}+b_{14}+b_{15}=l_{12}+l_{32}+l_{41}+l_{42}+l_{43}+l_{52}$
以及 $b_{13}+b_{14}+b_{15}=(b_{11}+b_{12}+b_{13})+(b_{11}+b_{12}+b_{14}+b_{15})$ 近速，所以有
$l_{13}+l_{23}+l_{43}+l_{53}=0$ 诈嘿，即不滿足該條件的軸對稱圖形無解。）

4.3 結(jié)論總結(jié)

以下為軸對稱圖形的第1行的1組解削葱，其他行可順推奖亚。
$b_{11}=b_{12}=0$
$b_{13}=l_{12}+l_{32}+l_{41}+l_{42}+l_{43}+l_{52}$
$b_{14}=b_{15}=l_{11}+l_{12}+l_{23}+l_{31}+l_{32}+l_{33}+l_{43}+l_{52}$

4.4 實戰(zhàn)

那么，首先來個理工男的浪漫吧析砸，點個心昔字。

直接套公式，第1行按鈕狀態(tài)為

其他行推理如下：

五首繁、 6階燈謎求解

5.1公式推導

以下為繁瑣的公式推導作郭，沒有耐心看的可以直接跳到5.2看結(jié)論。

考慮軸對稱性弦疮，直接采用簡化表格夹攒。

可以看出該行列式滿秩，因此解唯一挂捅，并且解具有對稱性芹助，可分為兩組。
按照三中方法闲先，同理可以得到

而實際上

5.2 結(jié)論總結(jié)

$b_{11}=b_{16}=l_{12}+l_{13}+l_{23}+l_{33}+l_{42}+l_{43}+l_{51}+l_{61}+l_{63}$
$b_{12}=b_{15}=l_{11}+l_{12}+l_{22}+l_{23}+l_{32}+l_{33}+l_{41}+l_{42}+l_{52}+l_{63}$
$b_{13}=b_{14}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{23}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}$

5.3 實戰(zhàn)

例一

$b_{11}=l_{12}+l_{13}+l_{23}+l_{33}+l_{42}+l_{43}+l_{51}+l_{61}+l_{63}$
$=1+1+1+1+0+1+0+1+1=1$
$b_{12}=l_{11}+l_{12}+l_{22}+l_{23}+l_{32}+l_{33}+l_{41}+l_{42}+l_{52}+l_{63}$
$=1+1+1+1+0+1+0+0+1+1=1$
$b_{13}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{23}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}$
$=1+1+1+0+1+1+0+0+1+0+1+1+1=1$
所以第1行按鈕為111111状土。
例二

$b_{11}=l_{12}+l_{13}+l_{23}+l_{33}+l_{42}+l_{43}+l_{51}+l_{61}+l_{63}$
$=1+1+1+1+1+1+0+0+1=1$
$b_{12}=l_{11}+l_{12}+l_{22}+l_{23}+l_{32}+l_{33}+l_{41}+l_{42}+l_{52}+l_{63}$
$=1+1+1+1+1+1+0+1+0+1=0$
$b_{13}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{23}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}$
$=1+1+1+1+1+1+0+1+1+0+1+0+0=1$
所以第1行按鈕為101101。

六伺糠、 8階燈謎求解

6.1公式推導

以下為繁瑣的公式推導蒙谓，沒有耐心看的可以直接跳到6.2看結(jié)論。

8階類似6階训桶，也是滿秩的累驮。考慮軸對稱性舵揭，直接采用簡化表格谤专。

6.2 結(jié)論總結(jié)

求解過程略去，得解
$b_{11}=b_{18}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{24}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}+l_{63}+l_{64}+l_{72}+l_{74}+l_{83}+l_{84}$
$b_{12}=b_{17}=l_{11}+l_{13}+l_{14}+l_{21}+l_{22}+l_{24}+l_{31}+l_{33}+l_{34}+l_{42}+l_{52}+l_{54}+l_{61}+l_{71}+l_{74}+l_{82}+l_{83}$
$b_{13}=b_{16}=l_{11}+l_{12}+l_{31}+l_{32}+l_{43}+l_{51}+l_{53}+l_{54}+l_{61}+l_{63}+l_{64}+l_{73}+l_{81}+l_{82}$
$b_{14}=b_{15}=l_{12}+l_{14}+l_{21}+l_{22}+l_{24}+l_{32}+l_{34}+l_{44}+l_{52}+l_{53}+l_{54}+l_{61}+l_{63}+l_{71}+l_{72}+l_{81}$

6.3 實戰(zhàn)

$b_{11}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{24}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}+l_{63}+l_{64}+l_{72}+l_{74}+l_{83}+l_{84}$
$=0+0+1+0+1+0+0+0+0+1+1+0+1+1+0+0+0+1+1=0$
$b_{12}=l_{11}+l_{13}+l_{14}+l_{21}+l_{22}+l_{24}+l_{31}+l_{33}+l_{34}+l_{42}+l_{52}+l_{54}+l_{61}+l_{71}+l_{74}+l_{82}+l_{83}$
$=0+1+0+0+1+0+0+0+1+0+0+0+0+1+0+0+1=1$
$b_{13}=l_{11}+l_{12}+l_{31}+l_{32}+l_{43}+l_{51}+l_{53}+l_{54}+l_{61}+l_{63}+l_{64}+l_{73}+l_{81}+l_{82}$
$=0+0+0+0+0+1+1+0+0+1+0+0+1+0=0$
$b_{14}=l_{12}+l_{14}+l_{21}+l_{22}+l_{24}+l_{32}+l_{34}+l_{44}+l_{52}+l_{53}+l_{54}+l_{61}+l_{63}+l_{71}+l_{72}+l_{81}$
$=0+0+0+1+0+0+1+0+0+1+0+0+1+1+0+1=0$
所以第1行按鈕為01000010午绳。

七置侍、比賽技巧

可能有人要說了，上面算出來的關(guān)聯(lián)表是好用，但是這么復雜蜡坊，比賽時怎么用呀杠输？實際上，上面的例子只需要稍加編碼秕衙，結(jié)合記憶方法蠢甲，就能用起來了。
下面以最復雜的8階燈謎為例据忘，
$b_{11}=l_{11}+l_{12}+l_{13}+l_{21}+l_{22}+l_{24}+l_{31}+l_{32}+l_{33}+l_{41}+l_{53}+l_{61}+l_{62}+l_{63}+l_{64}+l_{72}+l_{74}+l_{83}+l_{84}$
$b_{12}=l_{11}+l_{13}+l_{14}+l_{21}+l_{22}+l_{24}+l_{31}+l_{33}+l_{34}+l_{42}+l_{52}+l_{54}+l_{61}+l_{71}+l_{74}+l_{82}+l_{83}$
$b_{13}=l_{11}+l_{12}+l_{31}+l_{32}+l_{43}+l_{51}+l_{53}+l_{54}+l_{61}+l_{63}+l_{64}+l_{73}+l_{81}+l_{82}$
$b_{14}=l_{12}+l_{14}+l_{21}+l_{22}+l_{24}+l_{32}+l_{34}+l_{44}+l_{52}+l_{53}+l_{54}+l_{61}+l_{63}+l_{71}+l_{72}+l_{81}$
按照每行進行編碼鹦牛， $2^4=16$ ，只需要一位16進制數(shù)字就可以編碼1行若河。
以下是編碼結(jié)果：
$b_{11}=EDE82F53$
$b_{12}=BDB45896$
$b_{13}=C0C2BB2C$
$b_{14}=5D517AC8$
采用記憶宮殿8個樁能岩，每個樁4個數(shù)字，就可以記住這個32位編碼萧福。
做題時拉鹃，可以對照實圖過碼，算出第1行4位正確初始值鲫忍。

首先第一個編碼EDE82F53膏燕，對照實圖數(shù)數(shù)01311111=1，同理第二個編碼BDB45896悟民，對照實圖數(shù)數(shù)11312010=1坝辫，第三個編碼C0C2BB2C，對照實圖數(shù)數(shù)00203100=0射亏，第三個編碼5D517AC8近忙，對照實圖數(shù)數(shù)11213000=0。

然后記住4個初始值“1100”以及實圖就可以開始做題了智润。記憶實圖也可以采用此編碼方法及舍，將圖編碼為8位數(shù)字，這樣可以提高記憶準確性和持久性窟绷。（實圖可編碼為11FDF111）
開始解題锯玛，先點出11000011，然后根據(jù)實圖編碼11FDF111兼蜈，從第2行開始遞推攘残。

七、后記

時間倉促为狸，簡單整理了下思路寫的這篇攻略歼郭，基本上通過記憶關(guān)聯(lián)代碼，可以解決5x5辐棒、以及軸對稱的6x6病曾、軸對稱的8x8方格燈謎姊途。規(guī)模再增加或者無對稱性，記憶量將大大增加知态，不適合普通人練習（好像簡單規(guī)模普通人愿意玩的也不多-_-）。

大規(guī)模的無規(guī)律復雜圖形立叛，可以采用計算機程序求解负敏。如果下周有空的話，我就補個算法秘蛇，按照上述思路其做，首行固定推導加高斯消元法設(shè)計算法，復雜度應該在 $O(n^3)$ 赁还，應該可以輕松解決100x100方格燈謎妖泄。

另外關(guān)于n階方陣燈謎，還有很多有意思的地方艘策。比如蹈胡，數(shù)列A159257就表述了在不同n時方陣滿秩的情況（0, 0, 0, 4, 2, 0, 0, 0, 8, 0, 6, 0, 0, 4, 0, 8, 2, 0, 16, 0, 0, 0, 14, 4, 0, 0, 0, 0, 10, 20, 0, 20, 16, 4, 6, 0, 0, 0, 32, 0, 2, 0, 0, 4, 0, 0, 30, 0, 8, 8, 0, 0, 2, 4, 0, 0, 0, 0, 22, 0, 40, 24, 0, 28, 42, 0, 32, 0, 8, 0, 14, 0, 0, 4, 0, 0, 2, 0, 64, 0, 0, 0, 6, 12, 0, 0, 0, 0, 10, 0, 0, 20, 0, 4, 62, 0, 0, 20, 16, 0, 18, 0, 0, 4, 0, 0, 6, 0, 8, 0, 0, 0, 2, 4, 0, 0, 0, 8, 46, 0, 0, 0, 80, 4, 50, 56, 0, 56, 56, 0 ），而解個數(shù)就是對應的2的對應數(shù)字方冪朋蔫。又比如罚渐，如果你把燈全點亮的解顯示出來，會是十分優(yōu)美的圖案（ps再次感嘆數(shù)學之美）驯妄。

該圖為網(wǎng)圖荷并，感謝原作者。

最強大腦之黑白迭代吐槽攻略v1.0

最強大腦之黑白迭代吐槽攻略v1.0

一迎吵、序言

二育灸、題目

三、吐槽分析

四细移、 5階燈謎精確求解

4.1約定及引理

4.2 公式推導

4.3 結(jié)論總結(jié)

4.4 實戰(zhàn)

五首繁、 6階燈謎求解

5.1公式推導

5.2 結(jié)論總結(jié)

5.3 實戰(zhàn)

六伺糠、 8階燈謎求解

6.1公式推導

6.2 結(jié)論總結(jié)

6.3 實戰(zhàn)

七置侍、比賽技巧

七、后記

最強大腦之黑白迭代吐槽攻略v1.0

一迎吵、序言

二育灸、題目

三、吐槽分析

四细移、 5階燈謎精確求解

4.1約定及引理

4.2 公式推導

4.3 結(jié)論總結(jié)

4.4 實戰(zhàn)

五首繁、 6階燈謎求解

5.1公式推導

5.2 結(jié)論總結(jié)

5.3 實戰(zhàn)

六伺糠、 8階燈謎求解

6.1公式推導

6.2 結(jié)論總結(jié)

6.3 實戰(zhàn)

七置侍、比賽技巧

七、 后記

七、后記