熄燈謎題

一種單人遊戲，在燈的矩形格子上進行，燈可以開啟和關閉。一步操作包括翻轉其中一個方格內的“開關”，從而切換該方格以及所有垂直和水平相鄰方格的開/關狀態。從隨機選擇的燈光模式開始，目標是關閉所有燈。確定是否有可能從所有燈都亮的狀態開始到所有燈都關閉的狀態，這個問題被稱為“全亮問題”。正如 Sutner (1989) 所證明的，對於正方形格子，這總是可能的 (Rangel-Mondragon)。

這可以轉化為以下代數問題。

1. 每個燈的配置可以看作是一個矩陣 ，其條目在 中（即，一個 (0,1)-矩陣，其中每個 1 代表一個亮著的燈，0 代表一個關閉的燈。例如，對於 的情況，

2. 放置在 處的開關動作可以解釋為矩陣加法 ，其中 是矩陣，其中唯一等於 1 的條目是那些放置在 和相鄰位置的條目；本質上有三種不同型別的矩陣 ，取決於 是角條目，

邊條目，

或中間條目，

3. 由於矩陣加法是可交換的，因此執行移動的順序是無關緊要的。

4. 每個獲勝的移動組合都可以用數學形式表示為

這裡， 表示 零矩陣，它對應於所有燈都關閉的情況，並且每個係數 表示開關 必須按下的次數。因為我們正在求解方程（模 2），所以它們可以用等價形式寫成

此外，僅考慮 0 和 1 作為 的唯一可能值就足夠了。因此，上面的等式實際上是域 上未定元 中的線性方程組。

例如，對應於初始（左側）燈光模式的系統可以寫成

它有恰好一個解：(, , )，這意味著透過按下開關 , , , 和 （對應於上圖中的紅點）來解決遊戲。由於上述方程組的矩陣具有最大秩（它是一個行列式非零的 矩陣），因此在 -格子上的遊戲總是可解的。

一般來說， 格子的可解模式是那些透過按下某些開關從無燈模式獲得的模式。用線性代數的語言來說，它們是作為某些矩陣 之和的 -矩陣。例如，上面說明了 -格子的可解模式。尺寸為 或更小的所有其他矩形對於每種可能的起始模式都是可解的。

有時可能存在多個解。例如，在 的情況下，從所有燈都亮到所有燈都關閉，對於全亮模式有四種可能的解，如上所示。

某些模式無解。例如，在上面顯示的 模式中，不可能關閉所有燈。

正如 Sutner (1989) 所證明的，對於任何尺寸的正方形格子，從所有燈都亮到所有燈都關閉總是可能的。上面的插圖顯示了 到 7 的所有可能解。對於 , 2, ...，解的數量（忽略旋轉和反射）為 1, 1, 1, 16, 4, 1, 1, 1, 256, 1, 64, 1, 1, 16, 1, ... (OEIS A075462)，並且要按下的按鈕的相應最小數量為 1, 4, 5, 4, 15, 28, 33, 40, 25, 44, 55, 72, 105, 56, 117, ... (OEIS A075464)。因此，具有唯一解的棋盤尺寸（將透過旋轉或反射具有等效解的棋盤視為不同的棋盤）為 1, 2, 3, 6, 7, 8, 10, 12, 13, 15, 18, 20, ... (OEIS A076436; Cowen and Kennedy 2000)。

移除透過旋轉或反射等價的解，給出了上面所示的不同解，其中有 1, 1, 1, 5, 1, 1, 1, 1, 43, 1, 10, 1, 1, 5, 1, ... (OEIS A075463)。因此，具有唯一解的棋盤尺寸（將透過旋轉或反射具有等效解的棋盤視為等價的棋盤）為 1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 17, 18, ... (OEIS A076437)。