I'm trying to solve this task: Codewars — Square sums. The task asks you to find a permutation of $$${1, 2, \ldots, n}$$$ such that the sum of two adjacent elements is a perfect square. The constraint is $$$n\leq 1000$$$. My idea is to construct a graph where $$$i$$$ is connected to $$$j$$$ if $$$i+j$$$ is perfect square, then find a Hamiltonian path on this graph. However, backtrack to find Hamiltonian path is impossible because of large constraint. Anyone have idea on a heuristic to find Hamiltonian path on a graph that can be applied to this problem?