题目185：猜数字游戏

欧拉计划

Number Mind

The game Number Mind is a variant of the well known game Master Mind.

Instead of coloured pegs, you have to guess a secret sequence of digits. After each guess you're only told in how many places you've guessed the correct digit. So, if the sequence was 1234 and you guessed 2036, you'd be told that you have one correct digit; however, you would NOT be told that you also have another digit in the wrong place.

For instance, given the following guesses for a 5-digit secret sequence,

90342 ;2 correct
70794 ;0 correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct

The correct sequence 39542 is unique.

Based on the following guesses,

5616185650518293 ;2 correct
3847439647293047 ;1 correct
5855462940810587 ;3 correct
9742855507068353 ;3 correct
4296849643607543 ;3 correct
3174248439465858 ;1 correct
4513559094146117 ;2 correct
7890971548908067 ;3 correct
8157356344118483 ;1 correct
2615250744386899 ;2 correct
8690095851526254 ;3 correct
6375711915077050 ;1 correct
6913859173121360 ;1 correct
6442889055042768 ;2 correct
2321386104303845 ;0 correct
2326509471271448 ;2 correct
5251583379644322 ;2 correct
1748270476758276 ;3 correct
4895722652190306 ;1 correct
3041631117224635 ;3 correct
1841236454324589 ;3 correct
2659862637316867 ;2 correct

Find the unique 16-digit secret sequence.

题目：

猜数字游戏 Number Mind 是著名游戏 Master Mind 的一个变种。

与着色的柱子不同，你现在必须猜测一个秘密的数的序列。每次猜测之后，你只能得知你猜中多少个正确位置。因此，如果序列是 1234，你猜是 2036，则它会告诉你，你猜对了一个数字；但是，你在错误位置上放了另一个数字时，它是不会告诉你的。

比如，给出一个 5 位的数字序列的猜测结果，

90342 ；2 位正确
70794 ；0 位正确
39458 ；2 位正确
34109 ；1 位正确
51545 ；2 位正确
12531 ；1 位正确

可以得到唯一正确的序列 39542。

基于下面的猜测结果，

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 位正确

请给出唯一正确的 16 位秘密序列。

JAY饭

1. import itertools as it
   
2. t = '''2659862637316867 ；2
   
3. 1841236454324589 ；3
   
4. 3041631117224635 ；3
   
5. 4895722652190306 ；1
   
6. 1748270476758276 ；3
   
7. 5251583379644322 ；2
   
8. 2326509471271448 ；2
   
9. 2321386104303845 ；0
   
10. 6442889055042768 ；2
    
11. 6913859173121360 ；1
    
12. 6375711915077050 ；1
    
13. 8690095851526254 ；3
    
14. 2615250744386899 ；2
    
15. 8157356344118483 ；1
    
16. 7890971548908067 ；3
    
17. 4513559094146117 ；2
    
18. 3174248439465858 ；1
    
19. 4296849643607543 ；3
    
20. 9742855507068353 ；3
    
21. 5855462940810587 ；3
    
22. 3847439647293047 ；1
    
23. 5616185650518293 ；2'''
    
24. 
    
25. s = []
    
26. for i in t.split('\n'):
    
27.     f = i.strip()
    
28.     m = []
    
29.     for j in f.split('；'):
    
30.         j = j.strip()
    
31.         m.append(j)
    
32.     s.append(m)
    
33. 
    
34. s1 =[]
    
35. for each in s:
    
36.     m = []
    
37.     for i in each[0]:
    
38.         m.append(int(i))
    
39.     s1.append((m,int(each[1])))
    
40. 
    
41. t = s1[7]
    
42. s1.remove(t)
    
43. 
    
44. def shai_1():
    
45.     weizhi1 = []
    
46.     for i in s1:
    
47.         m = []
    
48.         for j in range(16):
    
49.             if i[0][j] != t[0][j]:
    
50.                 m.append(j)
    
51.         weizhi1.append(m)
    
52.    
    
53.     return weizhi1
    
54. 
    
55. weizhi = shai_1()
    
56. 
    
57. 
    
58. def sheng():
    
59.     S = []
    
60.     for t in it.combinations(weizhi[0],s1[0][1]):
    
61.         s_t = ['x']*16
    
62.         for x1 in range(s1[0][1]):
    
63.             s_t[t[x1]] = s1[0][0][t[x1]]
    
64.         s_x = s_t[:]
    
65.         S.append((s_x,t))
    
66.     return S
    
67.         
    
68. 
    
69. def shai_2(S, t, c, weizhi):
    
70. 
    
71.     if len(t)==16:
    
72.         V = 1
    
73.         for a in range(21):
    
74.             count = 0
    
75.             for each in range(16):
    
76.                 if S[each] == s1[a][0][each]:
    
77.                     count +=1
    
78.             if count != s1[a][1]:
    
79.                 V =0
    
80.                 break
    
81.         if V == 1:
    
82.             print(S)
    
83.                     
    
84.         return 1
    
85.     for i in range(c,21):
    
86.         s_t = S[:]
    
87.         flag = 1
    
88.         for j in weizhi[i]:
    
89.             if s_t[j] == s1[i][0][j]:
    
90.                 flag = 0
    
91.                 break
    
92.         if flag == 1:
    
93.             t1 = [k for k in weizhi[i] if k not in t]
    
94.             for x in it.combinations(t1,s1[i][1]):
    
95.                 t2 = t
    
96.                 s_y = s_t[:]
    
97.                 for y in range(s1[i][1]):
    
98.                     s_y[x[y]] = s1[i][0][x[y]]
    
99.                 s_z = s_y[:]
    
100.                 t2 += x
     
101.                 c = i
     
102.                 shai_2(s_z, t2, c, weizhi)
     
103. 
     
104. 
     
105. def main():
     
106.     M = sheng()
     
107.     for i in M:
     
108.         S,t = i[0],i[1]
     
109.         shai_2(S,t,1,weizhi)
     
110. 
     
111. main()
     
112.    
     

复制代码