Write the constraint checker that every CSP solver relies on.
What to build
A program that checks whether a colouring of a map breaks any border constraint.
Requirements
- Each border joins two regions that must have different colours.
- Print
conflict: X and Y are both COLOURfor each border whose two regions share a colour, in the order given, orvalidif there are none.
Input
Line 1: b. Then b lines X Y. Last line: the colouring, as REGION=COLOUR items separated by spaces.
Output
The conflicts, or valid.
Constraints
b ≤ 200; every region on a border is coloured.
Example
Input:
3
A B
B C
A C
A=red B=green C=red
Output:
conflict: A and C are both red
Why it works
A solution must satisfy every constraint, so checking each border once tells you whether the colouring is a solution.
Examples
Example 1 · Input
3 A B B C A C A=red B=green C=red
Expected output
conflict: A and C are both red
Example 2 · Input
3 A B B C A C A=red B=green C=blue
Expected output
valid
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Store the colours in a dictionary, then look at every border once.
Hint 2
Report the borders in the order they are given.
Solution
Show one correct solution (try it yourself first)
borders = [input().split() for _ in range(int(input()))]
colour = dict(item.split("=") for item in input().split())
conflicts = [f"conflict: {x} and {y} are both {colour[x]}" for x, y in borders if colour[x] == colour[y]]
print("\n".join(conflicts) if conflicts else "valid")