Complexity Thresholds for the Constrained Colored Token Swapping Problem

Davide Bilò, Stefano Leucci, Andrea Martinelli

Consider the following puzzle: a farmland consists of several fields, each occupied by either a farmer, a fox, a chicken, or a caterpillar. Creatures in neighboring fields can swap…