I recently saw a problem from Numberphile here, where the goal is to arrange the numbers $1,\ldots,n$ so that the sum of adjacent numbers is a perfect square. This question from Mathematics Stack Exchange has a good analysis of the generalization of the problem for arbitrary powers, but I have been unable to find an analysis of the complexity class of the decision version of the problem. It is $NP$ since you can check if an arrangement satisfies the square sum condition efficiently, but I have been unable to come up with a better algorithm than creating the associated graph and solving the Hamiltonian path problem.
So my question is if this problem is $NP$-complete or if there is a polynomial time algorithm that can decide if $1,\ldots,n$ can be arranged to satisfy the square-sum condition.
Arranging the integers means to find a permutation $a_1, \ldots, a_n$ of $1,\ldots, n$ with the property that for all $1 < i < n$, $a_i + a_{i+1}$ and $a_i + a_{i-1}$ are perfect squares.