Circle of squares

Question

Can you arrange numbers 1 to 16 in a circle such that the sum of adjacent two numbers is a perfect square? If yes, how and if not, why not? Can you write a program to solve this problem?

Answer 1

Hint for you. Using this set of numbers, there is only one possible sum which includes 16 that makes a perfect square (16+9 = 25), so the answer is no.

Answer 2

[1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16]

And yes, I can write a program to solve it.

EDIT: Just realised this isn't a circle ... this is the only linear solution, so my answer is:

No, not possible.

Answer 3

This might be wrong, but I can't seem to find possible cycles with this code:

/**
 * @author BjørnS
 * @created 30. aug. 2010
 */
public class PerfectSquares {

    /**
     * @param args
     */
    public static void main(String[] args) {

        List<Integer> options = Lists.newArrayList();

        for (int i = 1; i <= 16; i++) {
            options.add(i);
        }

        List<Integer> start = start(options);

        if (start == null) {
            System.out.println("Unsolvable unless this code is wrong.");
        } else {
            System.out.println("My answer is: " + start);
        }

    }

    private static List<Integer> start(List<Integer> options) {

        for (Integer i : options) {

            List<Integer> li = Lists.newArrayList(options);
            li.remove(i);

            List<Integer> ws = Lists.newArrayList(i);

            List<Integer> answer = findAnswer(ws, li);
            if (answer != null) {
                return answer;
            }
            ws = null;
            li = null;
        }

        return null;

    }

    private static List<Integer> findAnswer(List<Integer> workingSet, List<Integer> options) {

        Integer last = workingSet.get(workingSet.size() - 1);

        if (options.size() == 1) {

            Integer first = workingSet.get(0);

            Integer option = options.get(0);

            if (isPerfectSquare(first, option) && isPerfectSquare(last, option)) {
                workingSet.add(option);
                System.out.println("I think it is:" + workingSet);
                return workingSet;
            }
            return null;
        }

        for (Integer i : options) {

            if (isPerfectSquare(last, i)) {

                List<Integer> li = Lists.newArrayList(options);
                li.remove(i);

                List<Integer> ws = Lists.newArrayList(workingSet);
                ws.add(i);

                System.out.println("trying " + ws);

                List<Integer> answer = findAnswer(ws, li);
                if (answer != null) {
                    System.out.println("Potential answer:" + answer);
                    return ws;
                }

                li = null;
                ws = null;

            }

        }

        return null;
    }

    private static boolean isPerfectSquare(Integer a, Integer b) {

        return Math.pow(Math.floor(Math.sqrt(a + b)), 2) == (a + b);

    }

}

Answer 4

If you consider the graph with vertices 1, 2, ..., 16, and edges (a, b) if a + b is square, then the problem is the equivalent to finding a hamiltonian path on this graph.

Finding hamiltonian paths is in general NP, which suggests you're not going to do better than a search.