H5數獨游戲開發-按鈕控件的實現

　游戲中的按鈕不難實現，但是如何實現按鈕點擊后的狀態改變效果呢？例如：點擊游戲中的一個按鈕后，按鈕凹陷下去，隔了簡短的時間間隔后，按鈕又彈起來，恢復原來的狀態。這節課我們來實現按鈕的這種效果，我們在游戲資源加載完畢后，資源進度條顯示100%后，在資源進度條下面顯示一個按鈕，點擊這個按鈕后，進入游戲，顯示游戲主面板。效果如下圖所示

　　我們來看看游戲代碼需要做哪些調整，由于資源加載完畢后并不自動切換到游戲主面板，也就是說資源加載完畢后需要顯示資源加載進度條，所以，游戲的狀態變量值需要變更，修改如下

　　既然游戲狀態變量值更改了，那么，很自然，依賴此值繪制游戲場景的代碼也需要做相應的調整，修改后的代碼如下：

　　上節課將消息處理代碼handleMessage()放在了drawScene()函數里，嚴格意義上來說，每一個函數的功能是單一的，所以，這節課將消息處理代碼放在html頁面里的runGame()函數中，代碼如下：

　　接著就是今天的主角，游戲按鈕類，先看看它的定義

　　其中成員變量bDone表示按鈕狀態是否變更完成；成員變量nState表示按鈕當前的狀態；成員變量dbClickTime保存按鈕按下的時間，將當前時間與此成員變量比較，如超過某一固定時間間隔值，則修改按鈕的狀態；成員變量fCB保存按鈕的回調函數，即點擊按鈕后將執行此函數，將按鈕要實現的功能放在此回調函數中。下面是對相應成員變量操作的函數

　　我們接著看看初始化按鈕參數的函數代碼

　　由于點擊資源加載進度條下面的按鈕后，游戲場景會切換到游戲主面板，所以需要給按鈕的回調函數增加相應代碼來實現此功能，我將回調函數的代碼寫在了g_aControlPara參數初始化數組里，代碼如下

　　此外，我對消息的處理方式進行了調整，如果一條消息已經處理了，那么后續控件將不會再對此消息進行處理，代碼如下

　　接下來，是三個關鍵的成員函數，由于我們修改了參數初始化數組變量，所以控件的初始化成員函數需要修改

　　因為控件狀態變更涉及多個圖片，所以需要判斷o.name是否是數組對象（保存多個狀態使用的圖片名稱），是的話依次初始化每個圖片對象；然后，控件的繪制成員函數需要修改

　　需要根據控件當前狀態使用相應的圖片繪制控件，同時需要變更控件狀態并判斷狀態變更是否完成；最后，控件的消息處理成員函數需要修改，代碼如下

　　由于涉及控件狀態變更，所以需要判斷狀態變更是否未開始，是的話將狀態變更設為開始，同時保存狀態變更開始的時間，接著判斷狀態變更是否完成，是的話將調用控件的回調函數，即實現控件點擊后的功能，同時將消息標記為已處理，防止重復處理。最后，將今天的內容錄了一個視頻，文章未提到的地方可以參看視頻。

H5數獨游戲開發——按鈕控件的實現

　　未完待續，敬請關注！后續更精彩，謝謝大家！

言

數獨（及其前身）已經出現了一百多年。當它第一次出現時，人們實際上只能咬著筆抓著頭發來解決數獨題目。但現在我們有了強大的電腦！（現在的人就能在手機和電腦上做數獨題啦！）

在這篇文章中，你會學到如何搖身一變，成為一名數獨大師，在幾秒鐘時間內就能解出一般人要花幾小時才能解出的難題。當然，更重要的是，你會一步步的學習如何使用機器學習（Machine Learning）輕松解決每個數獨。設想一下，如果有計算機來做數獨，誰還需要思考呢，當然，多做數獨還是真的可以健腦的。（我沒有開掛做數獨啊，不要抓我）

我沒有開掛

Peter Norvig最先使用Python開發了一個優雅的程序，通過約束網格傳播和搜索以此來解出數獨。Norvig的解決方案被認為是目前十分經典的一個解決數獨的方案，當人們通過編程來解數獨時經常被引用。在回顧數獨和一些策略之后，本文將逐步分解Norvig的代碼，以便你能真正了解它的工作方式。

