卵石運動問題，或圖上的卵石運動，是圖論中的一組相關問題，涉及多個物體（卵石）在圖中從頂點到頂點的運動，對任何時候能占據一個頂點的卵石數量有約束。卵石運動問題出現在多機器人運動規劃（其中卵石是機器人）和網絡路由（其中卵石是數據包）等領域。卵石運動問題最有名的例子是著名的15謎題，其中一組無序的15塊瓷磚必須通過每次滑動一塊瓷磚在4x4網格內重新排列。

卵石運動問題的一般形式是圖上卵石運動，表述如下。{displaystyleP={1,ldots,k}是一個卵石集合，其中有許多卵石。｝是一個卵石集，其中{displaystyleu}轉移到相鄰的未被占用的頂點到相鄰的未被占用的頂點.圖上的卵石運動問題是決定，給定兩個安排{displaystyleS_{+}}，是否有一連串的舉動能將其轉換為一個新的模式？

該問題的常見變化限制了圖的結構。另一組變體考慮了部分或全部卵石未被標記且可互換的情況。該問題的其他版本不僅要證明可達性，而且要找到一個（潛在的最佳）移動序列（即一個計劃），以執行轉換。

在圖上的卵石運動問題中尋找最短路徑（有標記的卵石），已知是NP-hard和APX-hard。當使用上面提到的成本指標（最小化到相鄰頂點的移動總數）時，無標簽的問題可以在多項式時間內解決，但對于其他自然成本指標來說是NP-hard。