想不開的老爸：到底是誰在念小學？

 兒子小四，老師出了一個數學作業：

一個4 x 4的方格，要把1到16的數字都填上去，已經知道4個角落的數字如上圖，分別為1,12,16,10。1到16的數字都必須填上去，不能少也不能多。而且填好的數字必須滿足各行相加後等於其行的加總值，還有各列相加後等於其列的加總值。可以看得出來，這題目的用意是要讓孩子們在遊戲之中，可以多多練習加法運算。老師用心良苦啊！

可那不爭氣的孩子，算了一個晚上都算不出來，來找老爸求救。

可憐，好不容易才脫離可怕小學生涯的老爸，只好硬著頭皮來算算看。

其實這題目不難，就只是將1到16的排列(permutation)都列示出來，每一種排列的可能都如圖般的排好後，再去計算是否符合各行列加總後是否等於各自行列加總值的條件，若符合即為答案，如此即可。

不過，聰明的我們都想找捷徑，例如我們看到第一列，就會想："已經知道2個數字了，而且該列加總值為31, 所以第一列剩下的2個數字加總必為31-12-1=18"。同樣的，第4列剩下的2個數字加總必為49-16-10=23。第一行剩下的2個數字加總必為43-1-16=26。第四行剩下的2個數字加總必為33-12-10=11。然後就很高興自己找到一個捷徑，第四行。因為其剩下的2個數字加總應為11。而且1和10已經用掉了，所以只剩下以下4種組合（8種排列）：

2 9

3 8

4 7

5 6

只要用這種方式，把第一行和第一列及第四列的可能組合也都列示出來，就可以大大簡化需要嘗試的次數。可是人類還是記憶容量太小的動物，要這麼多種可能的記錄和檢查，實在很容易出錯的。

學過程式的老爸實在懶得算，想想還是交給電腦算比較輕鬆。

不過太久沒寫程式了，都忘得差不多了。就找個不太需要安裝的python直譯器來寫就好了吧！那麼第一步是先產生所有的排列吧，google一下python產生排列的寫法，很好，網路上都有:

https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list

看到了，其實用python寫不難，人家程式庫都已經放在那等你拿去用，如上圖試了一下產生1到3的排列，果然很容易就做出來了。好，那試一下產生1到16的所有排列了。結果，記憶體不夠！哇哇！電腦都卡住了，少少的這幾行簡直就變成電腦炸彈，可以輕易的癱瘓任何一台電腦。那是需要多大的記憶體，才會這樣呢？

先算一下，1到16的排列的總數為16! ＝16 * 15 * 14 * 13 ... * 2 * 1

按一下計算機，16! ＝20,922,789,888,000

天啊！這是天文數字吧！20T，20萬億種可能。難怪記憶體不夠用，我就算再有錢，也不可能買到20TB的記憶體，就只為了解這個小小的數學習題。所以這個方案要修正一下，首先不能把全部的排列都存放在記憶體，這樣記憶空間會爆掉；接著，體認到排列數量龐大，所以要使用效率最高的工具，那就是古老的程式語言：C。

所以找一下怎麼用C來求排列：

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

太好了！很容易的樣子，這個範例會列示ABC三個英文字母的所有排列，就是有3!=6種排列。而且列印排列的程式行，就在if (l == r) printf("%s\n", a);這一行。

這樣，我只要在這一行檢查所有行列加總條件是否符合，若符合就找到答案。這樣做，不需要存儲所有排列，所以幾乎用不到什麼記憶體，只需要計算排列的算力而已。試著讓這支程式跑1到16的排列，並觀察其記憶體使用情況，果然幾乎沒用到記憶體。但讓我驚訝的是，程式跑了一個晚上，還沒跑完！

想想也是，就算電腦跑得再快，20萬億種可能都要一一比對，也是要跑很久的。所以要來做一下效能最佳化的工作了。想一下，其實已經有4個數字已知了，所以只要解12!=479,001,600種可能。哇哇！這樣馬上由20萬億變少成4億種可能。試了一下，果然程式可以在40秒左右就跑完了。

我把程式放在GitHub：

https://github.com/poushen/math_game1

首先看第一個版本：test3.c

程式裡都有寫註解了，如果題目有修改，就去改相應的地方就可以用在不同的題目。

比較要說明的是找到的C範例程式是使用A，B，C這樣的英文字母來玩排列，但我們需要的是1到16的數字來排序。其實也不用改什麼，因為電腦裡面英文字母其實本來就是數字編碼的，可以查一下ASCII這個編碼方法就知道。但是因為A的編碼為65, B的編碼為66, C的編碼為67,依此類推。而且C裡面有型別檢查，所以google一下，如何把字串轉成byte array, 就會看到test3.c裡面的string2ByteArray()這個function, 我將之稍加修改(- 64), 這樣就符合我們的需要了。

