Problems made of rules
Timetables, Sudoku, seating plans, register allocation in compilers, scheduling the Hubble telescope: in each one, the question isn't "what's the path?" but "what assignment satisfies all the rules?". These are constraint satisfaction problems (CSPs), and because they share one shape, one solver handles them all.
The textbook example is colouring the map of Australia — seven regions, three colours, neighbours must differ. Today you'll write the solver: backtracking search with a smart choice of which region to colour next.
Variables, domains, constraints
A CSP has variables (the regions), a domain of values each can take (red, green, blue) and constraints (adjacent regions differ). A solution assigns every variable a value from its domain with no constraint broken. Unlike yesterday's search, the path doesn't matter — only the final assignment, and we can check constraints on partial assignments to reject bad choices early.
const AUSTRALIA = {
variables: ["WA", "NT", "SA", "Q", "NSW", "V", "T"],
domains: ["red", "green", "blue"],
neighbours: {
WA: ["NT", "SA"], SA: ["WA", "NT", "Q", "NSW", "V"],
T: [], // Tasmania is an island
// …
},
};The four colour theorem (proved in 1976, with a computer's help) says four colours are always enough for any flat map. Australia needs only three.