In the 2022 AMC 10A competition, Problem #9 presents a classic map coloring challenge on a partitioned rectangle:



Contest Problem Statement:
"A rectangle is partitioned into 5 regions as shown. Each region is to be painted a solid color—red, orange, yellow, blue, or green—so that regions that touch are painted different colors, and colors can be used more than once. How many different colorings are possible?"

Analyzing the Adjacency Constraints

Two regions "touch" if they share an edge (a boundary line segment). Merely touching at a single corner point does not count. Looking at the diagram:

• T1 (Top Left) touches: T2, B1, and B2.
• T2 (Top Right) touches: T1, B2, and B3.
• B1 (Bottom Left) touches: T1 and B2.
• B2 (Bottom Middle) spans the center division and touches all other four regions: B1, T1, T2, and B3!
• B3 (Bottom Right) touches: B2 and T2.

The Declarative Prolog Solution

In procedural languages (like C or Java), you would write nested for loops and nested if conditions. In Prolog, you simply declare what makes a coloring valid:

1. Pick a color for each region from the 5 available colors.
2. Ensure every pair of touching regions receives different colors (using \=).
3. Use findall/3 to collect all valid combinations and count them!

Move the mouse over a dotted box for more information.

By evaluating all combinations that satisfy these constraints, Prolog's backtracking search discovers exactly 540 valid colorings without any manual algebraic casework!