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

 好! 這個數學老師又出了一道難題, 兒子又來求救了.

想不開的老爸又來挑戰, 題目:

這次容易一點, 3 x 3, 也就是數字必須是由1到9填入格子, 同樣要滿足各行各列加總等於其各自的行或列加總值。

這不是比前一題容易多了嗎？9!=362,880 排列數目少了太多，把之前的test3.c改一下，不用一秒就可以算出來了。沒錯，我改了一個test3_3x3.c的程式， 來算這個題目。果然0.04秒就算完了。

但老師的題目不只是如此，題目是自己設計一個題目（也就是自行指定各行列的加總值），而這個題目可以求出最多的答案（就是1到9的排列符合此行列加總值的數目最多）。

一開始，我們父子倆想到的方法就是填入可以倆倆交換的數對，例如：

這4個數字，2比1大1，而3比4小1，所以1，2互換，同時3，4互換。這樣第一行和第二行的加總值都不會改變，而且第一列和第二列的列加總也不會改變。以這種想法, 可以再加上5,6或7,8等，這樣就可以有多種換法，所以可以得到多個答案。但是到底有多少答案呢？當然，可以用test3_3x3.c來求解即可。把9個數字排好後，求出各列和各行的加總值，放到test3_3x3.c程式去：

如上圖中的A1, A2, ..., B3，共6個數字。

這樣就可以求解得這個題目的答案數目，問題是要找到最多答案的題目，我們要試很多種行列加總值，這樣是要試到何時，而且也不能確定最多答案是多少。我們排了一種情況，算出其行列加總值，由test3_3x3.c求得其答案數為18種。這是最多的答案數了嗎？不知道，所以又排了另一種情況，運算不錯，其答案數目為30種。但是不是有更多種答案數目的呢？

這時候，宊然想到一個方法：

即然，我們已經可以由程式排出1到9的所有排列，我們也就可以同時得到每一種排列的行列加總值啊！那就把行列加總值排序，同樣的行列加總值計數，這樣不就可以得到同樣的行列加總值可以得到的答案數目嗎！取最大的數目，就是正確的解答了！

因此，修改test3_3x3.c得到test3_3x3_max.c:

1. 取消印出進度

2. 不再比較行列加總值

3. 每個排列都輸出其行列加總值，如下程式

test3_3x3_mac 程式的輸出：

...

12,15,18,18,12,15

12,15,18,18,10,17

12,15,18,17,11,17

12,15,18,17,12,16

12,12,21,19,13,13

12,12,21,19,11,15

12,12,21,20,12,13

12,12,21,20,11,14

12,12,21,18,13,14

12,12,21,18,12,15

...

接下來的排序和計數，就不用自己寫程式了，因為UNIX已經有提供現成的指令：

$ ./test3_3x3_max | sort | uniq -c | sort -nr > result.txt

$ nano result.txt

就可以看到答案了：

所以行列加總值 17,14,14,17,14,14，也就是

A1=17, A2=14, A3=14, B1=17, B2=14, B3=14

的題目可以有80種答案。

不信的話，利用test3_3x3.c來求算，就可以列出這80種不同的排列。

程式同樣放在GitHub: https://github.com/poushen/math_game1