## 梅林的魔術方塊

$\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}$

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

$\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}$

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

$\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$

\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}

$\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}

$\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}$

$\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}$

$\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]$

$\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$

$\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}$

$\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}$

$\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}$

$\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}$

$\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.