什么是數獨？

數獨是源自于18世紀瑞士的一種數學游戲。是一種傳統的運用紙、筆進行演算的邏輯游戲。人們需要根據9×9的盤面上的已知數字，一一推理出所有剩余空格的數字，并滿足每一行、每一列、每一個九宮格（3*3）內的數字均含1-9，不重復

數獨

如圖，突出顯示在藍色正方形中的數字不能在與同列同行和宮相對應的任何黃色正方形中重復

如何解數獨？

其實一般做數獨題的時候，只需要不斷做兩件事就OK了。要做的第一件事是就是排除行，列和宮中的已知數字。您要做的第二件事就是尋找一個可能填寫的候選數。

在下面給出的示例中，每個正方形中的可能填寫的數字以較小的字體標注。通過排除出現在同一列，行或宮中的已經重復的數字來確定剩下可能的數字。大多數人僅僅只會一次確定一個宮的可能數量，而不是直接確定整個網格中所有能填寫的數字（暗數、候選數）。

所有可能填寫的數字

進行排除操作后，你可以尋找僅剩余一種情況的格子。在下面的示例中，兩個黃色突出顯示的正方形必須包含1和8，因為其他所有的可能性已被排除，它們填在別的格子中會出現重復。

黃色的格子中只能填一種情況

現在已知以黃色突出顯示的兩個格子，這又排除了其他格子的更多可能性。現在我們可以知道以藍色突出顯示的格子必須填7。

更多的可能性被排除了

如果你繼續不斷的按照此法進行排除和確定，最終可能會達到能夠完全確定某個3*3的格子或行或列的情況。

一個九宮格被完全約束了

在下面的示例中，我們可以確定以藍色突出顯示的格子的解必須為6，因為數字6不可能出現在黃色宮中的其他任何的格子中。

繼續確定格子中的數字

有時，我們在求解的時候可能會遇到這種情況，似乎每個未解決的3*3的格子中有多個可能的值。這意味著我們可以選擇多種路徑，但至于哪條路才能最終得到結果就不知道了。

在這個選擇上，我們必須嘗試每個選項。選擇一條路并繼續求解，直到按這條路走下去最后只能得到“此路不通”的答案。然后，將不得不回溯到分歧點并嘗試其它的路。

但是我們可以使用二叉搜索樹在計算機上輕松完成此類檢索。當有兩個不同的數字都可以作為一個3*3的格子的答案時，我們可以嘗試引入兩種不同的可能性。二叉搜索樹將使算法沿選擇的一個分支下降，然后嘗試不同的選擇。

二叉搜索樹

現在，我們將了解用上述方法相似的思路來編寫的Python代碼，以此用來處理數獨問題。

Peter Norvig的解數獨代碼

Peter Norvig在他的解決數獨難題的文章中解釋了做數獨題的方法與他所使用的代碼。

www.norvig.com/sudoku.html

有些人可能理解他的解釋有些困難，尤其是初學者。本文將分解這些內容，以便讓你更輕松地了解Peter Norvig的代碼是如何工作的。

在本文中，Peter Norvig的代碼已經更新為Python3，以方便的在目前的環境下運行

首先，我們將介紹基本的設置和表示法。Norvig描述了他在代碼中所使用的基本符號：

數獨拼圖是一個由81個方格組成網格；廣大愛好者把列1-9、行a-i記為行列標記，把9個方格（列、行或宮）的集合稱為一個單位，把共享一個單位的方格稱為對等方

這是數獨中每個格子的名稱：

格子的名稱

Norvig將數字，行和列定義為字符串：

digits='123456789'
rows='ABCDEFGHI'
cols=digits

你可能會注意到將cols其設置為與digits相等。盡管它們具有相同的值，但它們表示不同的事物。該digits變量表示走在數獨上解決這一難題的數字。而cols變量代表網格的列名。

整個數獨盤也被定義為字符串，但是這些字符串是通過以下函數創建的：

def cross(A, B):
 "a中元素與b中元素的叉積。"
 return [a+b for a in A for b in B]
squares=cross(rows, cols)

