Card 08/ 09
Practice: Seating Guests Who Refuse to Sit Together
Four guests in a row, two pairs who must not be neighbours: list the seatings that work.
Counting a backtracking tree and pruning it are two separate skills, and this exercise practises both on one seating problem.
Four guests, Ana, Ben, Cai and Dev, sit in a row of four chairs. Ana and Ben must not sit next to each other, and neither must Cai and Dev.
- A search that seats the guests one chair at a time and checks the rule only once the row is full: how many complete seatings does it build?
- Now prune: before seating a guest, check them against the guest in the chair to their left. How many complete seatings does that search build, and how many of them are valid?
- List the valid seatings.
Show the counts and the seatings
Without pruning the search builds every ordering of four guests, 4! = 24 leaves, and checks each at the end. With pruning it builds only the 8 that are valid, because any seating with a forbidden pair is abandoned when the second of the pair sits down. The listing below runs both searches and prints the valid seatings.
guests = ["Ana", "Ben", "Cai", "Dev"]
apart = {frozenset(("Ana", "Ben")), frozenset(("Cai", "Dev"))}
def search(prune):
path, used = [], [False] * len(guests)
stats = {"placed": 0, "leaves": 0, "valid": []}
def ok(seats):
return all(frozenset(pair) not in apart for pair in zip(seats, seats[1:]))
def go():
if len(path) == len(guests):
stats["leaves"] += 1
if ok(path):
stats["valid"].append(" ".join(path))
return
for i, guest in enumerate(guests):
if used[i]:
continue
if prune and path and frozenset((path[-1], guest)) in apart:
continue
used[i] = True
path.append(guest)
stats["placed"] += 1
go()
path.pop()
used[i] = False
go()
return stats
full, pruned = search(False), search(True)
print(f"without pruning: {full['leaves']} full seatings built, {full['placed']} guests placed, {len(full['valid'])} valid")
print(f"with pruning: {pruned['leaves']} full seatings built, {pruned['placed']} guests placed, {len(pruned['valid'])} valid")
for seating in pruned["valid"]:
print(seating)without pruning: 24 full seatings built, 64 guests placed, 8 valid
with pruning: 8 full seatings built, 28 guests placed, 8 valid
Ana Cai Ben Dev
Ana Dev Ben Cai
Ben Cai Ana Dev
Ben Dev Ana Cai
Cai Ana Dev Ben
Cai Ben Dev Ana
Dev Ana Cai Ben
Dev Ben Cai AnaThe run seated 64 guests in all without pruning and 28 with it; every one of the 24 complete seatings in the first search was built before being checked. The pruning test in line 21 needs only the guest to the left, because every earlier pair was checked when its second guest sat down, so a partial row that has passed every check breaks no rule.
Every valid seating alternates the two pairs, one of Ana and Ben, then one of Cai and Dev, or the other way round. Either pair can take chairs 1 and 3, and each pair can sit in either order, giving 2 × 2 × 2 = 8, which matches the run.
← → move through sections and cards