Constraint Satisfaction (Map Colouring)

What is a CSP?

A constraint satisfaction problem has three parts:

Part	In map colouring
Variables	the 7 regions: WA, NT, SA, Q, NSW, V, T
Domains	every region can be red, green or blue
Constraints	neighbouring regions must have different colours

A solution gives every variable a value so that every constraint holds. Timetables, Sudoku, the N-queens puzzle, register allocation in compilers and frequency assignment for radio towers are all CSPs. The nice thing about the formulation is that one general solver works for all of them.

The neighbours of Australia’s regions form the constraint graph (white lines in the model):

Region	Neighbours
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	(none, it is an island)

Backtracking search

The basic algorithm is depth-first search over partial assignments:

backtrack(assignment):
    if every variable has a value: return assignment
    var ← choose an unassigned variable
    for each value in var's domain:
        if value is consistent with the assignment:
            assign it; result ← backtrack(assignment)
            if result is not failure: return result
            undo it                      # backtrack
    return failure

Plain backtracking

The model uses the fixed order WA, NSW, NT, Q, T, V, SA. It colours WA red, then NSW red as well (they are not neighbours, so that is allowed), NT green and Q blue, and then happily colours T and V. Only when it reaches SA, the region that touches five others, does it find that all three colours are taken by its neighbours (WA red, NT green, Q blue). The real culprit is the early choice NSW = red, but plain backtracking goes back chronologically: it changes V, then T, then Q, then NT, trying every combination of them, before it finally changes NSW to green. Altogether: 30 tries and 23 backtracks.

Forward checking

After each assignment, remove that colour from the domains of the uncoloured neighbours. If a domain becomes empty, the assignment cannot work, so undo it immediately. In the model the remaining colours are the little balls on each region. After WA = red and NSW = red, SA can only be green or blue; after NT = green, only blue; and the moment Q = blue is tried, SA’s domain is empty, so that choice is undone at once, before T and V are ever touched. Forward checking needs only 12 tries and 5 backtracks.

MRV and degree heuristics

Which variable to colour next matters even more:

• MRV (minimum remaining values): pick the variable with the fewest values left. It is the most likely to fail, so if it is going to fail, find out now (“fail first”).
• Degree heuristic (tie-breaker): among those, pick the one with the most constraints on unassigned variables.

At the start all regions have 3 colours, so the degree heuristic decides: SA (5 neighbours) goes first. After that, its neighbours have only 2 colours left and are picked next, and so on. With forward checking + MRV the map is coloured in 7 tries and 0 backtracks.

Method	Tries	Backtracks
Plain backtracking (fixed order)	30	23
+ forward checking	12	5
+ forward checking + MRV / degree	7	0

A third heuristic chooses the value: least constraining value tries first the colour that removes the fewest options from the neighbours. (Variables: fail first. Values: succeed first.)

Going further

• Arc consistency (AC-3) propagates more than forward checking. For every pair of neighbours X and Y, every value of X must have some compatible value of Y; values without support are deleted, and the deletions spread through the graph. On some problems (easy Sudokus, for instance) this alone solves the puzzle.
• Backjumping goes back to a variable that actually caused the conflict, instead of simply the most recent one, so it would skip T and V.
• Local search such as min-conflicts starts with a complete (wrong) colouring and repeatedly changes a conflicted variable to the value with the fewest conflicts. It solves the million-queens problem in seconds. See hill climbing.
• Problem structure helps too: Tasmania is not connected to the rest, so it is an independent sub-problem, and a tree-shaped constraint graph can be solved in linear time.

Code

NEIGHBOURS = {
    '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': [],
}
COLOURS = ['red', 'green', 'blue']
ORDER = ['WA', 'NSW', 'NT', 'Q', 'T', 'V', 'SA']     # a fixed order that hits a dead end late

def solve(forward_checking=False, mrv=False):
    """Backtracking search. Returns (solution, number of assignments tried, number of backtracks)."""
    stats = {'tries': 0, 'backtracks': 0}
    domains = {v: list(COLOURS) for v in NEIGHBOURS}

    def pick(assignment):
        free = [v for v in ORDER if v not in assignment]
        if not mrv:
            return free[0]
        # MRV: fewest values left; tie-break: most unassigned neighbours (degree heuristic)
        return min(free, key=lambda v: (len(domains[v]), -sum(n not in assignment for n in NEIGHBOURS[v])))

    def backtrack(assignment):
        if len(assignment) == len(NEIGHBOURS):
            return dict(assignment)
        var = pick(assignment)
        for colour in list(domains[var]):
            if any(assignment.get(n) == colour for n in NEIGHBOURS[var]):
                continue                                   # violates a constraint
            stats['tries'] += 1
            assignment[var] = colour
            saved = {v: list(d) for v, d in domains.items()}
            ok = True
            if forward_checking:                           # remove the colour from the neighbours' domains
                for n in NEIGHBOURS[var]:
                    if n not in assignment and colour in domains[n]:
                        domains[n].remove(colour)
                        if not domains[n]:
                            ok = False                     # a neighbour has no colour left: give up early
            if ok:
                result = backtrack(assignment)
                if result:
                    return result
            del assignment[var]
            domains.update(saved)
            stats['backtracks'] += 1
        return None

    return backtrack({}), stats['tries'], stats['backtracks']

for fc, mrv in [(False, False), (True, False), (True, True)]:
    sol, tries, back = solve(fc, mrv)
    print('forward checking' if fc else 'plain', '+ MRV' if mrv else '', '| tries', tries, '| backtracks', back)
    print('   ', sol)
# plain  | tries 30 | backtracks 23
#     {'WA': 'red', 'NSW': 'green', 'NT': 'green', 'Q': 'red', 'T': 'red', 'V': 'red', 'SA': 'blue'}
# forward checking  | tries 12 | backtracks 5
#     {'WA': 'red', 'NSW': 'green', 'NT': 'green', 'Q': 'red', 'T': 'red', 'V': 'red', 'SA': 'blue'}
# forward checking + MRV | tries 7 | backtracks 0
#     {'SA': 'red', 'NSW': 'green', 'Q': 'blue', 'NT': 'green', 'WA': 'blue', 'V': 'blue', 'T': 'red'}

Common mistakes

• Treating a CSP as a path search. The order in which values are assigned does not matter for the answer, only the final assignment does. That is what makes variable-ordering heuristics possible.
• Mixing up the heuristics. For the variable, choose the most constrained (fail first). For the value, choose the least constraining (succeed first).
• Forgetting to restore the domains when backtracking after forward checking.
• Thinking forward checking catches every dead end. It only looks at direct neighbours of the variable just assigned. Two neighbours left with the same single colour are only caught by arc consistency.
• Thinking heuristics change the worst case. It is still exponential; heuristics make typical problems fast.