Exhaustive search for best play in number game

24-game.py

N = 24

OTHER_FACTORS = {
    n: { i for i in range(1, n) if n % i == 0 }
    for n in range(1, N+1)
}

best_score = 0
trace_achieving_best_score = None

def search(rem, score, trace):
  global best_score, trace_achieving_best_score
  
  if score > best_score:
    best_score = score
    trace_achieving_best_score = trace
  
  candidates = {
    i
    for i in rem
    if len(OTHER_FACTORS[i] & rem) > 0
  }
  
  for candidate in candidates:
    search(rem - OTHER_FACTORS[candidate] - { candidate }, score + candidate, trace + (candidate,))

search(frozenset(range(1, N+1)), 0, ())

print(f"Best score: {best_score}")
print("Achieved by playing:", trace_achieving_best_score)