ProjectEuler 185 -- TLE on backtracking

Backtracking 只是比較聰明的暴力法，

所以 time complexity 大約還是 10^16。

import sys

DIGIT_COUNT = 5

#DIGIT_COUNT = 15

ANSWER = [0] * DIGIT_COUNT

GUESSES = { 
    "90342" : 2, 
    "70794" : 0, 
    "39458" : 2, 
    "34109" : 1, 
    "51545" : 2, 
    "12531" : 1,
}

#GUESSES = {
#    "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,
#}

def is_unique(digit, position):
    has_more = False

def check_guessing(dimension):
    for guess in GUESSES:
        correct_count = 0
        for i in range(dimension):
            if ANSWER[i] == int(guess[i]):
                correct_count += 1
            if correct_count > GUESSES[guess]:
                return False
        if correct_count + DIGIT_COUNT - dimension < GUESSES[guess]:
            return False
    return True

def backtracking(dimension):
    if not check_guessing(dimension):
        return
    if dimension == DIGIT_COUNT:
        print('Found =>', ANSWER[0:dimension])
        return
    for i in range(10):
        ANSWER[dimension] = i
        backtracking(dimension + 1)    
    
def solve():
    for i in range(10):
        ANSWER[0] = i
        backtracking(1)
    
def main():
    solve()
    
if __name__ == '__main__':
    sys.exit(main())