``````DIGITS = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
ZERO = {"0"}
OPERATORS = {"+", "-", "*", "/"}
EQUAL = {'='}

CORRECT = "c"
INCORRECT = "i"
ABSENT = "a"

class Solver:
def __init__(self, digits=DIGITS, operators=OPERATORS):
self.digits = digits.copy()
self.operators = operators.copy()
self.corrects = [None] * 8
self.incorrects = [set() for _ in range(8)]
self.unused = digits | operators

def all_absent(self, char, expr, result):
res = True
for e,r in zip(list(expr), list(result)):
if e == char:
res &= (r == ABSENT)
return res

def record(self, last_expr, last_result):
for i,(e,r) in enumerate(zip(list(last_expr), list(last_result))):
self.unused -= {e}
if r == CORRECT:
self.corrects[i] = e
elif r == ABSENT:
if self.all_absent(e, last_expr, last_result):
if e in self.digits:
self.digits -= {e}
elif e in self.operators:
self.operators -= {e}
elif r == INCORRECT:
else:
pass

def next_set(self, expr, element=[]):
if len(expr) == 0:
return self.digits - ZERO
elif len(expr) == 1:
return self.digits | self.operators
elif set(expr) & EQUAL == EQUAL:
return self.digits
elif len(expr) == 6 and expr[-1] not in EQUAL:
return EQUAL
elif set(expr) & OPERATORS != set() and expr[-1] not in OPERATORS:
return self.digits | self.operators | EQUAL
else:
if expr[-1] in OPERATORS:
return self.digits - ZERO
elif len(expr) > 2 and set(expr[-3:]) - DIGITS == set():
return self.operators
else:
return self.digits | self.operators

def validate(self, expr, res):
if self.unused == set() and (self.digits | self.operators) - set(expr) != set():
return False
if set(expr) & EQUAL == set():
return False
if not set(res) <= self.digits:
return False
for i,e in enumerate(res):
pos = len(expr) - len(res) + i
if self.corrects[pos] is not None and e != self.corrects[pos]:
return False
elif e in self.incorrects[pos]:
return False
return True

def score(self, expr):
# Favour experessions that use many different symbols and use many yet-unused symbols.
return -(len(self.unused | set(expr)) + len(set(expr)))

def evaluate(self, expr, solutions):
try:
res = eval("".join(expr[:-1]))
except:
pass
else:
if res >= 0 and int(res) == res:
res = list(str(int(res)))
if len(expr) + len(res) == 8:
expr += res
if self.validate(expr, res):

def _solve(self, solutions, expr=[]):
pos = len(expr)
if pos > 0 and expr[-1] in EQUAL:
self.evaluate(expr, solutions)
else:
next_set = self.next_set(expr) - self.incorrects[pos]
if self.corrects[pos] is not None:
next_set &= {self.corrects[pos]}
for e in next_set:
self._solve(solutions, expr + [e])

def _solutions(self):
solutions = set()
self._solve(solutions)
return {(self.score(e), e) for e in solutions}

def solve(self):
solutions = list(self._solutions())
return (sorted(solutions)[0], len(solutions))

def input(self, prompt=""):
while True:
s = input(prompt).strip()
if len(s) == 8 and set(s) <= { CORRECT, INCORRECT, ABSENT }:
return s
else:
print("Invalid input")

def run(self, expr="8+7*6=50", count=2562890625):
if count == 2562890625:
print("([c]orrect [i]ncorrect [a]bsent")
if count > 1:
self.record(expr, self.input(f"{expr} > ").strip())
try:
(score, expr), count = self.solve()
except:
print("Failed to find a suitable solution")
else:
self.run(expr, count)
else:
print(expr)

if __name__ == '__main__':
Solver().run()
``````