Permutation Reconstruction from Differences

We prove that the problem of reconstructing a permutation ${\pi }_1,\dots ,{\pi }_n$ of the integers $[1\dots n]$ given the absolute differences $\mathrm{\mid }{\pi }_{i+1}-{\pi }_i\mathrm{\mid }$, $i=1,\dots ,n-1$ is NP-complete. As an intermediate step we first prove the NP-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.