Square Sums Chain

Description
For this challenge your task is, given a number N, rearrange the numbers 1 to N so that all adjacent pairs of numbers sum up to square numbers.

There might not actually be a solution. There also might be multiple solution. You are only required to find one, if possible.

For example, the smallest number for which this is possbile is 15:

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

 8 +  1 =  9 = 3^2
 1 + 15 = 16 = 4^2
15 + 10 = 25 = 5^2
10 +  6 = 16 = 4^2
...
Example Input
15
8
Example Output
8 1 15 10 6 3 13 12 4 5 11 14 2 7 9
Not possible
Challenge Input
23
24
25
256

Solution
in C

#include <stdio.h>
#include <limits.h>

#define MAX 1024
#define ULONG_BIT (sizeof(unsigned long) * CHAR_BIT)

#define BITSET(b, i) b[i / ULONG_BIT] |= 1UL << (i % ULONG_BIT)
#define BITGET(b, i) ((b[i / ULONG_BIT] >> (i % ULONG_BIT)) & 1UL)

static unsigned long is_square[(MAX * (MAX - 1) + ULONG_BIT - 1) / ULONG_BIT];

static inline void
swap(short *a, short *b)
{
    short c = *a;
    *a = *b;
    *b = c;
}

static int
solve(short *values, int n, int i)
{
    if (i == n) {
        /* Solution found */
        for (int j = 0; j < n; j++)
            printf("%d ", values[j]);
        putchar('\n');
        return 1;
    }

    for (int j = i; j < n; j++) {
        swap(values + i, values + j);
        int valid = 1;
        if (i > 0) {
            int sum = values[i] + values[i - 1];
            valid = BITGET(is_square, sum);
        }
        int success = valid && solve(values, n, i + 1);
        swap(values + j, values + i);
        if (success)
            return 1;
    }

    return 0;
}

int
main(void)
{
    /* Fill out bit array of squares */
    for (int i = 1; i * i <= MAX * (MAX - 1); i++)
        BITSET(is_square, i * i);

    int n;
    while (scanf("%d", &n) == 1) {
        short values[MAX];
        for (int i = 0; i < n; i++)
            values[i] = i + 1;
        if (!solve(values, n, 0))
            puts("Not possible");
    }
}