El problema de la suma cuadrada

Elige un número entero N. Dados todos los números enteros de 1 a N, ¿se pueden ordenar de manera que cada par adyacente sume un número cuadrado? Empecemos con un conjunto pequeño de números no consecutivos, que se pueden ordenar para conseguir el objetivo: $$\{1,3,6,8,10\} \rightarrow \{8,1,3,6,10\}\rightarrow \{9,4,9,16\}=\{3^2,2^2,3^2,4^2\}$$

No hay forma de encontrar una solucíón sin probar todas las opciones. Es un problema de los llamados tipo NP-complejo. La mejor forma de visualizar estas relaciones es mediante un grafo donde los números son los vértices y las aristas conectan dos vértices cuya suma sea un número cuadrado. El problema tiene solución si hay un camino hamiltoniano, es decir, si podemos pasar una sola vez por todos los vértices.

Se observa que se pueden enlazar hasta 17 números, pero que al añadir el número 18 no es posible:

$$\{17,8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,16\}$$

$$\{25,9,16,25,16,9,16,25,16,9,16,25,16,9,16,25\}$$

Se puede ver la construcción 'paso a paso'.

Si añaden los números 19, 20, 21 y 22 sigue sin funcionar, pero si añade el número 23 si se consigue un camino hamiltoniano y por tanto hay una solución:

$$\{18,7,9,16,20,5,11,14,2,23,13,12,4,21,15,10,6,19,17,8,1,3,22\}$$

$$\{25,16,25,36,25,16,25,16,25,36,25,16,25,36,25,16,25,36,25,9,4,25\}$$

Si añadimos el número 24 vuelve a fallar pero desde el número 25 en adelante siempre hay una solución.