AI: Colour a map by backtracking

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 COLOUR for each region in order and then assignments N, or no solution and then assignments 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

Example 1 · Input
A B C D
red green blue
5
A B
B C
C D
D A
A C
Expected output
A red
B green
C blue
D green
assignments 4
Example 2 · Input
A B C
red green
3
A B
B C
A C
Expected output
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)

Lesson: Constraint satisfaction problems →