cross函數（[a+b for a in A for b in B]）的返回部分只是編寫這個代碼的一種優秀解決方案：

squares=[]
for a in rows:
 for b in cols:
 squares.append(a+b)

運行此函數后，變量等于所有小方格名稱的列表。

['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9', 'B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9', 'C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', 'D1', 'D2', 'D3', 'D4', 'D5', 'D6', 'D7', 'D8', 'D9', 'E1', 'E2', 'E3', 'E4', 'E5', 'E6', 'E7', 'E8', 'E9', 'F1', 'F2', 'F3', 'F4', 'F5', 'F6', 'F7', 'F8', 'F9', 'G1', 'G2', 'G3', 'G4', 'G5', 'G6', 'G7', 'G8', 'G9', 'H1', 'H2', 'H3', 'H4', 'H5', 'H6', 'H7', 'H8', 'H9', 'I1', 'I2', 'I3', 'I4', 'I5', 'I6', 'I7', 'I8', 'I9']

而網格中的每個小格子都有3個單位和20個對等方。小格子的單位是顯示在其中的行，列和九宮格。小格子的對等方是單位中的所有其他小格子。例如，以下是小格子C2中的單位和對等方：

單位與對等方

使用cross函數創建每個小格子的所有單位：

unitlist=([cross(rows, c) for c in cols] +
 [cross(r, cols) for r in rows] +
 [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])

在Python中，字典是鍵值對的集合。使用以下代碼行創建字典，字典使用小格子的名稱作為鍵，并使用三個單位或20個對等體作為值。

units=dict((s, [u for u in unitlist if s in u]) 
 for s in squares)
peers=dict((s, set(sum(units[s],[]))-set([s]))
 for s in squares)

現在，可以使用來訪問“ C2”的所有3個單位，units['C2']并將得到以下結果：

測試結果

接下來，我們需要完整的數獨網格的兩種表示形式。名為grid的文本將是數獨的初始狀態。

還需要網格的另一種表示形式來描述數獨解題的當前狀態。它將跟蹤每個格子的所有剩余可能值并命名為values。

與units和peers類似，values將是一個以小格子為鍵的字典。每個鍵的值將是一串數字，該串數字是該小格子內的所有可能數字。如果數字是在拼圖中給出的或已被找出，則vaules中將只有一位數字。例如，如果存在一個網格，其中A1為6而A2為空，則values的值可能是這樣{'A1': '6', 'A2': '123456789', ...}。

解析網格和網格值函數

該parse_grid函數（下面的代碼）可將網格轉換為可能值的字典。grid是給定的數獨題目。grid_values函數用來提取數字，0和“.”的重要值。在values字典中，正方形是鍵，而網格中的給定數字是值。

對于具有給定值的每個格，assign函數用于將值分配給方框并從對等方排除該值。assign函數將在下文介紹。如果發生任何錯誤，該函數將返回False。

這是parse_grid與grid_values函數的代碼。

def parse_grid(grid):
 """將網格轉換為可能值的dict，{square:digits}，如果檢測到錯誤，則返回false"""
 ## 首先，每個小格子可以是任意數字；然后從網格中賦值。
 values=dict((s, digits) for s in squares)
 for s,d in grid_values(grid).items():
 if d in digits and not assign(values, s, d):
 return False ## (如果我們不能把d賦給格子s，則失敗。)
 return values
def grid_values(grid):
 "將網格轉換為{square:char}的dict，并用'0'或'.'表示清空。"
 chars=[c for c in grid if c in digits or c in '0.']
 assert len(chars)==81
 return dict(zip(squares, chars))

約束傳播（Constraint propagation）

每個方格的初始值將是特定數字（1-9）或為空值。我們可以將約束應用于每個小格子并排除不可能的值。

Norvig使用以下兩種策略來幫助確定平方的正確值（與上述策略相對應）：

（1）如果一個方格只有一個可能的值，則從該正方形的對等方中排除該值。

（2）如果一個單位只有一個可能的位置放一個值，則將值放在那里。

第一種策略的示例是：如果我們知道A1的值為5，則可以從其所有20個對等方中刪除5個。

第二種策略的示例是：如果可以確定A1到A8都不包含9作為可能的值，那么我們可以確定A9的值為9，因為9必須出現在單位中的某個位置。

