Formally, what you have in the example is a simple constraint satisfaction problem with three variables ['a', 'b', 'c']
, each with a finite domain of integers and the "all-distinct" constraint.
Backtracking search with appropriate heuristics can solve this type of problems fairly quickly in practice. E.g.
def backtracking(domains):
if any(len(dom) == 0 for var, dom in domains.iteritems()):
return None
if all(len(dom) == 1 for var, dom in domains.iteritems()):
return domains
# minimum remaining values heuristic: process variables with few possible
# values first (fail-first strategy)
order = sorted(domains.iteritems(), key=lambda (var, dom): len(dom))
for var, dom in order:
if len(dom) == 1:
continue
for value in list(dom):
doms = {v: d - {value} for v, d in domains.iteritems()
if v != var}
doms[var] = {value}
solution = backtracking(doms)
if solution is not None:
return solution
print(backtracking({v: set(d) for v, d in options.iteritems()}))