2014/11/24

再用 list comprehension 解魔方陣

小朋友的學校又給了一個特殊的魔方陣題目,erlang 的 list comprehension 解魔方陣真的很快,把每一種可能發生的狀況慢慢列出來,就可以得出結果了。

題目:
五芒星共十個節點,填入 1 ~ 10 的數字,外側有五個小三角形,每一個小三角形的三個數字和,如果是 13,請列出十個節點的填法。再把總和改為14,15,16,17,18,19,20,分別找出可能的填寫方法。

如果用筆慢慢計算,必須要這樣想,五個三角形總和都是 13,13*5=45,因為 1~10 十個數字的總和是 55,但中間的 A,B,C,D,E 各被多加了一次,所以 A+B+C+D+E+55=45,因此 A+B+C+D+E = -10,此題無解。

至於 14,就是 A+B+C+D+E+55=14*5,所以 A+B+C+D+E=15,再慢慢列舉 A,B,C,D,E 進而找出 F,G,H,I,J。

用 erlang 可以這樣寫 matrix.erl

-module(matrix).
-export([resolve/1]).

resolve(SUM) ->
    statistics(runtime),
    statistics(wall_clock),
    K = lists:seq(1,10),
    L=[{A,B,C,D,E,F,G,H,I,J}||
     A <- K,
     B <- K--[A],
     F <- K--[A,B],
     A+B+F == SUM,

     C <- K--[A,B,F],
     G <- K--[A,B,F,C],
     B+C+G == SUM,

     D <- K--[A,B,F,C,G],
     H <- K--[A,B,F,C,G,D],
     C+D+H == SUM,

     E <- K--[A,B,F,C,G,D,H],
     I <- K--[A,B,F,C,G,D,H,E],
     D+E+I == SUM,

     J <- K--[A,B,F,C,G,D,H,E,I],
     A+E+J == SUM
    ],
    {_, Time1} = statistics(runtime),
    {_, Time2} = statistics(wall_clock),
    io:format("runtime=~p wall_clock=~p ~n", [Time1, Time2]),
    L.

編譯後,再到 erl 執行。

1> matrix:resolve(13).
runtime=0 wall_clock=0
[]
2> matrix:resolve(14).
runtime=15 wall_clock=15
[{1,3,5,2,4,10,6,7,8,9},
 {1,4,2,5,3,9,8,7,6,10},
 {2,4,1,3,5,8,9,10,6,7},
 {2,5,3,1,4,7,6,10,9,8},
 {3,1,4,2,5,10,9,8,7,6},
 {3,5,2,4,1,6,7,8,9,10},
 {4,1,3,5,2,9,10,6,7,8},
 {4,2,5,3,1,8,7,6,10,9},
 {5,2,4,1,3,7,8,9,10,6},
 {5,3,1,4,2,6,10,9,8,7}]

我們把一個答案填到五芒星中。

目前的缺點是 A,B,C,D,E 重複的 set,並沒有排除掉相同的答案,還沒想到要怎麼處理。

結果蠻奇怪的,13, 15, 18, 20 沒有解,14,16,17,19 有解,沒有什麼特別的規則。

沒有留言:

張貼留言