梅林的魔術方塊

本文的閱讀等級:初級

梅林 (Merlin) 是美國 Parker Brothers 公司於1978年生產的一款掌上型遊戲機 (見圖),內含六種益智遊戲,魔術方塊是其中之一[1]。遊戲機面板設有九個按鍵,布置成 3\times 3 陣列。每一個按鍵內裝一顆LED燈泡,燈號有兩種:閃爍或熄滅。按下任一按鍵可切換燈號,同時鄰近的按鍵燈號也一併自動切換。設 \bigstar 表示切換按鍵,\blacksquare 表示鄰近按鍵,\square 表示非鄰近按鍵。每一切換按鍵的鄰近按鍵定義如下:

\displaystyle \begin{array}{ccc} \bigstar\!\!&\blacksquare\!\!&\square\\ \blacksquare\!\!&\blacksquare\!\!&\square\\ \square\!\!&\square\!\!&\square \end{array}~~~~~\begin{array}{ccc} \blacksquare\!\!&\bigstar\!\!&\blacksquare\\ \square\!\!&\square\!\!&\square\\ \square\!\!&\square\!\!&\square \end{array}~~~~~\begin{array}{ccc} \square\!\!&\blacksquare\!\!&\bigstar\\ \square\!\!&\blacksquare\!\!&\blacksquare\\ \square\!\!&\square\!\!&\square \end{array}

\displaystyle \begin{array}{ccc} \blacksquare\!\!&\square\!\!&\square\\ \bigstar\!\!&\square\!\!&\square\\ \blacksquare\!\!&\square\!\!&\square \end{array}~~~~~\begin{array}{ccc} \square\!\!&\blacksquare\!\!&\square\\ \blacksquare\!\!&\bigstar\!\!&\blacksquare\\ \square\!\!&\blacksquare\!\!&\square \end{array}~~~~~\begin{array}{ccc} \square\!\!&\square\!\!&\blacksquare\\ \square\!\!&\square\!\!&\bigstar\\ \square\!\!&\square\!\!&\blacksquare \end{array}

\displaystyle \begin{array}{ccc} \square\!\!&\square\!\!&\square\\ \blacksquare\!\!&\blacksquare\!\!&\square\\ \bigstar\!\!&\blacksquare\!\!&\square \end{array}~~~~~\begin{array}{ccc} \square\!\!&\square\!\!&\square\\ \square\!\!&\square\!\!&\square\\ \blacksquare\!\!&\bigstar\!\!&\blacksquare \end{array}~~~~~\begin{array}{ccc} \square\!\!&\square\!\!&\square\\ \square\!\!&\blacksquare\!\!&\blacksquare\\ \square\!\!&\blacksquare\!\!&\bigstar \end{array}

遊戲開始時,系統產生一組隨機圖案,遊戲的目的要將初始圖案變換為生產商預設的目標圖案──除中心按鍵外,所有的周邊按鍵都在閃爍狀態。梅林魔術方塊的遊戲規則存在多樣的變化,譬如,目標圖案可以任意設定。往下閱讀前,建議讀者先體會遊戲過程。請進入線上梅林魔術方塊遊戲網站 Merlin Magic Square Game,畫面左邊顯示目標圖案,先點選方框設計個人喜好的圖案 (打勾代表燈號閃爍)。按下“Enjoy new game”,畫面右邊即出現隨機圖案,點選右圖的方框切換燈號,直到產生與左圖相同的圖案即告獲勝。

 
經過幾番嘗試,不難觀察出兩個事實。第一,任一按鍵切換兩次等於未曾切換該按鍵;第二,切換按鍵的順序並不重要。因此,遊戲者的任務在於找到必須切換的一組按鍵。我們提出下列三個問題:

  1. 給定任何初始圖案和目標圖案,是否存在致勝的切換方式?若各鍵至多切換一次,切換方式是否唯一?
  2. 如果答案是肯定的,如何設計一演算法以產生一組致勝的切換按鍵?
  3. 根據這個算法,能否推演出一套破解策略?

 
下面我們運用線性代數方法解決梅林魔術方塊問題[2]。第一步要制定便於推理的符號。令 1 表示燈閃,0 表示燈熄。例如,下圖左是給定的初始狀態,圖右是目標狀態:

\displaystyle \begin{array}{ccc} 0&1&0\\ 1&1&0\\ 1&0&1 \end{array}~~~\xrightarrow[]{~~?~~}~~~\begin{array}{ccc} 1&1&1\\ 1&0&1\\ 1&1&1 \end{array}

