哈佛大學數學家解決了150年前的國際象棋問題
哈佛大學的數學家在很大程度上解決了有150年曆史的國際象棋問題,涉及到棋盤上最強大的棋子。皇后是國際象棋棋盤上最強大的棋子。與其他任何棋子(包括國王)不同,它可以在垂直、水平或對角線上移動任何數量的位置。
現在考慮一下這個皇后的賭法。如果你把八個皇后放在一個八格乘八格的標準棋盤上,它們可以有多少種排列方式,使它們都無法攻擊對方?結果是有92種。但是,如果你在一個相對大小相同的棋盤上放置更多數量的王后,例如在一個1000乘1000平方的棋盤上放置1000個王后,甚至在一個類似大小的棋盤上放置100萬個王后呢?
n-queens數學問題的最初版本於1848年作為8-queens問題首次出現在一份德國國際象棋雜誌上,幾年後出現了正確答案。然後在1869年,這個問題的更廣泛的版本浮出水面,直到去年年底,哈佛大學的一位數學家提供了一個幾乎確定的答案。數學科學與應用中心的博士後邁克爾-西姆金計算出有大約(0.143n)n種方法可以放置皇后,使其在巨大的n乘n的棋盤上不互相攻擊。
西姆金的最終方程並沒有提供準確的答案,而是簡單地說,這個數字是你現在能得到的最接近實際的數字。0.143這個數字代表了變量可能結果的平均不確定性水平,它被乘以任何n,然後提高到n的冪,得到答案。例如,在有一百萬個皇后的極大型棋盤上,0.143將被乘以一百萬,得出約143000。然後這個數字會被提升到100萬的冪,也就是說它被自己乘以100萬次。最後的答案是一個有500萬位數的數字。
通過關注那些更有可能被佔領的空間,西姆金算出了在棋盤的每個部分會有多少個皇后,並想出了一個公式來獲得有效的配置數量。計算的結果就是所謂的下限,可能配置的最小數量。一旦有了這個數字,辛金就用一種被稱為熵法的策略來尋找上限,也就是可能配置的最高數量。辛金發現,下限答案幾乎與上限答案完全吻合。簡單地說,它表明確切的答案是夾在兩個界限之間的某個相對較小的數學空間裡。