Somados somos um quadrado perfeito!

A relação binária "somados somos um quadrado perfeito" no universo dos inteiros {1, 2, ..., 25} é muito interessante, por o grafo correspondente ter um único componente conexo e admitir caminhos Hamiltonianos, caminhos que visitam cada um dos nós do grafo exactamente uma vez.
Uma das minhas ferramentas favoritas, NodeXL, permite investigar estes factos muito facilmente.
Ja vimos algures que apenas 32 pares neste universo satisfazem a relação, que podem ser visualizados assim

evidenciando um dos tais caminhos Hamiltonianos, que percorre 24 dos 32 lados do grafo.
E quantos caminhos  Hamiltonianos haverá? Uma coisa é certa: o número 18 tem de estar num dos extremos, pois é o único nó do grafo com grau 1. E a seguir ao 7, temos de ir pelo 9, ou podemos ir pelo 2? Bem, não é fácil responder.É a vez da Informática... Fica o desafio.