我正在尝试在 python 中实现 Donald Knuth 的密码破解算法，只需不超过 5 步。我已经多次检查了我的代码，它似乎遵循算法，如下所示：http://en.wikipedia.org/wiki/Mastermind_(board_game)#五猜算法
然而，我发现有些秘密需要 7 甚至 8 步才能完成。这是代码：
#returns how many bulls and cows there are
def HowManyBc(guess,secret):
invalid=max(guess)+1
bulls=0
cows=0
r=0
while r<4:
if guess[r]==secret[r]:
bulls=bulls+1
secret[r]=invalid
guess[r]=invalid
r=r+1
r=0
while r<4:
p=0
while p<4:
if guess[r]==secret[p] and guess[r]!=invalid:
cows=cows+1
secret[p]=invalid
break
p=p+1
r=r+1
return [bulls,cows]
# sends every BC to its index in HMList
def Adjustment(BC1):
if BC1==[0,0]:
return 0
elif BC1==[0,1]:
return 1
elif BC1==[0,2]:
return 2
elif BC1==[0,3]:
return 3
elif BC1==[0,4]:
return 4
elif BC1==[1,0]:
return 5
elif BC1==[1,1]:
return 6
elif BC1==[1,2]:
return 7
elif BC1==[1,3]:
return 8
elif BC1==[2,0]:
return 9
elif BC1==[2,1]:
return 10
elif BC1==[2,2]:
return 11
elif BC1==[3,0]:
return 12
elif BC1==[4,0]:
return 13
# sends every index in HMList to its BC
def AdjustmentInverse(place):
if place==0:
return [0,0]
elif place==1:
return [0,1]
elif place==2:
return [0,2]
elif place==3:
return [0,3]
elif place==4:
return [0,4]
elif place==5:
return [1,0]
elif place==6:
return [1,1]
elif place==7:
return [1,2]
elif place==8:
return [1,3]
elif place==9:
return [2,0]
elif place==10:
return [2,1]
elif place==11:
return [2,2]
elif place==12:
return [3,0]
elif place==13:
return [4,0]
# gives minimum of positive list without including its zeros
def MinimumNozeros(List1):
minimum=max(List1)+1
for item in List1:
if item!=0 and item<minimum:
minimum=item
return minimum
#list with all possible guesses
allList=[]
for i0 in range(0,6):
for i1 in range(0,6):
for i2 in range(0,6):
for i3 in range(0,6):
allList.append([i0,i1,i2,i3])
TempList=[[0,0,5,4]]
for secret in TempList:
guess=[0,0,1,1]
BC=HowManyBc(guess[:],secret[:])
counter=1
optionList=[]
for i0 in range(0,6):
for i1 in range(0,6):
for i2 in range(0,6):
for i3 in range(0,6):
optionList.append([i0,i1,i2,i3])
while BC!=[4,0]:
dummyList=[] #list with possible secrets for this guess
for i0 in range(0,6):
for i1 in range(0,6):
for i2 in range(0,6):
for i3 in range(0,6):
opSecret=[i0,i1,i2,i3]
if HowManyBc(guess[:],opSecret[:])==BC:
dummyList.append(opSecret)
List1=[item for item in optionList if item in dummyList]
optionList=List1[:] # intersection of optionList and dummyList
item1Max=0
for item1 in allList:
ListBC=[] # [list of all [bulls,cows] in optionList
for item2 in optionList:
ListBC.append(HowManyBc(item1[:],item2[:]))
HMList=[0]*14 # counts how many B/C there are for item2 in optionList
for BC1 in ListBC:
index=Adjustment(BC1)
HMList[index]=HMList[index]+1
m=max(HMList)#maximum [B,C], more left - less eliminated (min in minimax)
maxList=[i for i, j in enumerate(HMList) if j == m]
maxElement=maxList[0] #index with max
possibleGuess=[]
if m>item1Max: #max of the guesses, the max in minimax
item1Max=m
possibleGuess=[i[:] for i in optionList if AdjustmentInverse(maxElement)==HowManyBc(item1[:],i[:])]
nextGuess=possibleGuess[0][:]
guess=nextGuess[:]
BC=HowManyBc(guess[:],secret[:])
counter=counter+1
I get:
对于 [5, 3, 3, 4] 计数器是 7
对于 [5, 4, 4, 5] 计数器是 8
如果有人可以提供帮助，我将非常感激！
谢谢，迈克
