This problem was proposed by me (Dorlir Ahmeti, Albania)

If $n$ works, then so does $n+1$, as one can just do any permutation which fixes $n+1$, then swap $n+1$ with a suitable number less than or equal to $n$ to get $n+1$ in the desired position and then again, if necessary, do any desired permutation which fixes $n+1$. So one just needs to guess the smallest working $n$ (or show there is no such, if the problem question is trolling).

I noticed that $n=14$ works. Sequences $a = (8, 1, 3, 6, 10)$ and $b = (9, 7, 2, 14, 11, 5, 4, 12, 13, 3)$ has adjacent sum square. Also, $3, 13$ contains $a$ and $b$, respectively. Also, $n=13$ doesn't work since $2, 7, 9$ cannot be paired any other numbers.

Assassino9931 wrote: ... and then again, if necessary, do any desired permutation which fixes $n+1$. Sure, something like that could work. But, I don't understand how you can do any desired permutation which fixes $n+1$. I mean, if you remove $n+1$ (it just stays still) then the connectivity of the rest may be broken. I mean that it's possible that to do some desired permutation you must touch $n+1$ again. So, suppose you had a graph - two numbers are connected if they sum up to a perfect square. One must prove that 1) if this graph is connected then any permutation can be achieved. 2) If $G_n$ is connected then $G_{n+1}$ is also connected. 3) Give an example of a graph $G_n$ which is connected but $G_{n-1}$ is not.

Let $G_n$ be the graph on the vertices $1,2,\dots,n$ such that $i$ is connected to $j$ only if $i+j$ is a perfect square. It's not difficult to see that if $G_n$ is connected for some sufficiently large $n$ then $G_m$ is connected for all $m>n$. We nect prove that if $G_n$ is connected then we can obtain every permutation of $\{1,2,\dots,n\}$. It's enough to prove that we can swap $i$ and $j$ for any two $i,j$ leaving all the other integer on its place. Let $i u_1 u_2\dots u_k j$ be a path. We prove by induction on the length $k+1$ that we can swap $i$ and $j$. It's true for $k=1$. So let it holds for some $k-1$ and we have a path $i u_1u_2\dots u_k j$. So, we swap $i$ and $u_k$ obtaining $u_ku_1 u_2\dots u_{k-1}ij$ and then consecutively: $j u_1\dots u_{k-1}i u_k$ ; $j i u_2\dots u_{k-1}u_1 u_k$ ; $ju_ku_2\dots u_{k-1}u_1 i$ ; $ju_1\dots u_ki$. It remains to find the first $n$ for which $G_n$ is connected and it can be checked that it is $n=14$.

dgrozev wrote: Assassino9931 wrote: ... and then again, if necessary, do any desired permutation which fixes $n+1$. Sure, something like that could work. But, I don't understand how you can do any desired permutation which fixes $n+1$. If you can do any permutation with $1,2,\ldots,n$ (which is the same thing as assuming that $n$ works), then there should be no problem to do the following: if at the moment you are $\sigma_1 \sigma_2 \ldots \sigma_k (n+1) \sigma_{k+1} \ldots \sigma_n$, then you can reach any other permutation in which $n+1$ is still in the $(k+1)$-st position, by just not touching $n+1$ at all? So in my idea is, when one starts from $(1,2,\ldots,n,n+1)$, is to use $n+1$ in exactly one swap (or none, if we want $n+1$ to be in the last position) in order to reach the desired permutation.

Assassino9931 wrote: ... there should be no problem to do the following: if at the moment you are $\sigma_1 \sigma_2 \ldots \sigma_k (n+1) \sigma_{k+1} \ldots \sigma_n$, then you can reach any other permutation in which $n+1$ is still in the $(k+1)$-st position, by just not touching $n+1$ at all... This is true in case the graph $G_n$ is still connected if you remove $n+1$. In this particular case it indeed holds. In the general, when you have just a connected graph, it's false.

