最強(qiáng)大腦之黑白迭代吐槽攻略v1.0

一、序言

繼續(xù)日常父女觀影，這周的“黑白迭代”游戲?qū)嶋H上就是“點(diǎn)燈游戲”的變異版，我十幾年前研究過(guò)該游戲的算法。這篇攻略將在程序算法的基礎(chǔ)上，整理出5x5、6x6、8x8方格的人工計(jì)算方法，并做適當(dāng)優(yōu)化。如果下周有空的話，就補(bǔ)齊幾種程序算法并對(duì)比算法復(fù)雜度。另外，現(xiàn)場(chǎng)比賽時(shí)采用8X8方格，實(shí)際上根據(jù)簡(jiǎn)單觀察做題的話，往往是要嘗試很多次的。比賽的題目很多選取了采用貪心策略可以做出來(lái)的，否則最壞情況下要嘗試16次，時(shí)間根本不夠，詳見(jiàn)吐槽分析章節(jié)。貪心法不好用，那么有沒(méi)有其他辦法又快又準(zhǔn)的做出來(lái)呢？答案是有的，就是要提前計(jì)算好關(guān)聯(lián)表，可以輕松解決，也就是這篇攻略的主要內(nèi)容了。

二、題目

共有8x8個(gè)電燈及對(duì)應(yīng)位置的按鈕，點(diǎn)擊一個(gè)按鈕后，這個(gè)按鈕對(duì)應(yīng)的電燈和周圍四個(gè)相鄰的電燈的狀態(tài)全部都會(huì)改變（由暗變?yōu)榱粱蛘吡磷優(yōu)榘担?。目?biāo)是通過(guò)點(diǎn)擊按鈕讓所有的電燈形成要求的圖案。

ps：游戲里貌似圖案都是軸對(duì)稱圖形，根據(jù)這點(diǎn)可以做優(yōu)化。

三、吐槽分析

為什么說(shuō)比賽時(shí)實(shí)際上是題目放水，要不然貪心法根本是無(wú)效的呢。實(shí)際上對(duì)于8x8方格的燈陣，解是唯一的。當(dāng)燈陣是軸對(duì)稱時(shí)，按鈕答案也對(duì)應(yīng)的是軸對(duì)程。（注：如果答案不是軸對(duì)稱，那么它的軸對(duì)稱答案也是正確答案并與它不同，與唯一解矛盾。）

只要選定第1行按鈕方式，都可以推算出1種n*n按鈕方式，使前n-1燈陣符合要求。但是其中只有1種第1行按鈕方式，能使第n行也滿足要求。而哪種第1行按鈕方式是正確解，是取決于全盤燈陣，而不是通過(guò)貪心法能確定的。怎么理解這段話呢？讓我們通過(guò)一個(gè)示例來(lái)說(shuō)明下。這是比賽時(shí)的一道題目，這道題就是不能用貪心法計(jì)算的。


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

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

是不是覺(jué)得正確解法有點(diǎn)神奇？實(shí)際上我甚至可以輕松編出一個(gè)前七行點(diǎn)陣圖一模一樣，但是需要第1行按鈕全點(diǎn)的圖形。

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

下面我將帶你出坑，找到1種100%能夠1次解出的方法。特別是對(duì)于軸對(duì)稱圖形，只需背幾個(gè)簡(jiǎn)單的數(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}同理。
    （簡(jiǎn)證：由于偶數(shù)次效果抵消。）
  • 引理2
    每個(gè)l_{ij}僅受該b_{ij}按鈕及四周按鈕影響，且有類似的關(guān)系式存在：l_{22}= b_{12}+b_{21}+b_{22}+b_{23}+b_{32}，其中加號(hào)為模2加，程序?qū)崿F(xiàn)可使用異或。
    （簡(jiǎn)證：可以理解為燈狀態(tài)是否改變?nèi)Q于所有能影響該燈的按鈕按下次數(shù)和的奇偶性。）
  • 引理3
    根據(jù)引理2，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=l_%7Bij%7D" alt="l_{ij}" mathimg="1">為固定變量，所以當(dāng)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}...唯一確定。
    推論 當(dāng)b_{11}, b_{12}, b_{13}...確定后，所有b_{ij}均唯一確定。

4.2 公式推導(dǎo)

