Token Reconfiguration

The token reconfiguration problem is a reconfiguration problem defined on a graph, in which indistinguishable tokens placed on some of the graph's vertices must be moved from a given initial configuration to a desired one, with each move sliding a token along an edge to a vertex not currently holding another token. The goal is to reach the desired configuration using as few moves as possible; because the tokens are indistinguishable, unlike the numbered tiles of a sliding puzzle, a solution always exists on any connected graph, and the problem is studied within computational complexity theory and combinatorics. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/