For all $1\leq i\leq n$, let $i^4 + \tau(i)^4 = p_i$, for primes $p_i$. Then, note that $$p_1 + p_2 + \cdots + p_n = 1^4 + 2^4 + \cdots + n^4 + (\tau(1)^4 + \tau(2)^4 + \cdots + \tau(n^4)) = 2(1^4+2^4+\cdots + n^4).$$ Now, suppose that $n$ was even. Then, $p_1+p_2+\cdots + p_n$ must be even. Note that for $i\geq 2$, $p_i > i^4 > 2$, so $p_i$ is odd for all $i\geq 2$. Thus, $p_1 + (n-1)$ must be even, so $p_1 - 1$ must be even, so $p_1$ is odd. Thus, $\tau(1) \neq 1$. Now, consider a graph and connect $1\leq i \neq j\leq n$ iff $i^4+j^4$ is prime. Note that if $i = j$, then $2i^4$ is only prime if $i = 1$, but we know that $\tau(1) \neq 1$ anyways, so we need not worry about that case. Then, if $i$ and $j$ are of the same parity, then $i^4+j^4$ is even, and greater than $2$ since $i\neq j$. Thus, this graph is bipartite, since we can take the bipartitions $A = \{1, 3, \cdots, n-1\}$ and $B = \{2, 4, \cdots, n\}$ and no two elements of $A$ are connected and no two elements of $B$ are connected. Now, to find $\tau$ for all odds, we need to find a perfect matching from $A$ to $B$, since we want to find $a_1, a_3, \cdots, a_{n-1}$ -- a permutation of $B$ such that $i^4 + a_i^4$ is prime for all odd $1\leq i\leq n-1$. To find $\tau$ for all evens, we need to find a perfect matching from $B$ to $A$, since we want to find $a_2, a_4, \cdots, a_n$ -- a permutation of $A$ such that $i^4 + a_i^4$ is prime for all even $2\leq i\leq n$. Thus, the number of ways to find $\tau$ for all evens is $P$, the number of perfect matchings from $A$ to $B$, and the number of ways to find $\tau$ for all evens is the number of perfect matchings from $B$ to $A$, which is also $P$. Thus, the number of such permutations $\tau$ is $P^2$, which is a perfect square, and all such permutations work since they work for all odds and all evens (and they are indeed permutations of $\{1, 2, \cdots, n\}$), so we are done in the case that $n$ is even. If $n$ is odd, then $p_1 + p_2 + \cdots + p_n$ is even as well, and for $i\geq 2$, $p_i > i^4 > 2$, so $p_i$ is odd for all $i\geq 2$. Thus, $p_1 + (n-1)$ must be even, so $p_1$ itself must be even, so $p_1 = 2$, implying $\tau(1) = 1$. Thus, it is equivalent to find all permutations $\tau$ of $\{2, 3, \cdots, n\}$ for which $i^4 + \tau(i)^4$ is prime for all $2\leq i\leq n$, since we have already handled $i = 1$, and nothing besides $1$ can map to $1$ and $1$ can map to nothing besides $1$. To do this, do pretty much the exact same thing -- connect $2\leq i \neq j\leq n$ if $i^4 + j^4$ is prime -- if $i = j$ then clearly $2i^4$ is not prime since $i\geq 2$. If $i$ and $j$ are of the same parity, then $i^4 + j^4$ is even, and greater than $2$ since $i\neq j$, so this graph is bipartite since we can take the bipartitions $A = \{3, 5, \cdots, n\}$ and $B = \{2, 4, \cdots, n-1\}$, and so by the same logic in the $n$ even case, the number of ways to find such a $\tau$ is just the square of the number of perfect matchings from $A$ to $B$, which is a perfect square. Thus, in all cases, $S(n)$ is a perfect square, as desired. $\blacksquare$