Arrange number 1..n so that each pair of consecutive numbers sum up to a square number

Problem Statement

Write a program to arrange numbers from 1 to n such that the sum of two consecutive numbers is a perfect square.

An interesting way of looking at this problem

Make a graph so that each node is one of the numbers and there is an edge between two nodes if these two numbers can add up to a square number. Find a path starting from one node and end up in another so that each node is visited once and all nodes are visited. Such path may not exist.

There should be an easier way to do this by seeking for nodes with only one edge in/out...