每次更新網格時，都會導致其所有對等方的可能更新。此過程將連續不斷的進行，稱為約束傳播。

分配功能

該assign(values, s, d)函數在parse_grid函數內部被調用。它返回更新的值。它接受三個參數：values，s和d。

請記住，values是一個字典，它將每個格子與該格子的所有可能的數字值相關聯。s是我們要為其分配值的格子，d是需要分配給該格子的值。D才是我們首先要解決的給定的難題。

它調用函數eliminate(values, s, d)以排除S中除D之外的所有值。

如果存在矛盾，例如兩個正方形被分配了相同的數字，則排除函數將返回False。

def assign(values, s, d):
 """從值[s]中排除所有其他值（d除外）并傳播。如果存在矛盾，則本函數將返回False。"""
 other_values=values[s].replace(d, '')
 if all(eliminate(values, s, d2) for d2 in other_values):
 return values
 else:
 return False

消除功能

我們看到assign函數調用了eliminate函數。消除函數的調用如下：eliminate(values, s, d2) for d2 in other_values)

eliminate函數將排除使用上述兩種策略無法解決的值。第一種策略是，當僅存在一個潛在值s時，該值將從s的對等方中刪除。第二種策略是，當值只能存在一個位置時，該值d將從所有對等方中刪除。

這是它的全部功能：

def eliminate(values, s, d):
 """從值[s]中刪除d；當值或位置<=2時傳播。如果存在矛盾，則本函數將返回False。"""
 if d not in values[s]:
 return values ## 已被排除
 values[s]=values[s].replace(d,'')
 ## （1）如果方格s減去一個值d2，則從對等點中消除d2。
 if len(values[s])==0:
 return False ## 矛盾：去掉最后一個值
 elif len(values[s])==1:
 d2=values[s]
 if not all(eliminate(values, s2, d2) for s2 in peers[s]):
 return False
 ##（2）如果一個單位u的值d減少到只剩一個地方，那么就不動它。
 for u in units[s]:
 dplaces=[s for s in u if d in values[s]]
 if len(dplaces)==0:
 return False ## 矛盾：沒有這個值的地方
 elif len(dplaces)==1:
 #d只能在一個單元中的其中一個位置；將它分配到那里
 if not assign(values, dplaces[0], d):
 return False
 return values

顯示功能

本display函數將在調用后顯示結果parse_grid。

def display(values):
 "將這些值顯示為二維網格。"
 width=1+max(len(values[s]) for s in squares)
 line='+'.join(['-'*(width*3)]*3)
 for r in rows:
 print(''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in cols))
 if r in 'CF': 
 print(line)
 print()

這是一個示例，它在解析一個網格之后調用顯示函數后，顯示的網格依然是個候選數的集合

示例

您會注意到，許多格具有多個候選數，而有些則完全解決了。上面的網格是上面兩種策略死記硬背應用的結果。但是正如你所看到的，僅憑這些策略還不足以完全解決數獨。

搜索（Search）

解決數獨問題的??方法有很多，但有些方法效率更高。Norvig建議使用一種特定類型的搜索算法。

搜索算法可以做這些事情。首先，它可以確保還沒有找到解決方案。然后，它選擇一個未填充的正方形，并考慮所有可能的值。最后，它一次一次嘗試為格子分配每個值，然后從結果位置再次進行搜索。

可變順序用于選擇要開始搜索的格子。這是Norvig的描述方式：

我們將使用一種稱為最小剩余值的通用啟發式方法，這意味著我們將選擇具有最小可能值數量的格子（或其中之一）。為什么？考慮上面的grid。假設我們首先選擇了B3。它有7種可能性（1256789），因此我們期望以6/7的概率猜測錯誤。如果取而代之，我們選擇G2，它只有2種可能性（89），那么我們期望錯的概率只有1/2。因此，我們選擇可能性最小，直接得到正確答案的期望也就越大。

這些數值按自然數順序排列。

這是本search函數以及solve解析初始網格并調用的函數search。

