猜数字

猜数字是大家十分熟悉的游戏。

玩家需要猜测一个预设的数字序列，每次猜测后，你会被告知你猜对了多少个位置上的数字。

与“文曲星”等设备中广为流传的猜数字游戏不同，本题中只反馈位置和数值的正确的数字，不反馈数值正确但位置不正确的数字。

例如，若正确的序列是1234，而你猜的是2036，那么你猜对了一个数字（即第三个位置上的3)，因此反馈为1个数字正确，而不是传统猜数字游戏的1A1B。

显然只要猜测的次数充分多就可以找出唯一解，例如根据以下几条对一个五位数字序列猜测可得其唯一解是39542。

90342：2个数字正确。

70794：0个数字正确。

39458：2个数字正确。

34109：1个数字正确。

51545：2个数字正确。

12531：1个数字正确。

根据下面的22条猜测数据，求出唯一满足要求的16位数字序列：

5616185650518293：2个数字正确。

3847439647293047：1个数字正确。

5855462940810587：3个数字正确。

9742855507068353：3个数字正确。

4296849643607543：3个数字正确。

3174248439465858：1个数字正确。

4513559094146117：2个数字正确。

7890971548908067：3个数字正确。

8157356344118483：1个数字正确。

2615250744386899：2个数字正确。

8690095851526254：3个数字正确。

6375711915077050：1个数字正确。

6913859173121360：1个数字正确。

6442889055042768：2个数字正确。

2321386104303845：0个数字正确。

2326509471271448：2个数字正确。

5251583379644322：2个数字正确。

1748270476758276：3个数字正确。

4895722652190306：1个数字正确。

3041631117224635：3个数字正确。

1841236454324589：3个数字正确。

2659862637316867：2个数字正确。

注：原题题面涉及到外国的电视节目，此处修改为国内读者更熟悉的猜数字游戏。

本题难度:

解答

本题是SAT类型的问题（Boolean Satisfiability Problem），这一类问题至少是NP完全问题，天然地具有较高的复杂度，因此尝试寻找一个“聪明”的方法的意义不大，我们的目标是尽可能降低一些复杂度。

本解法使用经典的折半搜索（meet in the middle algorithm）策略，由于16位折半后是8位搜索量仍比较大，因此折办两次再搜索。

生成0000到9999之间的所有四位数字串，将每个数字串分别与给定的22个16位串的第1到4位、5到8位、9到12位、13到16位比较，并记录猜中的数量。

排除猜中次数高于给定次数的那些数字串，并将其它串以猜中次数形成的22元组为键值保存在四个字典中，字典的值就是当前的数字串。

如此可得四个规模分别为2662、4052、3122、4470的字典。

双循环合并前两个字典（计算规模为千万级），排除总猜中次数高于给定次数，保留其他并仍按上述规则生成字典x。

双循环合并后两个字典，并按合并结果比照给定的猜中次数在x中搜索，最后合并符合要求的数字串即得结果$4640261571849533$。

d=["5616185650518293",
"3847439647293047",
"5855462940810587",
"9742855507068353",
"4296849643607543",
"3174248439465858",
"4513559094146117",
"7890971548908067",
"8157356344118483",
"2615250744386899",
"8690095851526254",
"6375711915077050",
"6913859173121360",
"6442889055042768",
"2321386104303845",
"2326509471271448",
"5251583379644322",
"1748270476758276",
"4895722652190306",
"3041631117224635",
"1841236454324589",
"2659862637316867"]

c=[2,1,3,3,3,1,2,3,1,2,3,1,1,2,0,2,2,3,1,3,3,2]
x1,x2,x3,x4={},{},{},{}
for m in range(10000):
    s=str(m).zfill(4)
    c1=[sum(s[i]==t[i] for i in range(0,4)) for t in d]
    c2=[sum(s[i]==t[4+i] for i in range(0,4)) for t in d]
    c3=[sum(s[i]==t[8+i] for i in range(0,4)) for t in d]
    c4=[sum(s[i]==t[12+i] for i in range(0,4)) for t in d]
    if all(c[i]>=c1[i] for i in range(22)):
        x1[tuple(c1)]=s
    if all(c[i]>=c2[i] for i in range(22)):
        x2[tuple(c2)]=s
    if all(c[i]>=c3[i] for i in range(22)):
        x3[tuple(c3)]=s
    if all(c[i]>=c4[i] for i in range(22)):
        x4[tuple(c4)]=s

print len(x1),len(x2),len(x3),len(x4)

x={}
for a in x1:
    for b in x2:
        u=[a[i]+b[i] for i in range(22)]
        if all(c[i]>=u[i] for i in range(22)):
            x[tuple(u)]=x1[a]+x2[b]

print len(x)

found=False
for a in x3:
    for b in x4:
        u=tuple([c[i]-a[i]-b[i] for i in range(22)])
        if u in x:
            print x[u]+x3[a]+x4[b]
            found=True
            break
    if found:
        break