Assembing a number line

Arrange the numbers 1-17 so that adjacent numbers sum to a perfect square.

Apparently, Matt Parker (@standupmaths) tweeted this, then Megan Schmidt followed up with a report of giving the problem to her remedial high schoolers; then Dan Meyer kicked that into my feed reader, and I had to go take a look.

After picking up my notebook and working through it, I asked myself the obvious question: why 17?  And of course it has the obvious answer -- because 18 doesn't work.

Then I looked at my solution again, and discovered that 14 doesn't work either.  In fact, it seems that 15 is the first number that has a solution.

So I did the obvious thing: I shared it with the guys at work.  The boss has an interview question of the flavor "show me how you would solve..."  and so we attacked it with that idea in mind.  After confusing ourselves on the whiteboard for a bit, we began to understand that numbers of the form 2n² are a problem, because they can't pair with themselves to produce (2n)²...

It's "just" a problem of finding a Hamiltonian path through a graph where each number is uniquely represented by a node, and edges exist only if the two connected nodes sum to a perfect square.  You don't add very many edges when you add a new node to the graph, so brute forcing it in code shouldn't be too difficult.

But where's the fun in that?