def solve(grid): return search(parse_grid(grid))
def search(values):
 "使用深度優先搜索和傳播，嘗試所有可能的值。"
 if values is False:
 return False ## 失敗了
 if all(len(values[s])==1 for s in squares): 
 return values ## 解出來辣!
 ## 選擇可能性最小的未填充正方形
 n,s=min((len(values[s]), s) for s in squares if len(values[s]) > 1)
 return some(search(assign(values.copy(), s, d)) 
 for d in values[s])

根據數獨的規則，當每個格子只有一個值時， 問題 就解決了。該search函數將遞歸調用，直到解決難題為止。它通過values復制以避免復雜。

some是用于檢查嘗試是否成功解決難題的函數。

def some(seq):
 "返回seq的某個元素，該元素為true。"
 for e in seq:
 if e: return e
 return False

完整代碼（在Python3.x下測試通過）

這些代碼組合起來將會讓你變成數獨大師，以下給出完整代碼。

def cross(A, B):
 "a中元素與b中元素的叉積。"
 return [a+b for a in A for b in B]
digits='123456789'
rows='ABCDEFGHI'
cols=digits
squares=cross(rows, cols)
unitlist=([cross(rows, c) for c in cols] +
 [cross(r, cols) for r in rows] +
 [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units=dict((s, [u for u in unitlist if s in u])
 for s in squares)
peers=dict((s, set(sum(units[s],[]))-set([s]))
 for s in squares)
def parse_grid(grid):
 """將網格轉換為可能值的dict，{square:digits}，如果檢測到錯誤，則返回false"""
 ## 首先，每個小格子可以是任意數字；然后從網格中賦值。
 values=dict((s, digits) for s in squares)
 for s,d in grid_values(grid).items():
 if d in digits and not assign(values, s, d):
 return False ## (如果我們不能把d賦給格子s，則失敗。)
 return values
def grid_values(grid):
 "將網格轉換為{square:char}的dict，并用'0'或'.'表示清空。"
 chars=[c for c in grid if c in digits or c in '0.']
 assert len(chars)==81
 return dict(zip(squares, chars))
def assign(values, s, d):
 """從值[s]中排除所有其他值（d除外）并傳播。如果存在矛盾，則本函數將返回False。"""
 other_values=values[s].replace(d, '')
 if all(eliminate(values, s, d2) for d2 in other_values):
 return values
 else:
 return False
def eliminate(values, s, d):
 """從值[s]中刪除d；當值或位置<=2時傳播。如果存在矛盾，則本函數將返回False。"""
 if d not in values[s]:
 return values ## ## 已被排除
 values[s]=values[s].replace(d,'')
## （1）如果方格s減去一個值d2，則從對等點中消除d2。
 if len(values[s])==0:
 return False ## 矛盾：去掉最后一個值
 elif len(values[s])==1:
 d2=values[s]
 if not all(eliminate(values, s2, d2) for s2 in peers[s]):
 return False
 ##（2）如果一個單位u的值d減少到只剩一個地方，那么就不動它。
 for u in units[s]:
 dplaces=[s for s in u if d in values[s]]
 if len(dplaces)==0:
 return False ## 矛盾：沒有這個值的地方
 elif len(dplaces)==1:
 #d只能在一個單元中的其中一個位置；將它分配到那里
 if not assign(values, dplaces[0], d):
 return False
 return values
def solve(grid): return search(parse_grid(grid))
def search(values):
 "使用深度優先搜索和傳播，嘗試所有可能的值。"
 if values is False:
 return False ## 已False
 if all(len(values[s])==1 for s in squares):
 return values ## 解出來拉!
 ## 以最少的可能性選擇未填充的正方形
 n,s=min((len(values[s]), s) for s in squares if len(values[s]) > 1)
 return some(search(assign(values.copy(), s, d))
 for d in values[s])
def display(values):
 "Display these values as a 2-D grid."
 width=1+max(len(values[s]) for s in squares)
 line='+'.join(['-'*(width*3)]*3)
 for r in rows:
 print(''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in cols))
 if r in 'CF':
 print(line)
 print()
def some(seq):
 "返回seq的某個元素，該元素為true。"
 for e in seq:
 if e: return e
 return False

調試

測試用Grid數獨題,同時它也是一個最小數獨（供讀者自己測試python時調試用）：

grid='4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'

測試結果如圖

苦逼作者碼字不易，各位看官老爺們給個關注吧！

尋找非周期性平鋪方案和相關瓷磚的過程，如同打碎一個花瓶然后再復原它。不過，研究者希望花瓶碎裂后形成的是均勻的碎片，且破碎的紋理是“非周期性的”。這樣的瓷磚即使鋪滿全世界，拼接圖案也不會重復。

能否尋找到一塊這樣的瓷磚，即使用它鋪滿全世界，其拼接圖案也永不重復？

近日，數學界的“莫扎特”、華裔數學家、菲爾茲獎得主、美國加州大學洛杉磯分校數學系教授陶哲軒（Terence Tao）在個人博客上宣布，推翻了“周期性平鋪猜想”。

他們在超高維空間中找到一塊這樣的“瓷磚”。

預印本網站arXiv顯示，陶哲軒與合作者合著的相關論文于2022年11月29日凌晨上傳。

但實際上，陶哲軒提前了兩個多月就在其博客上宣布了上述消息；并在9月18日凌晨，他們向arXiv網站提交了一篇縮略的“公告”論文——announcement，全文共13頁。

而完整版論文共48頁。論文標題是《周期性平鋪猜想的一個反例》（A counterexample to the periodic tiling conjecture）。

該論文的合著者是原美國加州大學洛杉磯分校數學系Hedrick助理教授、現美國普林斯頓高等研究院數學學院成員雷切爾·格林菲爾德（Rachel Greenfeld）。她是陶哲軒的博士后。

諾貝爾獎和永不重復的拼圖

什么是周期性平鋪猜想？

設想用相同大小的正方形瓷磚，去鋪滿一個方方正正房間的地面，這似乎難度不大。人們只要像“復制黏貼”一樣，不留空隙地將一塊塊大小合適的瓷磚平鋪下去就行。在這樣的地板上，圖案的周期性顯而易見：如果你將部分圖案平移到另一個位置，就跟沒有移動過一樣。

這或許是最容易的“施工方案”之一，被稱為周期性平鋪。

周期性平鋪和非周期性平鋪產生的不同效果。截圖來自《Aperiodic Texture Mapping》

六年前，2016年2月18日，來自印度孟買塔塔基礎研究所數學院的數學家悉達多·巴塔查里亞（Siddhartha Bhattacharya）在arXiv網站上傳預印本論文“Periodicity and decidability of tilings of ?^2”，宣布其在二維平面上證明了“周期平鋪猜想”——通過平移，單個瓷磚在平面上只能進行周期性平鋪，無法進行非周期性平鋪。

數學家們推測，在二維以上更高維度上，也不存在用同一種就實現非周期性平鋪的瓷磚。這一假設被稱為“周期性平鋪猜想”。

換句話說，“周期性平鋪猜想”斷言，如果只能以平移的方式平鋪或填充，那么在任意維度上（二維及以上），不存在一塊能以非周期性的方式鋪滿整個表面或填充整個空間的特殊瓷磚。即使設計出來這樣一塊瓷磚，那么它也只能以周期性的方式平鋪或填滿相應的空間。

但“周期性平鋪猜想”似乎只在二維平面上成立。

彭羅斯瓷磚樣式之一。截圖自Eureka 39(1978) 16-32

早在六十年前，1960年左右，在牛津大學任教的華裔數學家王浩在對美國新澤西州的貝爾電話實驗室進行學術訪問期間，研究了周期性平鋪問題，并提出“王磚”（或王氏磚、王浩瓷磚，aka Wang squares）模型。

部分王浩瓷磚。來自Parcly Taxel

四年后，一種似乎更高級的方案出現了：非周期性平鋪。它雖然也是很多塊瓷磚拼接在一起，密密麻麻地鋪滿整個地板，但其拼接的圖案永不重復，即使鋪滿整個世界也不重復。1964年，王浩的學生Robert Berger提出最早的非周期性平鋪方案，需要20426塊瓷磚組合。

用“王磚”進行的一種非周期性平鋪。來自Claudio Rocchini

隨后，英國數學物理學家、牛津大學數學系名譽教授羅杰·彭羅斯（Roger Penrose）把需要的瓷磚組合減少到5種，最后只用2種形狀的瓷磚組合，比如一大一小兩個菱形，就可以在二維平面上實現非周期性平鋪。這種瓷磚被稱為彭羅斯瓷磚。它成為數學藝術的象征之一，被鋪在牛津大學數學系等知名大學相關建筑物的地板上。相關平鋪樣式被稱為彭羅斯平鋪，或彭羅斯鑲嵌、彭羅斯密鋪、彭羅斯拼圖、彭羅斯幾何拼圖等。

平面上的非周期圖案具有一個奇特的性質，排布位置的信息似乎能夠通過某種方式跨過很大距離進行傳遞，防止數百（甚至數千、數百萬）塊之外的瓷磚出現某種排列類型。阿肯色大學助理教授埃蒙德·哈里斯（Edmund Harriss）的博士論文主題就是彭羅斯貼磚。他說：“局部約束鬼使神差地拓展為全局約束。”

而彭羅斯瓷磚不只在數學界很有名，在建筑裝潢領域甚至材料科學領域也成功圈粉，給人們帶來新的啟示。

彭羅斯瓷磚或拼圖的樣式之一。來自Taktaal

1982年，在美國正進行學術休假的以色列材料科學家丹·謝特曼（Dan Shechtman），在實驗室里觀察到合金的奇特衍射圖樣，不符合此前人們關于晶體的印象，缺乏標準的對稱。它們原子排列的樣子，跟彭羅斯地磚拼接的圖案一樣，是非重復、非周期性的。他后來稱之為“準晶體”（quasicrystal）。

丹·謝特曼拍攝到的電子衍射圖片。截圖自Phys. Rev. Lett. Vol. 53(20),1984

丹·謝特曼的論文和他的發現引起了極大的爭議和攻擊。直到20多年后，2011年，他因“發現準晶體”，被授予諾貝爾化學獎。

準晶體的電子衍射圖片。來自nobelprize.org

此外，彭羅斯也是諾貝爾獎得主之一。

1965年1月18日，彭羅斯在《物理評論快報》（Physical Review Letters）發表論文，闡述了彭羅斯奇點定理。斯蒂芬·霍金（Stephen Hawking）與彭羅斯一起研究奇點后，以彭羅斯定理顛覆了有關宇宙起源的理論。奇點后來被人們熟知，稱為“黑洞”。

2020年，89歲的彭羅斯被授予諾貝爾物理學獎，表彰他“發現黑洞的形成是對廣義相對論的有力預測”。他獨享一半獎金，與“在銀河系的中心發現了一個超大質量致密天體”的德國科學家賴因哈德·根策爾（Reinhard Genzel）和美國科學家安德烈婭·蓋茲（Andrea Ghez）分享了2020年的諾貝爾物理學獎。

但問題是，一直沒人用一塊瓷磚完成非周期平鋪“游戲”。直到最近，陶哲軒和合作者在超高維空間找到一塊這樣奇特的“瓷磚”。

用數獨、俄羅斯方塊游戲尋找一個反例

尋找非周期性平鋪方案和相關瓷磚的過程，如同打碎一個花瓶然后再復原它。不過，研究者希望花瓶碎裂后形成的是均勻的碎片，且破碎的紋理是“非周期性的”。

從在二維平面“拼圖”到更高維空間里“堆積木”，陶哲軒希望找到一塊能夠實現非周期性地堆疊的單一“瓷磚”。

立方形密鋪。來自Tomruen

在解釋其最新證明策略和方法的博客文章中，陶哲軒提到數獨和俄羅斯方塊游戲，還有電腦編程。

在印度數學家悉達多·巴塔查里亞證明“周期平鋪猜想”在二維平面上成立三年后，2019年，格林菲爾德以博士后身份來到加州大學洛杉磯分校。隨后，她和陶哲軒用不同于悉達多·巴塔查里亞的另一種方法，再次證明了二維平面中的“周期平鋪猜想”。但是，當他們想推進到在三維空間中也證明這一猜想時，碰壁了。

陶哲軒說，無法在更高維度上證明這個猜想成立也許是有原因的，應該開始尋找反例。

2021年8月，他們第一次接近目標：他們在超高維空間找到了兩塊可以實現非周期性填充的瓷磚，但不是一塊。

2021年8月17日，格林菲爾德在arXiv網站上傳她和陶哲軒共同署名的論文，標題是“Undecidable translational tilings with only two tiles, or one nonabelian tile”。六天后，她上傳了更新版。

“2非常接近了，但還不夠。” 格林菲爾德說。

像“俄羅斯方塊游戲”一樣消行。截圖自陶哲軒2022年9月19日的博客文章

2022年9月19日，陶哲軒在其博客文章中表示，“格林菲爾德和我剛剛將我們的公告——‘周期性平鋪猜想的反例’上傳到 arXiv。這是我們目前正在撰寫（并希望在幾周內發布）的一篇更長的論文的公告。其中，我們推翻了 Grünbaum-Shephard 和 Lagarias-Wang 的周期性平鋪猜想。”

在上述博客文章中，陶哲軒寫道，他們創建了一種“平鋪語言”（“tiling language”），使用平鋪方程組來描述非周期函數。“這個證明，讓人強烈地聯想到解決數獨謎題所需的推理類型，因此，我們在論點中采用了一些類似數獨的術語來提供直覺和視覺效果。一個關鍵步驟是，對拼圖進行剪切變換……然后執行消除常量行的‘俄羅斯方塊’移動以得出次級數獨謎題，然后依次分析該謎題。正是這個過程的迭代最終生成了非周期性p-adic結構。”

在其兩個月后、11月29日的博客文章中，陶哲軒寫道：“格林菲爾德和我剛剛將論文上傳到 arXiv。這是我幾個月前在這個博客上公布的結果的完整版本……這篇論文完成的時間比預期的要長一些，這是由于我們在發布公告時沒有意識到的一個技術問題需要個解決方法。”

陶哲軒進一步解釋說，如公告中所述，最初的策略是構建一種“平鋪語言”——一種能夠用來編碼“P進數數獨謎題”（P-adic Sudoku puzzle）的語言；然后證明如果P是一個足夠大的素數，那么后一種類型的謎題只有非周期性的解決方案。“事實證明，該策略的后半部分成功了。”“在編程過程中，我們還發現，一旦引入‘可表達屬性’和‘弱表達屬性’兩個新定義，證明的編碼部分將變得更加模塊化和概念化。”

陶哲軒和格林菲爾德將他們的方程式系統看作一個計算機程序：每一行代碼或方程式都是一個命令，這些命令組合起來可以生成一個實現特定目標的程序。

最終，他們在一個非常高維度的空間中，尚未被詳細計算，但大約2^100^100維里，找到一塊目標“瓷磚”——一塊非常復雜、彎彎曲曲、充滿孔洞的“瓷磚”。

此外，陶哲軒表示，使用他們最新創造的“語言”應該能創造一個無法判定的謎題。“（比如）可能存在一些瓷磚，我們永遠也無法證明，它是否能鋪滿它所在的空間。”

既無法證明也無法反駁，數學中充滿了這樣的“不可判定”（undecidable）的陳述。為了證明一個陳述是不可判定的，數學家通常證明它等價于另一個已知不可判定的問題。所以，如果平鋪問題被證明是不可判定的，它將可以作為新工具，證明更多其他問題的不可判定性。

格林菲爾德的簡歷顯示，其研究課題“平移平鋪和正交系統指數”（translational tiling and orthogonal systems exponentials）獲得了美國國家科學基金會（NSF）11.7056萬的資助，編號是DMS-2242871，資助期限是2022年到2025年。

參考資料：

1.https://www.quantamagazine.org/nasty-geometry-breaks-decades-old-tiling-conjecture-20221215/#newsletter

2.https://nautil.us/impossible-cookware-and-other-triumphs-of-the-penrose-tile-rp-234895/?_sp=1048d065-5002-434f-85c5-fa868cbccae2.1671370700212

3.https://huanqiukexue.com/a/qianyan/cailiao__huaxue/2017/0527/27301.html

4.https://terrytao.wordpress.com/2022/09/19/a-counterexample-to-the-periodic-tiling-conjecture/

5.https://arxiv.org/abs/1602.05738

在線咨詢

上一篇：require.js 禁用緩存
下一篇：HTML5 拖放

您的項目需求

*請認真填寫需求信息，我們會在24小時內與您取得聯系。

整合營銷服務商