科普系列 - 數學與數獨（一）

除了電影和圖像處理這些比較可以直接用肉眼看見的數學應用外，還有一些無論是在媒體上，還是從不同用家口中，都經常提到的一些可以聲稱段練數學思維的遊戲。在這一篇文章裏面，希望可以「從遊戲中學習」，透過討論一些遊戲裏面可能會用到的數學，介紹一下一些比較抽象的數學工具如何可以應用在日常生活裏面。

遊戲也可以用來吸引大眾對數學的興趣。其中一些遊戲，包括了題目所提到的「數獨」（Sudoku）[1]。相信大家也有玩過這個遊戲。遊戲開始時，將會在一個九格乘九格的Excel數表內給予一些從一至九選定的數字。這一共81個小方格，遊戲會用三種不同的方法將他們聯繫起來。第一款是橫行（Row），第二款是直列（Column）。所以每一個數獨遊戲，一共會有九個橫行，以及九個直列。第三款是一些三格乘三格的宮（Cell）。遊戲考慮的一共有九個宮，包括最左上角的3×3小方格，最想三行中間的3×3小方格，最右上角的3×3小方格，然後是中間三橫行會分成三個宮，最後是下面三行亦都會分成三個宮。遊戲的目的，遊戲玩家必須要把剩餘的空格填滿，令到每橫行，每一直列，和每一個三格乘三格的宮，都有一至九這九個數目字。由於每橫行，每一直列，和每一個三格乘三格的宮，一共有九個小方格，所以我們填進裏面的九個數目字都不會重複。

遊戲剛出現時，經常會聽到不同報道都說這遊戲可以訓練玩家的邏輯思維，數學能力等等。說起來好像很厲害似的。可是想來想去，也想不出到底數學的訓練在哪裏。簡單的來說，對訓練玩家的推理能力應該也有一定的關係，可是從數學的角度上來看，可以有什麼更加直接的關連呢？如果從一個數學研究的角度來看，應該可以做出一些什麼樣的數學結果呢？

這遊戲的出處好像已不可考[2]，但在數學歷史裏面，有一個相關的數學問題叫做拉丁方陣（Latin Squares）[3] 由非常出名的數學家歐拉（Euler）[4] 所討論過。拉丁方陣的設計，比數獨遊戲「簡單」了一點。給予一個N×N的方陣，拉丁方陣的數字並不需要遵從與「宮」相關的那個限制，而只要每一橫行以及每一直列都填進了一至N的數字令到他們不會重複。由於數獨比拉丁方陣多了一個需要滿足的條件，所以所有數獨的答案，都是一個拉丁方陣。由於數獨遊戲多了一個條件，而且玩法亦不單單只是把整個拉丁方陣列出來，而是從一些已經給定了的條件裏面找出一個滿足遊戲三個條件的答案。這遠比確定了N，然後找出所有拉丁方陣的問題更為有趣。有興趣的讀者可以在網上找到很多關於這問題的研究和應用，在這裏我就不再仔細討論了。

關於數獨遊戲裏面數學的研究有很多，比如說一個數獨遊戲可以有多少個不同的變化？這個問題的答案，需要有一點計算的能力，仔細想一下也可以找出來。這篇文章想討論的，是如何可以教導電腦把答案找出來的方法。當然一個直接的方法就是從所有可能性裏面，找出一個跟遊戲開始時給的提示相所符合的。可是由於答案的可能性相當之多，這個直接的方法在現實生活上並不可能。可以想像一下，我們如果需要從 \(10^{21}\) 那麼多個可能性裏面找出一個答案[5]，假設一個可能性只需要一次運算，而一個普通電腦每1秒可以做大約\({10}^9\)次運算，我們就需要 \({10}^{12}\) 秒鐘，就差不多等於3萬年！這個例子就顯示了，我們必須要想一些聰明的辦法去把答案找出來，而不是用一些看起來簡單，可是窮我們一生也找不到答案的方法。

下面所討論的是一個比較有趣的方法，而且裏面所討論的數學成份也相當多。