Question: Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square

Solution: Solution must end or begin with 16 since there is only one number in the rest of the list that sums to a perfect square with 16 so it can't be between two of the other numbers.

So you can start with 16 in one list of numbers and the remaining numbers 1-15 in another list and solve it recursively. The following code works and comes up with the solution

16 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8


import java.util.Arrays;
import java.util.LinkedList;



class SolutionFinder
{
public static void find(final LinkedList remaining, final LinkedList found)
{
if (remaining.size() == 0) // We made it through the whole list, this is a solution
{
for (final Integer curr : found)
{
System.out.printf("%d ", curr);
}
}
else
{
for (int i = 0; i < remaining.size(); i++)
{
final Integer next = remaining.get(i);
if (Arrays.asList(4, 9, 16, 25).contains(found.get(found.size() - 1) + next))
{
found.add(remaining.remove(i));
find(remaining, found);
remaining.add(i, found.remove(found.size() - 1));
}
}
}
}


public static void main(final String[] args)
{
final LinkedList remaining = new LinkedList();
final LinkedList found = new LinkedList();
for (int i = 1; i <= 15; i++)
{
remaining.add(i);
}
found.add(16);
find(remaining, found);
}
}