A permutation is square chained if the sum of consecutive numbers is always a perfect square. For example,
8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16
is a squared chain permutation of the numbers 1 to 16. I want to write a program to find a square chained permutation of the numbers 1 to n, for n from 1 to 100.
The simplest thing to do is to go lexicographically through all the permutations of n (I know how to write that) and check the square chained condition, but that will take ages for n big.
A slightly better way is to pick the numbers in my permutation one at a time, check to make sure the number I just picked makes a square when added to the previous number, and hope I make it to the end. I'll have to back up a lot, though, and I don't think it will be very efficient.
Is there a better way? Also, is this a well-known problem? Thanks for your help.