Project Euler 166

发表于 更新于 分类于 阅读次数： 本文字数： 700 阅读时长 ≈ 1 分钟

Project Euler 166

题目

Criss Cross

A $4\times 4$ grid is filled with digits $d$, $0 \le d \le 9$.

It can be seen that in the grid

the sum of each row and each column has the value $12$. Moreover the sum of each diagonal is also $12$.

In how many ways can you fill a $4\times 4$ grid with the digits $d$, $0 \le d \le 9$ so that each row, each column, and both diagonals have the same sum?

解决方案

本题基于meet-in-the-middle的思想完成。

首先枚举幻方一行中所有的可能性填法，按照行的和分别存储，共$10000$种可能的填法。

接下来，枚举前两行的填法。

第二行元素的和$s$必须和第一行相同（这就是按和分类存储的原因）。这时就枚举了整个幻方的一半数字。用一个六元组$(a,b,c,d,e,f)$分别统计这一半的填法分别有多少，其中，$a,b,c,d$分别表示幻方$4$列上的两个数的和，$e,f$则表示主副对角线上两个数的和。

不失一般性，幻方的下两行和上两行的枚举方式是完全一样的。下面两行如果存在一种填法$(a,b,c,d,e,f)$，那么上面两行的填法一定是$(s-a,s-b,s-c,s-d,s-e,s-f)$。

直接统计这种做法个数之和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
mp = {}
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            for l in range(10):
                w = i + j + k + l
                if w not in mp.keys():
                    mp[w] = []
                mp[w].append((i, j, k, l))
for s, vec in mp.items():
    mq = {}
    for u in vec:
        for v in vec:
            t = (u[0] + v[0], u[1] + v[1], u[2] + v[2], u[3] + v[3], u[0] + v[1], u[3] + v[2])
            if t not in mq:
                mq[t] = 0
            mq[t] += 1
    for u in vec:
        for v in vec:
            t = (s - u[0] - v[0], s - u[1] - v[1], s - u[2] - v[2], s - u[3] - v[3], s - u[2] - v[3], s - u[1] - v[0])
            if t in mq:
                ans += mq[t]
print(ans)