Circle of squares [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incompl开发者_JAVA技巧ete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 10 years ago.

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?

---

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.

---

[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.

---

The answer is NO If you look backward from 16->1, 16 need 2 adjacent number satisfied that the sum is perfect square. But we can only find 16+9=25, and no more. (because the next one is 16 or 36, which are both impossible). But, if the problem change to a linear instead of circle, then there will be a solution： 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16 And this is the only possible solution.

Here I attached my code to solve the linear version:

import java.util.Arrays;

public class PerfectSquareLinear {
    public static final int MAX_NUMBER = 16;
    public static int[] square = { 1, 4, 9, 16, 25 };

    public static void main(String args[]) {
        new PerfectSquareLinear().go();
    }

    public boolean sumIsPerfectSquare(int a, int b) {
        return Arrays.binarySearch(square, a + b) < 0 ? false : true;
    }

    /**
     * 
     * @param l
     *            current result array
     * @param p
     *            position to fill in
     * @param pool
     *            available numbers
     */
    public void fill(int[] l, int p, int[] pool) {

        if (p > MAX_NUMBER - 1) {
            System.out.println(Arrays.toString(l));
        } else {
            for (int i = 0; i < MAX_NUMBER; i++) {
                if (pool[i] > 0) {
                    l[p] = pool[i];
                    if (p == 0 || sumIsPerfectSquare(l[p], l[p - 1])) {
                        pool[i] = -1;
                        fill(l, p + 1, pool);
                        pool[i] = i + 1;
                    } else {
                        // System.out.println("dead end: " +
                        // Arrays.toString(l));
                    }
                }
            }
        }
    }

    public void go() {
        // the result array for compute the permutation
        int[] list = new int[MAX_NUMBER];
        // the pool array to store the available number
        int[] pool = new int[MAX_NUMBER];
        // initial pool array
        for (int n = 1; n <= MAX_NUMBER; n++) {
            pool[n - 1] = n;
        }
        fill(list, 0, pool);
    }
}

---

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);

    }

}

---

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.