將按鍵位置由左至右,從上而下,依序設為 19,如下所示:

\displaystyle \begin{array}{ccc} 1&2&3\\ 4&5&6\\ 7&8&9 \end{array}

根據這個指定順序,初始圖案可用 9 維向量表示:

\displaystyle \mathbf{v}_0=(0,1,0,1,1,0,1,0,1)^T

目標圖案則為

\displaystyle \mathbf{v}_t=(1,1,1,1,0,1,1,1,1)^T

同樣地,根據切換按鍵的鄰近按鍵規則,定義下列9個切換向量:

\displaystyle\begin{aligned} \mathbf{a}_1&=(1,1,0,1,1,0,0,0,0)^T\\ \mathbf{a}_2&=(1,1,1,0,0,0,0,0,0)^T\\ \mathbf{a}_3&=(0,1,1,0,1,1,0,0,0)^T\\ \mathbf{a}_4&=(1,0,0,1,0,0,1,0,0)^T\\ \mathbf{a}_5&=(0,1,0,1,1,1,0,1,0)^T\\ \mathbf{a}_6&=(0,0,1,0,0,1,0,0,1)^T\\ \mathbf{a}_7&=(0,0,0,1,1,0,1,1,0)^T\\ \mathbf{a}_8&=(0,0,0,0,0,0,1,1,1)^T\\ \mathbf{a}_9&=(0,0,0,0,1,1,0,1,1)^T \end{aligned}

假設目前的圖案為 \mathbf{v}_jj=0,1,\ldots,遊戲者切換第 i 個按鍵,1\le i\le 9,如何以運算方式求出切換按鍵後得到的新圖案 \mathbf{v}_{j+1}?很簡單,使用模算術加法 (見“利用模算術判定可逆矩陣”)。上例中,針對初始圖案 \mathbf{v}_0,若按下第1鍵,則圖案變換顯示於下,切換鍵以底線標記:

\displaystyle \begin{array}{ccc} 0&1&0\\ 1&1&0\\ 1&0&1 \end{array}~+~\begin{array}{ccc} \underline{1}&1&0\\ 1&1&0\\ 0&0&0 \end{array}~\to~\begin{array}{ccc} 1&0&0\\ 0&0&0\\ 1&0&1 \end{array}

對應的算式如下:

\displaystyle\begin{aligned} \mathbf{v}_0+\mathbf{a}_1&=(0,1,0,1,1,0,1,0,1)^T+(1,1,0,1,1,0,0,0,0)^T\\ &=(1,2,0,2,2,0,1,0,1)^T\\ &\equiv(1,0,0,0,0,0,1,0,1)^T\pmod 2.\end{aligned}

為簡化模算術的表達,定義有限體 \mathbb{F}_2=\{0,1\} 的加法和乘法運算 (見“有限體與模算術”),如下表:

\begin{array}{cccc} +&\vline& 0 & 1\\ \hline 0&\vline& 0& 1\\ 1&\vline& 1& 0 \end{array}~~~~~~~~~~\begin{array}{cccc} \cdot &\vline& 0 & 1\\ \hline 0&\vline& 0& 0\\ 1&\vline& 0& 1 \end{array}

提醒讀者,這裡我們考慮的向量空間並非以往慣用的 \mathbb{R}^9,而是 \mathbb{F}_2^9

 
\mathbf{x}=(x_1,\ldots,x_9)^T 代表所選擇的切換鍵向量,其中 x_i=1 若切換第 i 鍵,否則 x_i=0。梅林魔術方塊遊戲的目標即在於找出致勝切換鍵向量 \mathbf{x} 使得

\displaystyle \mathbf{v}_t-\mathbf{v}_0=x_1\mathbf{a}_1+\cdots+x_9\mathbf{a}_9=\begin{bmatrix} \mathbf{a}_1&\cdots&\mathbf{a}_9 \end{bmatrix}\begin{bmatrix} x_1\\ \vdots\\ x_9 \end{bmatrix}=A\mathbf{x}

其中

\displaystyle A=\begin{bmatrix} 1&1&0&1&0&0&0&0&0\\ 1&1&1&0&1&0&0&0&0\\ 0&1&1&0&0&1&0&0&0\\ 1&0&0&1&1&0&1&0&0\\ 1&0&1&0&1&0&1&0&1\\ 0&0&1&0&1&1&0&0&1\\ 0&0&0&1&0&0&1&1&0\\ 0&0&0&0&1&0&1&1&1\\ 0&0&0&0&0&1&0&1&1 \end{bmatrix}

