0166 纵横交错
* * * *
拉格朗日计划
* * * *
纵横交错

把0到9之间的整数(包括0和9)填入$4\times 4$的方格。

例如按下图的填法 $$\begin{matrix}6 & 3 & 3 & 0 \\ 5 & 0 & 4 & 3 \\ 0 & 7 & 1 & 4 \\ 1 & 2 & 4 & 5 \end{matrix}$$ 那么每行、每列、以及两条对角线上的数字和都是$12$。

把0到9之间的整数(包括0和9)填入$4\times 4$的方格,使得每一行、每一列和两条对角线上的和都相同的填法共有多少种?

本题难度:



解答

首先枚举每一行的不同填法,共有$10^4$种,按照这一行的和将这些填法分类。

随后遍历所有的行和,对每一个和数,取出两种填法(可以相同)x和y作为方格的前两行(从上往下填),记录$(x[0]+y[0],x[1]+y[1],x[2]+y[2],x[3]+y[3],x[0]+y[1],x[3]+y[2])$作为键值。

那么后两行(从下往上填)每行的和也应当是s,并且键值应该是$(s-k[0],s-k[1],s-k[2],s-k[3],s-k[5],s-k[4])$,找出具有该键值的行对的数量再汇总即可。

结果是$7130034$。

import itertools

p={}
for a,b,c,d in itertools.product(range(10),repeat=4):
    s=a+b+c+d
    if s in p:
        p[s].append([a,b,c,d])
    else:
        p[s]=[[a,b,c,d]]

res=0
for s in p:
    print s,len(p[s])
    q={}
    for x,y in itertools.product(p[s],repeat=2):
        k=(x[0]+y[0],x[1]+y[1],x[2]+y[2],x[3]+y[3],x[0]+y[1],x[3]+y[2])
        q[k]=q.get(k,0)+1
    print len(q)
    for k in q:
        k2=(s-k[0],s-k[1],s-k[2],s-k[3],s-k[5],s-k[4])
        res+=q.get(k2,0)*q[k]

print res