Heuristics for Hamiltonian path

Правка en1, от fpc_coder, 2021-08-19 19:17:12

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский fpc_coder 2021-08-19 19:17:12 623 Initial revision (published)