請注意,9\times 9 階常數矩陣 A 完全由遊戲規則決定,與初始圖案或目標圖案無關。計算得到 \det A=5,故 \det A\equiv 1\pmod 2。因為 \det A\neq 0,對於任意初始圖案 \mathbf{v}_0 和目標圖案 \mathbf{v}_t,線性方程 A\mathbf{x}=\mathbf{v}_t-\mathbf{v}_0 (在 \mathbb{F}_2) 必定存在唯一解。

 
接著說明如何計算定義於 \mathbb{F}_2 的逆矩陣 A^{-1}。使用逆矩陣公式 A^{-1}=(\det A)^{-1}\text{adj}A,定義於實數系的逆矩陣為

\displaystyle \frac{1}{5}\left[\!\!\begin{array}{rrrrrrrrr} -1&2&-1&2&2&-3&-1&-3&4\\ 3&-1&3&-1&-1&-1&-2&4&-2\\ -1&2&-1&-3&2&2&4&-3&-1\\ 3&-1&-2&-1&-1&4&3&-1&-2\\ -1&2&-1&2&-3&2&-1&2&-1\\ -2&-1&3&4&-1&-1&-2&-1&3\\ -1&-3&4&2&2&-3&-1&2&-1\\ -2&4&-2&-1&-1&-1&3&-1&3\\ 4&-3&-1&-3&2&2&-1&2&-1 \end{array}\!\!\right]

因為 (\det A)^{-1}(\det A)\equiv 1\pmod 2,立知 (\det A)^{-1}\equiv 1\pmod 2,設偶數元為 0,奇數元設為 1,立得

\displaystyle A^{-1}=\begin{bmatrix} 1&0&1&0&0&1&1&1&0\\ 1&1&1&1&1&1&0&0&0\\ 1&0&1&1&0&0&0&1&1\\ 1&1&0&1&1&0&1&1&0\\ 1&0&1&0&1&0&1&0&1\\ 0&1&1&0&1&1&0&1&1\\ 1&1&0&0&0&1&1&0&1\\ 0&0&0&1&1&1&1&1&1\\ 0&1&1&1&0&0&1&0&1 \end{bmatrix}

上例中,代入給定的初始圖案和目標圖案,解出

\displaystyle \mathbf{x}=A^{-1}(\mathbf{v}_t-\mathbf{v}_0)=A^{-1}(1,0,1,0,1,1,0,1,0)^T=(0,0,1,1,1,0,0,1,1)^T

也就是說,致勝的切換按鍵為 3, 4, 5, 8, 9。下圖顯示從初始圖案至目標圖案的變換過程,切換鍵以底線標記:

\displaystyle \begin{array}{ccc} 0&1&\underline{0}\\ 1&1&0\\ 1&0&1 \end{array}~\to~\begin{array}{ccc} 0&0&1\\ \underline{1}&0&1\\ 1&0&1 \end{array}~\to~\begin{array}{ccc} 1&0&1\\ 0&\underline{0}&1\\ 0&0&1 \end{array}~\to~\begin{array}{ccc} 1&1&1\\ 1&1&0\\ 0&\underline{1}&1 \end{array}~\to~\begin{array}{ccc} 1&1&1\\ 1&1&0\\ 1&0&\underline{0} \end{array}~\to~\begin{array}{ccc} 1&1&1\\ 1&0&1\\ 1&1&1 \end{array}

 
從上述算法不難推演出一套容易施行的致勝策略[3]。根據對稱性,我們將9個按鍵分為三類:邊按鍵 2,4,6,8,角按鍵 1,3,7,9,以及中心按鍵 5。首先考慮邊按鍵。令差異向量 \mathbf{w}=\mathbf{v}_t-\mathbf{v}_0。寫出 \mathbf{x}=A^{-1}\mathbf{w} 的邊按鍵算式

\displaystyle \begin{bmatrix} *\\ x_2\\ *\\ x_4\\ *\\ x_6\\ *\\ x_8\\ * \end{bmatrix}=\begin{bmatrix} *&*&*&*&*&*&*&*&*\\ 1&1&1&1&1&1&0&0&0\\ *&*&*&*&*&*&*&*&*\\ 1&1&0&1&1&0&1&1&0\\ *&*&*&*&*&*&*&*&*\\ 0&1&1&0&1&1&0&1&1\\ *&*&*&*&*&*&*&*&*\\ 0&0&0&1&1&1&1&1&1\\ *&*&*&*&*&*&*&*&* \end{bmatrix}\begin{bmatrix} w_1\\ w_2\\ w_3\\ w_4\\ w_5\\ w_6\\ w_7\\ w_8\\ w_9 \end{bmatrix}