The answer is all $n\ge 14$. Take the graph $\mathcal{G}_n$ on $[n]$ and $i\neq j$ have an edge if and only if their sum is a perfect square and call $n$ to be good if it satisfies the problem statement, with the stronger condition that from any permutation we get any other permutation. Now if $n$ is good clearly $\mathcal{G}_n$ is connected. Claim: $n\ge 14$ Suppose by contradiction that $n\le 13$ and look at the number $2$.His neighbours in his connected component are $7$ and $9$ (with the edges 2-7-9).But $1$ is not in this component so the graph is not conex,contradiction. Claim: if $n$ is good then $n+1$ is good Proof: The main idea is that $\mathcal{G}_{n+1}- \{n+1\}=\mathcal{G}_n$.Since $\mathcal{G}_n$ is coonected and $\deg(n+1)\ge 1$ we have $\mathcal{G}_{n+1}$ is connected. Now suppose we want to get from $\sigma$ to $\tau$.We first move $n+1$ where he must go in $\tau$ and we can do that sin $\mathcal{G}_{n+1}$ is connected.Now ignore $n+1$ and do the rest on $[n]$ and we can do that since $n$ is good $\blacksquare$ So we must find the minimum n which is good. Let's look at $n=14$.The graph looks something like this : $1-3-13-12-4-5-11-14-2-7-9$ $-3-6-10$ $-8$ $ n=14$ is good because we take care of the leafs and eliminate them because the graph remains connected and the remaning paths don't use them. So the process is somethong like this: Move $9$ where he must go to and eliminate him,same thing with $7,2,14,11,5,4,12,13$(in this order) and after this do the same thing with 10 and 6.Now you must swap the tuple $(1,3,8)$ and you have $6$ cases and all of them are trivial(or you can continue eliminate leafs). Anyway $n=14$ is good and the problem is solved. $\blacksquare$

Found this very straightforward but still quite interesting. It turns out that the answer is all $n\geq 14$. We call a pair of integers $a$ and $b$ linked if $a+b$ is a perfect square. We look at this in terms of a graph. Let $\mathcal{G}$ be a graph with vertices labelled $1$ to $n$, with an edge between two vertices $a$ and $b$ if and only if $a$ and $b$ are linked. Now, we start by proving the following key claim. Claim : If two vertices $i$ and $j$ are connected (there exists some path with these two vertices as its endpoints) then we can obtain a new permutation of $\{1,2,\dots , n\}$ by swapping only the positions of $i$ and $j$. Proof : Consider two vertices $a_1$ and $a_k$ connected by the path $a_1-a_2-\dots - a_k$. Then, we consider the reduced $k$-tuple $(a_1,a_2,\dots , a_k)$ and give permutations of it. Here, all integers from $1$ to $n$ not in this tuple, retain their positions in the $(1,2,\dots , n)$ tuple. We give an algorithm which reverses the given $k-$tuple. Note that since $a_1$ and $a_2$ are linked we can swap them, to obtain the tuple \[(a_2,a_1,a_3,\dots, a_k)\]Likewise, we do the steps, \[(a_2,a_1,a_3,\dots, a_k) \rightarrow (a_3,a_1,a_2,a_4, \dots, a_k)\rightarrow \dots \rightarrow (a_n,a_1,a_2,\dots, a_{k-1}) \rightarrow (a_n , a_2, a_1, a_3, \dots , a_{k-1}) \rightarrow \dots \rightarrow (a_k, a_{k-1},a_1,\dots, a_{k-2}) \rightarrow \dots \rightarrow (a_k,a_{k-1},\dots, a_2,a_1)\]which indeed reverses the given $k$-tuple as desired. Now, by repeating the same algorithm on the path $a_{k-1} - a_{k-2} - \dots - a_2$ we can reverse this $k-2-$subtuple, which swaps $a_n$ and $a_1$ only as we wished. Now, with this claim, it is actually necessary and sufficient to see for which $n$ the graph $\mathcal{G}$ is connected, since any permuation can be obtained if every pair of vertices is connected by some path (since we can swap them and only them by the given algorithm). It is also easy to see the following result. Claim : If the graph $\mathcal{G}$ is connected for some $n_0>9$ then it is connected for all $n>n_0$ as well. Proof : Say $x^2 \leq n < (x+1)^2$ for some $x\geq 3$. Then, \[(x+1)^2 - (n+1) \leq (x+1)^2 - (x^2+1)=2x < x^2 \leq n\]for all $x\geq 3$. So, $(x+1)^2-(n+1)<n$, which implies that $n+1$ is indeed linked to some number $1\leq a<n$ which implies that the graph $\mathcal{G}$ is connected for $n+1$ as well. Now, it is easy to see that $\mathcal{G}$ is connected when $n=14$ since the following chains of integers are linked. \[1-8 \text{ and } 1-3-6-10\]and \[1-3-13-12-4-5-11-14-2-7-9\]Thus, all $n\geq 14$ indeed work as claimed. Now, if $n>2$, the number $2$ must be linked to some integer if $\mathcal{G}$ is connected. The smallest such integer is $9-2=7$, so $n\geq 7$. Further, $7$ must be connected to something besides $2$ or vice versa. Thus, $n$ must be atleast one of $16-2=14$ or $16-7=9$. Thus, $n\geq 9$. Now, $9$ must also be connected to something besides $7$ and etc. So, $n\geq 16-2=14$, or $n\geq 25-9=16$ or $n\geq 25-7=18$ either way $n\geq 14$ as desired. Thus, we are done.