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

這個方法的第一步，是需要把這個數獨遊戲的問題作出改變，將他變成一個我們有其他方法解決的數學問題。這種解決問題的辦法在數學界非常常見。如何把一個問題重新寫成另一個我們可以解決的問題，這需要數學家對問題掌握的能力和他對不同數學範疇的理解。

為了簡化之後的討論，我們先從一個比較簡單的數獨遊戲着手。我們考慮一個4×4 數獨遊戲，英文叫做Shidoku。遊戲原理跟9×9的一樣。只是我們要填進去方陣的數字改變為一到四。遊戲條件裏面的九個宮就改變為四個宮，每個宮的定義也改變為一個2×2的小方塊。每一個方陣的數字我們會用x(i,j)表示，代表着由上面數起第i橫行，又左手面起第j直列的數值。這個數值是從一，二，三和四裏面挑選。這個表是發，我們只需要儲存起最多 16個小格的數字。當然並不是所有16格的數字我們都從一開始便知道，所以如果真的需要在電腦裏面儲存起這個數獨，我們可以用一個拉丁方陣的表示方式，只需要儲存i，j，和在這個位置相對型的的值。用左手面這個例子，我們只需有用一個8×3的方陣就可以代表這個遊戲。八，是由於我們有八個提示。三，是由於相對每一個提示，我們必須要儲存三個數字。

1,4,3

2,1,3

2,2,2

2,3,4

3,2,4

3,3,3

3,4,2

4,1,2

這個表示方式聽起來好像要儲存的數字比原來的更多，可是在原來9×9的數獨遊戲裏面，我們只需要用N×3的方陣就可以代表一個遊戲。如果遊戲給予的提示是少於27個，這個新的儲存方式所需要代表的數字就比原來的小。

我們也可以用標籤作為一個遊戲的表示方式。由於每一格的數字都必須是由一到四其中一個整數，除了把這個數值儲存起來，我們也可以想像在每一小格向上延伸多四個小格，標示着這個遊戲小格所代表的數字。數學上來說，我們假設x(i,j,k)是小格x(i,j)是否等於k的表示。如果x(i,j,k)=1，就是說x(i,j)=k。如果x(i,j,k)=0，就是說x(i,j)≠k。以上邊x(1,4)這方格為例。由於所給的提示說這方格儲存的數值為3，所以這個用標籤作為表示的方式，我們得到x(1,4,1)=0, x(1,4,2)=0, x(1,4,3)=1, x(1,4,4)=0。又以x(2,2) 這方格為例。由於所給的提示說這方格儲存的數值為2，所以這個用標籤作為表示的方式，我們得到x(2,2,1)=0, x(2,2,2)=1, x(2,2,3)=0, x(2,2,4)=0。如此類推，上面這個遊戲給予的8個提示，就會化成32個可能是零也可能是一的數值。

每一小格只會有一個數目字

讀者可能已經發現，這個表示方式會有以下的一些特性。首先，由於每一小方格只會放着從一到四其中一個數目字，所以如果我們把每一小方格向上延伸的四個數值一起來看，就會發現四個數值裏面只會有其中一個的數值等於一，其餘三個都必須是等於零。由於一般來說，我們沒法知道數值是一的是那一個，所以一個折衷的辦法，是以一個數學方程式代表

x(i,j,1) + x(i,j,2) + x(i,j,3) + x(i,j,4) = 1。

由於i和j都是由一到四挑選的，所以我們一共就有16條線性方程式。

關於橫行的約束條件

這個表示方式另外一個好處，就是遊戲裏面的約束條件都可以簡單的表示出來。譬如說每一橫行，我們都必須要見到一到四裏面四個數目字。而每一個數目字出現的次數都必須是一次。以第一橫行來說，由於我們必須要看見一這個數字的出現，我們就可以限制

x(1,1,1) + x(1,2,1) + x(1,3,1) + x(1,4,1) = 1

這方程式左手邊四個項目，代表着x(1,1)，x(1,2)，x(1,3)和x(1,4)這是小方格裏面有其中一個存在着一這數字，另外三個都不代表着一。同樣道理，我們可以得到另外三條方程式

x(1,1,2) + x(1,2,2) + x(1,3,2) + x(1,4,2) = 1

x(1,1,3) + x(1,2,3) + x(1,3,3) + x(1,4,3) = 1

x(1,1,4) + x(1,2,4) + x(1,3,4) + x(1,4,4) = 1

代表着這一橫行裏面只會有一個二，一個三和一個四。由於一共有四條橫行，這一款約束條件，將可以幻化成16條線性方程式。

關於直列的約束條件

差不多的方法，我們也可以把另外的約束條件幻化成不同的線性方程式。每一直列，我們都必須要見到一度四裏面的四個數目字。以第一直列為例好我們就可以得到

x(1,1,1) + x(2,1,1) + x(3,1,1) + x(4,1,1) = 1

x(1,1,2) + x(2,1,2) + x(3,1,2) + x(4,1,2) = 1

x(1,1,3) + x(2,1,3) + x(3,1,3) + x(4,1,3) = 1

x(1,1,4) + x(2,1,4) + x(3,1,4) + x(4,1,4) = 1

已第一條方程式為例，代表着第一直列只會出現數字一一次，另外三個小方格都不會是數字一了。同樣道理，第二條方程式代表着數字二將會出現一次，另外三小方格都不會再是數字二。如此類推。由於另外有三直列，這個關於直列約束條件就會化成另外16條線性方程式。

相關於宮的約束條件

另外亦都有16條線性方程式是關於宮的約束條件。已左上方2×2的宮為例，由於我們要求這四小格裏面必須有一個數字一，我們可以得到

x(1,1,1) + x(2,1,1) + x(1,2,1) + x(2,2,1) = 1。

對於這個宮，我們可以有下面三條方程式

x(1,1,2) + x(2,1,2) + x(1,2,2) + x(2,2,2) = 1

x(1,1,3) + x(2,1,3) + x(1,2,3) + x(2,2,3) = 1

x(1,1,4) + x(2,1,4) + x(1,2,4) + x(2,2,4) = 1。

由於這個Shidoku一共有四個宮，我們有多收集了16條線性方程式。