以下為繁瑣的公式推導(dǎo)，沒(méi)有耐心看的可以直接跳到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，當(dāng)b_{11}, b_{12}, b_{13}...確定后，所有b_{ij}可表為b_{11}, b_{12}, b_{13}...及l_{ij}的關(guān)系式。以下為方便人工計(jì)算，將其拆為兩張表分別計(jì)算，將表中將b_{11}, b_{12}, b_{13}...簡(jiǎn)記為1,2,3...，加號(hào)省略，l_{ij}簡(jiǎn)記為ij，加號(hào)以“,”代替。
（注：計(jì)算過(guò)程中注意同樣的數(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})，說(shuō)明該行列式非滿秩，有兩個(gè)自由變量，于是不妨設(shè)b_{11}=0, b_{12}=0進(jìn)行求解。
如果考慮到圖形是軸對(duì)稱圖形，該表可進(jìn)一步化簡(jiǎn)為下表






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

（ps1：由于有兩個(gè)自由變量，所以總共有四組解。可以依次設(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，即不滿足該條件的軸對(duì)稱圖形無(wú)解。）

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

以下為軸對(duì)稱圖形的第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 實(shí)戰(zhàn)

那么，首先來(lái)個(gè)理工男的浪漫吧，點(diǎn)個(gè)心。


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



其他行推理如下：


五、 6階燈謎求解

5.1公式推導(dǎo)

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

考慮軸對(duì)稱性，直接采用簡(jiǎn)化表格。


可以看出該行列式滿秩，因此解唯一，并且解具有對(duì)稱性，可分為兩組。
按照三中方法，同理可以得到



而實(shí)際上

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 實(shí)戰(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公式推導(dǎo)

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

8階類似6階，也是滿秩的。考慮軸對(duì)稱性，直接采用簡(jiǎn)化表格。


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

求解過(guò)程略去，得解
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 實(shí)戰(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。

七、比賽技巧

可能有人要說(shuō)了，上面算出來(lái)的關(guān)聯(lián)表是好用，但是這么復(fù)雜，比賽時(shí)怎么用呀？實(shí)際上，上面的例子只需要稍加編碼，結(jié)合記憶方法，就能用起來(lái)了。
下面以最復(fù)雜的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}
按照每行進(jìn)行編碼，2^4=16，只需要一位16進(jìn)制數(shù)字就可以編碼1行。
以下是編碼結(jié)果：
b_{11}=EDE82F53
b_{12}=BDB45896
b_{13}=C0C2BB2C
b_{14}=5D517AC8
采用記憶宮殿8個(gè)樁，每個(gè)樁4個(gè)數(shù)字，就可以記住這個(gè)32位編碼。
做題時(shí)，可以對(duì)照實(shí)圖過(guò)碼，算出第1行4位正確初始值。


首先第一個(gè)編碼EDE82F53，對(duì)照實(shí)圖數(shù)數(shù)01311111=1，同理第二個(gè)編碼BDB45896，對(duì)照實(shí)圖數(shù)數(shù)11312010=1，第三個(gè)編碼C0C2BB2C，對(duì)照實(shí)圖數(shù)數(shù)00203100=0，第三個(gè)編碼5D517AC8，對(duì)照實(shí)圖數(shù)數(shù)11213000=0。

然后記住4個(gè)初始值“1100”以及實(shí)圖就可以開(kāi)始做題了。記憶實(shí)圖也可以采用此編碼方法，將圖編碼為8位數(shù)字，這樣可以提高記憶準(zhǔn)確性和持久性。（實(shí)圖可編碼為11FDF111）
開(kāi)始解題，先點(diǎn)出11000011，然后根據(jù)實(shí)圖編碼11FDF111，從第2行開(kāi)始遞推。


七、 后記

時(shí)間倉(cāng)促，簡(jiǎn)單整理了下思路寫的這篇攻略，基本上通過(guò)記憶關(guān)聯(lián)代碼，可以解決5x5、以及軸對(duì)稱的6x6、軸對(duì)稱的8x8方格燈謎。規(guī)模再增加或者無(wú)對(duì)稱性，記憶量將大大增加，不適合普通人練習(xí)（好像簡(jiǎn)單規(guī)模普通人愿意玩的也不多-_-）。

大規(guī)模的無(wú)規(guī)律復(fù)雜圖形，可以采用計(jì)算機(jī)程序求解。如果下周有空的話，我就補(bǔ)個(gè)算法，按照上述思路，首行固定推導(dǎo)加高斯消元法設(shè)計(jì)算法，復(fù)雜度應(yīng)該在O(n^3)，應(yīng)該可以輕松解決100x100方格燈謎。

另外關(guān)于n階方陣燈謎，還有很多有意思的地方。比如，數(shù)列A159257就表述了在不同n時(shí)方陣滿秩的情況（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 ），而解個(gè)數(shù)就是對(duì)應(yīng)的2的對(duì)應(yīng)數(shù)字方冪。又比如，如果你把燈全點(diǎn)亮的解顯示出來(lái)，會(huì)是十分優(yōu)美的圖案（ps再次感嘆數(shù)學(xué)之美）。




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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容