Three-color map coloring

Treat the map as an undirected graph: each location is a vertex and each adjacency pair is an edge. A valid assignment is a proper 3-coloring. Deciding 3-colorability is NP-complete, so no polynomial algorithm is expected. The interviewer wants a clean backtracking search with good pruning, and wants you to say why it is exponential in the worst case.

Validate and build the graph first. Build an adjacency set per location. If a pair names a location that is not in the list, or a location is adjacent to itself, fail fast. A self-loop can never be colored. Duplicate pairs collapse in the set.

Brute force. Try all 3^n assignments and check every edge. This is correct but useless past about 15 locations.

Backtracking. Color one vertex at a time. Give it only colors that no colored neighbor already uses, recurse, and undo on failure. Two pruning steps make this fast in practice:

1. Most-constrained vertex first (DSATUR order). Always pick next the uncolored vertex whose neighbors already use the most distinct colors. Break ties by uncolored degree. A vertex with 0 legal colors ends the branch at once. A vertex with 1 legal color is forced, so it costs nothing.
2. Components are independent. The search runs over every vertex, but because the next pick is always the most constrained one, it finishes one connected component before it moves on. A failure in one component means the whole map fails. No branching is spent mixing components.

Cheap pre-checks: a vertex with degree <= 2 can always be colored last, so you can peel it off. Any 4-clique, for example 4 mutually adjacent locations, makes the answer impossible.

Symmetry. The three colors are interchangeable. The first vertex of each component can take color 0 without trying the others, which cuts the search by a factor of 3.

Invariants. At every point in the recursion the partial coloring is proper: no edge joins two colored vertices of the same color. used[v] counts, for each color, how many colored neighbors of v hold it. It stays in sync with color because every assign and every undo updates all neighbors.

from typing import Dict, List, Optional, Sequence

COLORS = ("red", "green", "blue")


def color_map(
    locations: Sequence[str],
    adjacencies: Sequence[Sequence[str]],
) -> Optional[Dict[str, str]]:
    """Return a location -> color mapping where adjacent locations differ,
    or None if no 3-coloring exists."""
    index = {name: i for i, name in enumerate(locations)}
    n = len(locations)
    adj: List[set] = [set() for _ in range(n)]
    for pair in adjacencies:
        a, b = pair
        if a not in index or b not in index:
            raise ValueError(f"unknown location in {pair!r}")
        if a == b:
            return None  # a region bordering itself can never be colored
        adj[index[a]].add(index[b])
        adj[index[b]].add(index[a])

    k = len(COLORS)
    color = [-1] * n
    # used[v][c] = number of colored neighbors of v that have color c
    used = [[0] * k for _ in range(n)]

    def assign(v: int, c: int) -> None:
        color[v] = c
        for u in adj[v]:
            used[u][c] += 1

    def unassign(v: int) -> None:
        c = color[v]
        color[v] = -1
        for u in adj[v]:
            used[u][c] -= 1

    def pick() -> int:
        """Uncolored vertex with the most distinct neighbor colors (DSATUR)."""
        best, best_key = -1, (-1, -1)
        for v in range(n):
            if color[v] != -1:
                continue
            saturation = sum(1 for c in range(k) if used[v][c])
            uncolored_degree = sum(1 for u in adj[v] if color[u] == -1)
            key = (saturation, uncolored_degree)
            if key > best_key:
                best, best_key = v, key
        return best

    def solve(remaining: int) -> bool:
        if remaining == 0:
            return True
        v = pick()
        if not any(used[v]):
            # Fresh component (or no colored neighbors): colors are symmetric.
            candidates = [0]
        else:
            candidates = [c for c in range(k) if used[v][c] == 0]
        for c in candidates:
            assign(v, c)
            if solve(remaining - 1):
                return True
            unassign(v)
        return False

    if not solve(n):
        return None
    return {locations[i]: COLORS[color[i]] for i in range(n)}


def is_valid(coloring: Dict[str, str], adjacencies: Sequence[Sequence[str]]) -> bool:
    return all(coloring[a] != coloring[b] for a, b in adjacencies)