每一個邊按鍵切換與否 (即 x_2,x_4,x_6,x_8 的值),由 \mathbf{w} 的6個元決定,它們恰好形成長方形,稱為相關長方形。下圖顯示每一邊按鍵 \bigstar 的相關長方形,以 \blacksquare 表示:

\displaystyle \begin{array}{ccc} \blacksquare\!\!&\bigstar\!\!&\blacksquare\\ \blacksquare\!\!&\blacksquare\!\!&\blacksquare\\ \square\!\!&\square\!\!&\square \end{array}~~~~~ \begin{array}{ccc} \blacksquare\!\!&\blacksquare\!\!&\square\\ \bigstar\!\!&\blacksquare\!\!&\square\\ \blacksquare\!\!&\blacksquare\!\!&\square \end{array}~~~~~ \begin{array}{ccc} \square\!\!&\blacksquare\!\!&\blacksquare\\ \square\!\!&\blacksquare\!\!&\bigstar\\ \square\!\!&\blacksquare\!\!&\blacksquare \end{array}~~~~~ \begin{array}{ccc} \square\!\!&\square\!\!&\square\\ \blacksquare\!\!&\blacksquare\!\!&\blacksquare\\ \blacksquare\!\!&\bigstar\!\!&\blacksquare \end{array}

以邊按鍵2為例,若 w_1+\cdots+w_6=1,則 x_2=1,否則 x_2=0。我們得到第一條規則:對於一邊按鍵,如果目前圖案與目標圖案的相關長方形閃爍燈號有不同的奇偶數,則切換該邊按鍵。沿用上例說明,下圖左是目標圖案,圖右顯示從初始圖案起,切換邊按鍵4,8的變換過程:

\displaystyle \begin{array}{ccc} 1&1&1\\ 1&0&1\\ 1&1&1 \end{array}~~~~~~~ \begin{array}{ccc} 0&1&0\\ \underline{1}&1&0\\ 1&0&1 \end{array}~\to~\begin{array}{ccc} 1&1&0\\ 0&1&0\\ 0&\underline{0}&1 \end{array}~\to~\begin{array}{ccc} 1&1&0\\ 0&1&0\\ 1&1&0 \end{array}

接下來考慮角按鍵的切換法。因為角按鍵彼此獨立互不影響,直接比對目前圖案與目標圖案的燈號即可,我們有了第二個規則:對於一角按鍵,如果目前圖案的燈號不同於目標圖案的燈號,則切換該角按鍵。延續上例,下圖左是目標圖案,圖右顯示切換角按鍵3,9的變換過程:

\displaystyle \begin{array}{ccc} 1&1&1\\ 1&0&1\\ 1&1&1 \end{array}~~~~~~~ \begin{array}{ccc} 1&1&\underline{0}\\ 0&1&0\\ 1&1&0 \end{array}~\to~\begin{array}{ccc} 1&0&1\\ 0&0&1\\ 1&1&\underline{0} \end{array}~\to~\begin{array}{ccc} 1&0&1\\ 0&1&0\\ 1&0&1 \end{array}

最後剩下中心按鍵。同樣地,第三個規則說:如果目前圖案的中心燈號不同於目標圖案的中心燈號,則切換中心按鍵。上例的最末一個步驟顯示於下:

\displaystyle \begin{array}{ccc} 1&1&1\\ 1&0&1\\ 1&1&1 \end{array}~~~~~~~ \begin{array}{ccc} 1&0&1\\ 0&\underline{1}&0\\ 1&0&1 \end{array}~\to~\begin{array}{ccc} 1&1&1\\ 1&0&1\\ 1&1&1 \end{array}

 
我們整理出梅林魔術方塊的致勝策略。當下列情況發生時,切換按鍵:

  1. 邊按鍵:目前圖案與目標圖案的相關長方形閃爍燈號有不同的奇偶數。
  2. 角按鍵:目前圖案的燈號不同於目標圖案的燈號。
  3. 中心按鍵:目前圖案的燈號不同於目標圖案的燈號。

 
參考來源:
[1] 維基百科:Merlin magic square
[2] Don Pelletier, Merlin’s magic square, The American Mathematical Monthly, vol. 94, no. 2, 1987, pp 143-150.
[3] Daniel L. Stock, Merlin’s magic square revisited, The American Mathematical Monthly, vol. 96, no. 7, 1989, pp 608-610.

This entry was posted in 線性代數專欄, 應用之道 and tagged , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s