魔方陣で最大値？

魔方陣で最大値？

締め切りが 2017/01/09 10:00 AM なので，その 1 分後に投稿されるように予約

設問

４×４の魔方陣は1〜16までの数字を１度ずつ使ったもので、以下の左図のようなものがあります。



魔方陣は縦、横、斜めのすべての列について、その和が等しいという特徴があります。

魔方陣において、左上のマスからスタートして、右か下の隣り合うマスへの移動を繰り返して最短距離で右下のマスまで移動します。
このとき、経由したマスの数の和が最大になるような移動経路を考えます。
上図の魔方陣の場合、上図右のように移動すると和は 67 になります。

標準入力から整数 n が与えられたとき、４×４のすべての魔方陣に対してこのような移動経路を求め、その和が n になる魔方陣の個数を求め、標準出力に出力してください。

４×４の魔方陣は全部で7,040個存在することが知られています。
その中で、n=54のときは以下の2パターンに回転や鏡像を含めたものが全部で8通りありますので、以下のような入出力になります。



【入出力サンプル】
標準入力
54

標準出力
8

=================

R で書くと制限時間（1 秒）に引っかかるので，AWK で書いた（Java でも C でもよいけど）
魔方陣の生成部分はネットを参考に

func = function(num) {
    route = function(table) {
        sums = integer(20)
        sums[1] = table[1, 2] + table[1, 3] + table[1, 4] + table[2, 4] + table[3, 4]
        sums[2] = table[1, 2] + table[1, 3] + table[2, 3] + table[2, 4] + table[3, 4]
        sums[3] = table[1, 2] + table[1, 3] + table[2, 3] + table[3, 3] + table[3, 4]
        sums[4] = table[1, 2] + table[1, 3] + table[2, 3] + table[3, 3] + table[4, 3]
        sums[5] = table[1, 2] + table[2, 2] + table[2, 3] + table[2, 4] + table[3, 4]
        sums[6] = table[1, 2] + table[2, 2] + table[2, 3] + table[3, 3] + table[3, 4]
        sums[7] = table[1, 2] + table[2, 2] + table[2, 3] + table[3, 3] + table[4, 3]
        sums[8] = table[1, 2] + table[2, 2] + table[3, 2] + table[3, 3] + table[3, 4]
        sums[9] = table[1, 2] + table[2, 2] + table[3, 2] + table[3, 3] + table[4, 3]
        sums[10] = table[1, 2] + table[2, 2] + table[3, 2] + table[4, 2] + table[4, 3]
        sums[11] = table[2, 1] + table[2, 2] + table[2, 3] + table[2, 4] + table[3, 4]
        sums[12] = table[2, 1] + table[2, 2] + table[2, 3] + table[3, 3] + table[3, 4]
        sums[13] = table[2, 1] + table[2, 2] + table[2, 3] + table[3, 3] + table[4, 3]
        sums[14] = table[2, 1] + table[2, 2] + table[3, 2] + table[3, 3] + table[3, 4]
        sums[15] = table[2, 1] + table[2, 2] + table[3, 2] + table[3, 3] + table[4, 3]
        sums[16] = table[2, 1] + table[2, 2] + table[3, 2] + table[4, 2] + table[4, 3]
        sums[17] = table[2, 1] + table[3, 1] + table[3, 2] + table[3, 3] + table[3, 4]
        sums[18] = table[2, 1] + table[3, 1] + table[3, 2] + table[3, 3] + table[4, 3]
        sums[19] = table[2, 1] + table[3, 1] + table[3, 2] + table[4, 2] + table[4, 3]
        sums[20] = table[2, 1] + table[3, 1] + table[4, 1] + table[4, 2] + table[4, 3]
        max(sums + table[1, 1] + table[4, 4]) == num
    }

    table = matrix(0, 4, 4)
    used = logical(16)
    count = 0
    for (a in 1:13) {
        used[a] = TRUE
        for (d in (a + 1):15) {
            used[d] = TRUE
            for (m in (d + 1):16) {
                p = 34 - a - d - m
                if (p < a) break
                if (p > 16) next
                if (used[p]) next
                if (p == m) next
                used[m] = used[p] = TRUE
                for (f in 1:16) {
                    if (used[f]) next
                    k = 34 - a - f - p
                    if (k < 1) break
                    if (k > 16) next
                    if (used[k]) next
                    if (f == k) next
                    used[f] = used[k] = TRUE
                    for (b in 1:16) {
                        if (used[b]) next
                        c = 34 - a - b - d
                        if (c < 1) break
                        if (c > 16) next
                        if (used[c]) next
                        if (b == c) next
                        used[b] = used[c] = TRUE
                        for (g in 1:16) {
                            if (used[g]) next
                            j = 34 - d - g - m
                            if (j < 1) break
                            if (j > 16) next
                            if (used[j]) next
                            if (j == g) next
                            o = 34 - c - g - k
                            if (o < 1) break
                            if (o > 16) next
                            if (used[o]) next
                            if (o == g || o == j) next
                            n = 34 - b - f - j
                            if (n > 16) break
                            if (n < 1) next
                            if (used[n]) next
                            if (n == g || n == j || n == o) next
                            used[g] = used[j] = used[o] = used[n] = TRUE
                            for (e in 1:16) {
                                if (used[e]) next
                                h = 34 - e - f - g
                                if (h < 1) break
                                if (h > 16) next
                                if (used[h]) next
                                if (h == e) next
                                i = 34 - a - e - m
                                if (i < 1) break
                                if (i > 16) next
                                if (used[i]) next
                                if (i == e || i == h) next
                                l = 34 - d - h - p
                                if (l > 16) break
                                if (l < 1) next
                                if (used[l]) next
                                if (l == e || l == h || l == i) next
                                table[1, 1] = a
                                table[1, 2] = b
                                table[1, 3] = c
                                table[1, 4] = d
                                table[2, 1] = e
                                table[2, 2] = f
                                table[2, 3] = g
                                table[2, 4] = h
                                table[3, 1] = i
                                table[3, 2] = j
                                table[3, 3] = k
                                table[3, 4] = l
                                table[4, 1] = m
                                table[4, 2] = n
                                table[4, 3] = o
                                table[4, 4] = p
                                table2 = table[, 4:1]
                                table3 = t(table)
                                table4 = table3[, 4:1]
                                table5 = t(table2)
                                table6 = table5[, 4:1]
                                table7 = t(table4)
                                table8 = table7[, 4:1]
                                ans = sum(route(table), route(table2), route(table3), route(table4), route(table5),
                                    route(table6), route(table7), route(table8))
                                count = count + ans
                            }
                            used[g] = used[j] = used[o] = used[n] = FALSE
                        }
                        used[b] = used[c] = FALSE
                    }
                    used[f] = used[k] = FALSE
                }
                used[m] = used[p] = FALSE
            }
            used[d] = FALSE
        }
        used[a] = FALSE
    }
    count
}