if __name__ == "__main__":
    # Triangle: needs all three colors.
    adj = [["A", "B"], ["B", "C"], ["C", "A"]]
    res = color_map(["A", "B", "C"], adj)
    assert res is not None and is_valid(res, adj) and len(set(res.values())) == 3

    # K4: impossible.
    locs = ["A", "B", "C", "D"]
    k4 = [[a, b] for i, a in enumerate(locs) for b in locs[i + 1:]]
    assert color_map(locs, k4) is None

    # Wheel with odd rim (hub + 5-cycle): impossible.
    rim = ["1", "2", "3", "4", "5"]
    wheel = [[rim[i], rim[(i + 1) % 5]] for i in range(5)] + [["H", r] for r in rim]
    assert color_map(["H"] + rim, wheel) is None

    # Wheel with even rim (hub + 4-cycle): possible.
    rim4 = rim[:4]
    wheel4 = [[rim4[i], rim4[(i + 1) % 4]] for i in range(4)] + [["H", r] for r in rim4]
    res = color_map(["H"] + rim4, wheel4)
    assert res is not None and is_valid(res, wheel4)

    # Isolated locations, empty input, self-loop, duplicate edges.
    assert color_map(["X", "Y"], []) == {"X": "red", "Y": "red"}
    assert color_map([], []) == {}
    assert color_map(["A"], [["A", "A"]]) is None
    res = color_map(["A", "B"], [["A", "B"], ["B", "A"], ["A", "B"]])
    assert res is not None and res["A"] != res["B"]

    # Two components, one impossible -> whole map impossible.
    assert color_map(locs + ["E", "F"], k4 + [["E", "F"]]) is None

    # Larger 3-colorable graph: triangular grid strip.
    names = [f"v{i}" for i in range(60)]
    strip = [[names[i], names[i + 1]] for i in range(59)] + \
            [[names[i], names[i + 2]] for i in range(58)]
    res = color_map(names, strip)
    assert res is not None and is_valid(res, strip)
    print("all tests passed")

Let n be the number of locations and m the number of adjacency pairs.

• Building the graph: O(n + m) time and space.
• Search, worst case: O(3^n) branches. 3-coloring is NP-complete, so no algorithm is known to be polynomial. Each step costs O(n + m) here, because pick() scans every vertex and its neighbors. A bucket queue keyed on saturation brings that down to about O(deg) per step. In practice DSATUR ordering forces most choices on map-like (planar, sparse) inputs, and the search barely branches.
• assign / unassign: O(deg(v)).
• Space: O(n + m) for the graph and counters, plus O(n) recursion depth. For very large inputs, change the recursion to an explicit stack.

• locations=["A","B","C"], adjacencies=[["A","B"],["B","C"],["C","A"]] -> a coloring that uses all three colors.
• ["A","B","C","D"], all 6 pairs (K4) -> None.
• Hub H adjacent to every vertex of a 5-cycle (odd wheel) -> None. No 4-clique exists, but the map is still impossible. This catches a "just check for K4" shortcut.
• Hub plus a 4-cycle (even wheel) -> valid coloring. The hub takes one color and the rim alternates between the other two.
• ["X","Y"], no adjacencies -> both locations get some color. Any color is valid.
• [], [] -> {}.
• ["A"], [["A","A"]] -> None (self-adjacent).
• Duplicate and reversed pairs [["A","B"],["B","A"]] -> A and B get different colors.
• K4 plus a separate edge E-F -> None. One impossible component fails the whole map.
• A pair that names an unknown location -> ValueError. Confirm this policy with the interviewer.
• A 60-vertex triangulated strip (i~i+1, i~i+2) -> valid coloring with no backtracking.

1. Some locations are pre-colored. Call assign for each fixed location before the search, and check that no two fixed neighbors clash. Turn off the symmetry shortcut for any component that holds a fixed color, because the colors are no longer interchangeable there.
2. k colors instead of 3. Make COLORS a parameter. For k = 2 the problem is polynomial: BFS 2-coloring, which fails exactly on an odd cycle, in O(n + m). For k >= 4 and a planar map, the four color theorem says a coloring always exists. A greedy pass with the smallest-last order still uses at most 6 colors in linear time.
3. Minimum number of colors (chromatic number). Try k = 1, 2, 3, ... with the same solver, or run DSATUR branch-and-bound that keeps the best k found so far. Give the lower bound from the largest clique you find.
4. Count all valid colorings. Do not stop at the first success. Add up the counts over all branches and multiply the counts of the components together. For a tree, a memoized DP gives 3 * 2^(n-1). For general graphs this is #P-hard, so mention a chromatic polynomial or tree-width DP.
5. Adjacencies arrive in a stream, and you must keep a valid coloring. For each new edge whose ends have the same color, try to recolor one end to a color free among its neighbors. If none is free, rerun the search on that component only, starting from the current coloring. Report impossibility as soon as the component fails.

Mid-level (L4)

• Models the map as a graph and writes correct backtracking that checks neighbors before assigning.
• Handles empty input, isolated locations and duplicate pairs.
• States the exponential worst case.

Senior (L5)

• Adds a most-constrained-first order, and either does each connected component separately or explains why the order already does so.
• Fixes the first color to break symmetry, keeps the neighbor color counters incremental, and catches self-adjacency.
• Knows that 2-coloring is BFS bipartiteness and that 3-coloring is NP-complete, and explains why a K4 check alone is not enough (the odd wheel).

Staff (L6+)

• Talks about complexity limits clearly: why the problem is NP-complete, what is practical for real map sizes, and when to reach for a SAT or CSP solver instead.
• Extends the design to pre-colored regions, incremental edges and counting without rewriting the solver.
• Thinks about the production shape: input validation policy, deep-recursion limits, and an explainable answer when the map fails (for example, return the conflicting subgraph).