Constraint satisfaction: coloring a map
A constraint satisfaction problem (CSP) is defined by variables, a domain of possible values for each, and constraints that restrict which combinations of values are allowed. A solution is a complete assignment that satisfies every constraint. Scheduling, timetabling, sudoku, and circuit layout are all CSPs.
Python
NEIGHBORS = {
"WA": ["NT", "SA"],
"NT": ["WA", "SA", "Q"],
"SA": ["WA", "NT", "Q", "NSW", "V"],
"Q": ["NT", "SA", "NSW"],
"NSW": ["Q", "SA", "V"],
"V": ["SA", "NSW"],
"T": [],
}
def solve(colors):
regions = list(NEIGHBORS)
def backtrack(assignment):
if len(assignment) == len(regions):
return assignment
region = next(r for r in regions if r not in assignment)
for color in colors:
if all(assignment.get(neighbor) != color for neighbor in NEIGHBORS[region]):
result = backtrack({**assignment, region: color})
if result:
return result
return None
return backtrack({})
solution = solve(["red", "green", "blue"])
print(dict(sorted(solution.items())))
print(all(solution[a] != solution[b] for a in NEIGHBORS for b in NEIGHBORS[a]))
print(solve(["red", "green"]))