Solve a CSP with plain backtracking search and measure its work.
What to build
A program that colours a map with backtracking search.
Requirements
- Regions are coloured in the order listed, each trying the colours in the order listed, skipping colours used by a coloured neighbour. When a region has no colour left, undo the previous region's colour and try its next one.
- Print
REGION COLOURfor each region in order and thenassignments N, orno solutionand thenassignments N, where N counts every colour given to a region.
Input
Line 1: the regions. Line 2: the colours. Line 3: b. Then b lines X Y (borders).
Output
The colouring and the count, or no solution and the count.
Constraints
At most 12 regions and 4 colours.
Example
Input:
A B C D
red green blue
5
A B
B C
C D
D A
A C
Output:
A red
B green
C blue
D green
assignments 4
Why it works
Checking each colour against the neighbours already coloured abandons a partial colouring the moment it breaks a rule, and backing up tries the alternatives in order.
Examples
A B C D red green blue 5 A B B C C D D A A C
A red B green C blue D green assignments 4
A B C red green 3 A B B C A C
no solution assignments 4
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Assign the regions in the order given; for each, try the colours in the order given and skip any used by an already coloured neighbour.
Hint 2
Count an assignment every time a region receives a colour, including ones later undone.
Solution
Show one correct solution (try it yourself first)
regions = input().split()
colours = input().split()
neighbours = {r: set() for r in regions}
for _ in range(int(input())):
x, y = input().split()
neighbours[x].add(y)
neighbours[y].add(x)
assignment = {}
count = 0
def solve(index):
global count
if index == len(regions):
return True
region = regions[index]
for colour in colours:
if all(assignment.get(n) != colour for n in neighbours[region]):
assignment[region] = colour
count += 1
if solve(index + 1):
return True
del assignment[region]
return False
if solve(0):
for region in regions:
print(region, assignment[region])
else:
print("no solution")
print("assignments", count)