另外，題目本身是2維空間，但為了簡單起見，用找到的範例程式來排列，只用到1維空間的陣列。所以，在我們的腦袋裡，必須將題目的2維空間對應到實際上電腦裡的1維空間。如下圖般的，題目的16個格子，在電腦裡被編排了索引數字：

這樣一來，我們只要告訴電腦："請檢查A[0]+A[1]+A[2]+A[3]是否等於31"，這樣就可以檢查第一列的列加總條件是否符合。同樣的方法，可以檢查第二列，第三列，第四列，只要改變索引數碼即可。對了，那行加總條件的檢查也是一樣的。"A[0]+A[4]+A[8]+A[12]是否等於43"，這樣就完成第一行的檢查。其他幾行，就自己類推一下。

不過，我們為了效能最佳化，把4個角的已知數字(1, 12, 16, 10)都先排除掉了。所以這個方格的對應會變成：

所以第一列的列加總檢查會變成："A[0]+A[1]=31-1-12=18"這樣的型式，而第二列的列加總檢查會是"A[2]+A[3]+A[4]+A[5]=27", 其他依此類推，只是索引數字依上圖來改變而已。對應的程式如下：

最後要再說明的是，我們前面說用A來代表數字1, B代表數字2，那因為我們把4個角落的已知數字排除，所以程式一開始的字串就要把這4個對應的字母也拿掉。

這就是為什麼char str[] = "BCDEFGHIKMNO";這一行看起來這麼奇怪的原因。但也不難理解，就像這個題目已知數字(1, 12, 16, 10)對應到的字母是A, L, P, J。將其從A, B, C, . . . , P的字母中排除後，就變成了"BCDEFGHIKMNO"。

ok! 程式主要的核心就這樣而已，其他為了讓使用者在程式執行時，可以了解到比對的進度，我也加入簡單的進度顯示，還有答案的顯示方式也改成讓人類容易理解的原始題目樣式。來看一下程式執行的樣子吧：

這就是編譯程式的方法，和執行的方法，以及執行中看到的進度顯示。

下面則是執行結束的樣子：

可以看到列印出了答案，以這一題來說是有4種可能結果。

最後程式也把所花費的時間36.63秒，和找到的答案數都顯示出來。

好了，這樣就做完了，不是嗎？原本跑一個晚上的，現在只要半分鐘不到，這已經很棒了，不是嗎？

是沒錯！可是這個老爸真的想不開！

看到系統監視器顯示，只有一個CPU核心在跑，其他幾個都在閒置，而且就這個題目來說，答案總在75%之後才會出現。如下圖, 簡言之, 就是沒有全力在運算。因為我們寫的程式, 本來就是單緒的, 無法運用到全部核心的運算能力。

這就讓老爸心想，是不是把多工的寫法拿來試試！結果就是test5.c這支程式了：

編譯方法，執行方法，和執行結果如上兩圖，可以看到整個執行時間已經大大減少至10.18秒。而且答案其實在5秒左右就跑出來了。多工的用法在這裡其實很適用，因為排列是不會重複的，第一個格子的可能性有12種，正好用來分給12個小朋友(CPU核心)去賞試！

觀察工作管理, 可以看到如下的CPU使用率, 全部的CPU都被分配工作, 不會如之前只有一個核心在工作, 其他核心閒置。

只是多工的程式寫法比較容易出現一些不容易除錯的小問題，所以才會有test4.c和test5.c這兩支程式，其實都是一樣的功能，只是寫法不同。主要的問題出在，使用多緒pthread來寫時，產生每個緒時，都要傳參數給緒，這個過程很容易出錯。關鍵在於，我們程式其實很快的產生緒，要傳送的參數如果在這個過程中也會改變，那麼傳送過去到緒取得時，可能會拿到錯誤的值。所以多工版本的程式，我會在緒開始時先列印出取得的參數值內容，以確保程式正確。因此，要傳送的參數，最好不要在此過程中變動，方法很簡單，就是準備不會變動的值：

像這裡的參數是一個字串(void*)str[i]，我們就先用字串陣列將其準備好，而且不再變動之。就能保證傳過去的參數正確。如果你傳的是這個迴圈的變數i，那麼保證很容易出錯。

另外傳給緒的參數，以這個例子來說，是str_a字串，似乎不能直接在緒裡拿來運算！我花了快一天在找這個問題，最後是把傳過來的字串參數，利用字串複製的方法strcpy()，複製到緒的區域變數char str[]去，才解了這個問題！

好了，就這樣！哦對了，這幾支程式我試過可以在Linux，Mac OS X，也可以在Windows裡的Linux subsystem裡執行，都不用修改任何一行程式哦。所以C語言真的是跨平台的呢！

後記: 後來想到一個更好的算法: 利用解數獨的方法來解小四數學題