能否将4位非首零无重复数字的Mastermind算法最坏步数从7优化到6？

我正在用Python实现Mastermind求解算法，选用了Knuth提出的Minimax求解器——该求解器在4位置、6颜色可重复的场景下，承诺最坏情况仅需5步即可猜出密码。

我的实现场景为：4个位置、10个数字且无重复，同时猜测的数字不能以0开头，因此总共有9×9×8×7=4536种可能的密码。我让代码遍历所有可能组合进行自我对战，预设了前两次猜测，结果显示有241种情况求解器需要7步才能猜出，当前最坏情况为7步。

请问是否可以优化该算法，使得所有情况都能在最多6步内猜出密码？例如，密码9872当前需要7步才能猜出。

附我的实现代码：

import random

possible_combs = []
possible_feedbacks = [[0,0], [0,1], [0,2], [0,3], [0,4], [1,0], [1,1], [1,2], [1,3], [2,0], [2,1], [2,2], [3,0]]

def check_dup(number):
    if len(set(str(number))) != 4:
        return False
    else:
        return True
    
for i in range(1000,10000):
    if check_dup(i):
      possible_combs.append(i)

all_combs = possible_combs.copy()

def match_answer(number, last_number):
    pluses = sum([1 for a, b in zip(str(number), str(last_number)) if a == b])

    minuses = len(set(str(last_number)) & (set(str(number)))) - pluses
    return [pluses, minuses]


def constrain(pergj, answers, feedbacks):
    leng = len(answers)
    valid = True

    if leng == 0:
        return valid
    else:   
        for i in range(0,leng):
            if match_answer(pergj, answers[i]) != feedbacks[i]:
                valid = False
        
    return valid

#the minimax implementation with some pruning to make it faster
def get_next_guess(all_combs, possible_combs, answers):
    min_guess = 10000
    next_guess = 1234

    for i in all_combs:
        max = -1000

        for j in possible_feedbacks:
            if max > min_guess:
                break
            eliminated = possible_combs.copy()

            for k in possible_combs:
                if max > len(eliminated):
                    break

                elif j != match_answer(k, i):
                    eliminated.remove(k)
            
            if len(eliminated) > max:
                max = len(eliminated)
            
        if max < min_guess and i not in answers:
            min_guess = max
            next_guess = i

    return next_guess

#because the second iteration of the minimax was too slow, I precomputed these values for each feedback that is possible after the starting guess of 1234
def get_second_guess(feedback):
    if feedback == [0,0]:
        return 5067
    elif feedback == [0,1]:
        return 5167
    elif feedback == [0,2]:
        return 2546
    elif feedback == [0,3]:
        return 2015
    elif feedback == [0,4]:
        return 1342
    elif feedback == [1,0]:
        return 1035
    elif feedback == [1,1]:
        return 5236
    elif feedback == [1,2]:
        return 5236
    elif feedback == [1,3]:
        return 1023
    elif feedback == [2,0]:
        return 5014
    elif feedback == [2,1]:
        return 2035
    elif feedback == [2,2]:
        return 1023
    elif feedback == [3,0]:
        return 1035

def check_minus(secret, guess):
    str_secret= str(secret)
    str_guess = str(guess)
    count=0
    for i in range(0,4):
        if str_guess[i] in str_secret and str_guess[i] != str_secret[i]:
            count += 1
    return count

def check_plus(secret, guess):
    str_secret= str(secret)
    str_guess = str(guess)
    count=0
    for i in range(0,4):
        if str_guess[i] == str_secret[i]:
            count += 1
    return count


attempts = []

#play against itself for all possible values
for number in all_combs:

    possible_combs = []
    for i in range(1000,10000):
        if check_dup(i):
            possible_combs.append(i)

    secret = number 
    found = False

    answers = []
    feedbacks = []

    while not found:

        eliminated = possible_combs.copy()

        if answers == []:
            answer_attempt = 1234 #random.choice(possible_combs)
        elif len(answers) == 1:
            answer_attempt = get_second_guess(feedback)
        else:
            answer_attempt = get_next_guess(all_combs, possible_combs, answers)

        answers.append(answer_attempt)

        pluses = check_plus(secret, answer_attempt)
        minuses = check_minus(secret, answer_attempt)

        if int(pluses) == 4:
            feedbacks.append([4,0])
            found = True
            attempts.append(len(answers))

        else:
            feedback = [int(pluses), int(minuses)]
            feedbacks.append(feedback)

            if feedback == [0,0]:
                for i in possible_combs:
                    if len(set(str(answer_attempt)) & (set(str(i)))) > 0:
                        eliminated.remove(i)
                possible_combs = eliminated.copy()       

            for i in possible_combs:   

                if feedback != match_answer(i, answer_attempt):
                    eliminated.remove(i)

            possible_combs = eliminated.copy()

print(attempts)

注：minuses指数字正确但位置错误，pluses指数字和位置均正确。

内容的提问来源于stack exchange，提问作者infinitedreamer666