# Identify this type of graph puzzle

There are $$V-1$$ pieces, each with an identifying symbol. The board is a graph with $$V$$ vertices and some number of edges $$E$$. The idea is to move around the pieces so that each piece's symbol matches the underlying vertex's symbol. You can only move a piece if it is connected to the empty vertex by an edge. One of the vertices is blank (no symbol) since there is one more vertex than pieces. Is there a name for this type of puzzle?

Since you put the question into a graph theory context, the most appropriate name for these games might be "(Labeled) Pebble Motion Problems", those being the generalisation of the 15 puzzle onto arbitrary graph and piece configurations.

• Thank you as well! That is a very specific name and I am happy to see a Wikipedia article about it. Thus I am making this the accepted answer. – Mixolydian Feb 7 '19 at 17:01
• @Bass neat, I didn't know that these had a "name"! Good to know. – user46002 Feb 7 '19 at 18:04

That game specifically being the Nancy Drew game Labyrinth Of Lies. In the game, a slightly different version is used, with $$V - 3$$ tokens instead of $$V - 1$$ — but I believe that my answer should still hold. In many of the 'walkthroughs' of this game, the puzzle is referred to as "The Token Puzzle" or "The Sliding Token Puzzle".