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

總括來說，我們到現在為止一共收集了64條方程式，裏面一共有64個不同的變數。看起來好像方程式的總數跟要解決的變數數目是一樣，我們可能馬上就會猜想可以從這個64元一次方程組裏面找到解決這個Shidoku的答案。我是這裏有個問題， 64條方程式裏面其實並不包括任何有關遊戲開始時所給予的任何提示。所以我們根本不可能從這64條方程式裏面找出一個解。我們要解決的線性代數問題，其實是必須要從這64條方程式裏面再加上開始時提到的提示，所以假設遊戲開始時有\(N_c\)個提示，我們要解決的方程組就會有\(64+N_c\)條方程式。

這一段的討論，可能需要有一點數學的背景。如果同學有修讀過本科生的線性代數，另外一個數學問題，就是左手邊的矩陣並不是Full Rank的。如果我們並沒有任何提示（是說 \(N_c=0\) ），左手邊這個64×64的矩陣，Rank只得40。所以這代表着，如果這個代數問題需要找到唯一的解，我們就必須起碼多加上24條linearly independent的橫行。這樣，我們才可以找得到一個Full Rank的問題然後得到一個唯一的解。根據同樣的演示方式，一個9×9的數學問題，我們可以把它還化成一個 \(324+N_c \)的方程組，而每一條方程式都會有729個未知數。不理會遊戲開始時所給予的提示，那一個324×729的矩陣，Rank只會有249。也就是說，我們必須要多追加起碼729-249=480條linearly independent的橫行，我們才可以找得到一個Full Rank的問題然後得到一個唯一的解。

當然，在Shidoku這個遊戲裏面，一共只有16小方格，所以根本沒有可能多加24條方程組給那個線性代數問題。在Sudoku裏面，要有另外480條提示也非常之不合常理。所以在這個討論裏面，有什麼問題呢？

最主要的問題，是在本科生的線性代數討論裏面，我們容許答案存在於高維空間裏面的任何數值。要記得，我們這個演示方式只容許每一個未知數不是等於0就是等於1。所以，我們其實只容許答案存在於一個很小的空間裏面。雖然說很少，這些非0即1的答案，卻會有\( C_{16}^{64}=4.8853\times{10}^{14} \)（Shidoku）或者 \(C_{81}^{729}=1.2950\times{10}^{109} \)（Sudoku）個。由於可能的答案數目相當龐大，要從這麼多可能的數值解裏面找出一個答案，非常不容易。所以我們必須要多施展幾次魔法，運用一些更加好的數學方法解決這個問題。

第一個將問題簡化的方法，是去找一些特別的解。在這麼多答案裏面我們只希望見到有16個（Shidoku）或者81個（Sudoku）數值不等於零的答案。這裏我們需要小心一點，我們找到一個這樣子的答案，並不等於說「不等於零」就會得出「等於1」。但是如果我們只找得出一個這樣子的答案，又或者只有很少量這樣子的答案，我們就可以有很簡單的去判斷這個數獨遊戲的答案。這些答案在數學裏面我們叫做16-Sparse或者81-Sparse的答案。Sparse代表着疏落，N-Sparse是指在整個解x裏面所有的未知數內，只有N個不是等於零的數字。也就是說，假設x是一支在d維上的向量，我們有\( |x|_0=N\) 。一般來說這個0-norm並不可以用來定義長度或距離，這裏我們定義他為看看有多少個不等於零的元素。所以，要解決這個4×4數獨問題就等同於要解決下面這一個線性代數問題

\[ Ax=b\mathrm{\ such\ that\ }\|x\|_0=16. \]

第二個步驟，是放棄限制着有多少不等於零的項目，而希望找出一些有「非常少」不等於零項目的答案。數學上來說，就是要解決下面的優化問題，

\[ min_x \|x\|_1\mathrm{\ such\ that\ }Ax=b. \]

這個優化問題跟上面那一個線性代數問題，在這個應用裏面可以證明答案是相等的[1]。我在這裏就不再多加討論。雖然優化問題有很多看起來可以解決的方法，可是對於0-norm的優化問題，很多時候可以證明要找出一個答案並不容易。在計算機科學裏面，這些問題都可以歸類為NP-Hard。

重要的是下面這一個步驟。第二個將問題簡單化的方法，是去用1-norm代替0-norm。數學上來說，就是要解決下面的優化問題

\[ min_x \|x\|_1\mathrm{\ such\ that\ }Ax=b \]

而\( |x|_1=\left|x_1\right|+\left|x_2\right|+\cdots+\left|x_d\right| \)。這個優化問題，就可以變得非常簡單。有很多計算上有效率的數值方法可以很快速的把這個答案找出來。當然，一般來說這兩個問題的答案是不會一樣的。可是，如果矩陣A有某一些特別的特性，我們就有很大的信心兩個問題會給我們相同的答案。至於「特別的特性」和「很大的信心」是什麼意思，就不是這篇普及數學文章可以探討的。有興趣的讀者，可以看一下陶哲軒在Compressed Sensing方面的文章[2]。