Here's a solution sketch; the main idea is the notion of the parity of a permutation. We'll prove the configurations that can be attained from a returning sequence are exactly those that correspond to even permutations. A little fiddling around reveals we can cycle any 3 counters that make an L-shape and leave the rest untouched, from which it's not too difficult to show, by performing three well-chosen 3-cycles, that we can cycle any 3 counters without disturbing the others. An operation that will be particularly useful is, given two pairs of counters, swapping both pairs (which can be reached from two appropriately chosen 3-cycles on the four counters). Consider an arbitrary even permutation and write it as the product of transpositions: $\sigma_1\sigma_2 \dots \sigma_{2k}$. If $\sigma_{2k - 1}$ and $\sigma_{2k}$ don't intersect, they correspond to a double transposition, an operation we are capable of doing. If instead they do, they are either the same or have exactly one term in common. If they're the same, we can remove both of them (since all transpositions are their own inverses) without affecting the parity of the permutation. If they share exactly one term, $\sigma_{2k - 1}\sigma_{2k}$ is in fact a 3-cycle, another operation we can do. By applying these steps successively, any even permutation can be reached. This resolves the first part of the problem; we can choose to include or exclude the transposition between the cells that house the two indistinguishable counters at the end of the sequence in order to guarantee the permutation has even parity yet remains indistinguishable. It remains to show no odd permutations can be reached. First set up a coordinate grid in which the counters occupy $([n] - 1)^2$. Notice that the sum of the $x$ and $y$ coordinates of all squares with a counter on them changes by $\pm n$ each move and does not change from start to finish; it follows that the returning sequence has even length. Next, color the squares of the grid in $n^2$ colors $c_1, c_2, \dots, c_{n^2}$, where each color represents one of the $n^2$ possible $(x, y)$ combinations (both modulo $n$). It's easy to see that after any sequence of moves, exactly one square with color $c_i$ has a counter on it for all $i$. Furthermore, each move is an $n$-cycle on which counters are on which colors. An even number of $n$-cycles give an even permutation; since only even permutations on colors can be reached, and the final configuration in a returning sequence is its own color permutation, returning sequences only exist for even permutations.

This is a play on Sam Lloyd's puzzle "RATE YOUR MIND PAL" (also known as the $15$ puzzle), discussed by Martin Gardner.

Part (b) is good motivation for (a), so we do that first. We claim that we can only obtain even permutations. The proof takes two observations: On the one hand, consider $\sum (x+y)$ across all counters at each step of the operation. It increases by $+n$ or $-n$ at every step. So any returning sequence must have an even number of operations. On the other hand, at any time, we can consider the counter labeling as a permutation on $({\mathbb Z}/n{\mathbb Z})^2$ (at any point, for any ordered pair of residues, exactly one counter occupies that residue). Then each operation is an $n$-cycle. Hence, a returning sequence is a composition of an even number of $n$-cycles; consequently, it follows that each permutation is obtained has even parity. Therefore, it's impossible to achieve (b). On the other hand, towards (a), we show any even permutation is achievable. Claim: We can permute any ``right triangle,'' i.e. \[ \begin{bmatrix} \ddots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\ \vdots & A & B & \vdots \\ \vdots & C & \bullet & \vdots \\ {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \ddots \end{bmatrix} \longrightarrow \begin{bmatrix} \ddots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\ \vdots & B & C & \vdots \\ \vdots & A & \bullet & \vdots \\ {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \ddots \end{bmatrix} \qquad (1) \]Proof. Push the row with $A$ and $B$ left, push the column with $C$ and $A$ up, push the same row right, push the same column down. $\blacksquare$ By composing these, we also get that \[ \begin{bmatrix} \ddots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\ \vdots & A & B & \vdots \\ \vdots & C & D & \vdots \\ {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \ddots \end{bmatrix} \longrightarrow \begin{bmatrix} \ddots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\ \vdots & B & A & \vdots \\ \vdots & D & C & \vdots \\ {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \ddots \end{bmatrix} \qquad (2) \]and \[ \begin{bmatrix} \ddots & \dots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\ \vdots & A & B & C & \vdots \\ \vdots & \bullet & D & \bullet \vdots \\ {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \dots & \ddots \end{bmatrix} \longrightarrow \begin{bmatrix} \ddots & \dots & \dots & \dots & {\cdot^{\cdot^{\cdot}}} \\ \vdots & B & C & A & \vdots \\ \vdots & \bullet & D & \bullet \vdots \\ {\cdot^{\cdot^{\cdot}}} & \dots & \dots & \dots & \ddots \end{bmatrix} \qquad (3) \]are both possible. To finish, we number the counters in the following way: \[ \begin{bmatrix} 1 & 2 & 3 & \dots & n-1 & n \\ 2n & 2n-1 & 2n-2 & \dots & n+2 & n+1 \\ 2n+1 & 2n+2 & 2n+3 & \dots & 3n-1 & 3n \\ 4n & 4n-1 & 4n-2 & \dots & 3n+2 & 3n+1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \end{bmatrix} \]Observe that any two consecutive numbers are consecutive. But we have the following fact: Lemma: [Bubble sort] Let $N$ be any integer. Any permutation on $\{1, 2, \dots, N\}$ is generated by the $N-1$ adjacent transpositions $(1\; 2)$, $(2\; 3)$, \dots, $(N-1\; N)$. Proof. This is a standard fact, most easily proved by induction on $N$. $\blacksquare$ It follows an even permutation on $\{1, 2, \dots, N\}$ is an even composition of adjacent transpositions. But: Claim: Any two adjacent transpositions for our $n^2$ counters can be obtained as the product of operations of the form $(1)$, $(2)$, $(3)$. Proof. By cases: If both transpositions are horizontal, start with any operation of the form $(2)$ and then ``move'' the two transpositions in place by using $(2)$ and $(3)$ repeatedly. Same for two vertical. If one horizontal and one vertical, then start with $(1)$ and use the same proof. $\blacksquare$ This completes the proof.

(a) Basically we can cyclic shift any three squares in an L shape by sliding the bottom row left until the right square aligns, sliding the right column down until the top square aligns, then sliding the row back and then the column back. Now work backwards from the finish, permute an L taking a blank square to the bottom right, then take a L permuting the other blank square to the square one left of the bottom right, of which at least one exists. Now go in order from top to bottom left to right and one by one fill in each square by taking the L with it, the square that belongs there, and the more bottom square of the rectangle to form an L. If the two are already in the same row/column take the lowest square that fits, and since we are going in order this does not run into issues. Do this until only the bottom two rows are not correct. Now do the same thing but rotated from left to right until only the corner two by two square, which must contain both blanks, is not ordered. But this is easy to order since taking a shift that fixes one non-blank, the other three must be fixed by the shift between them. Now just undo the working backwards steps to finish. (b) First the total number of moves is even by overlaying a checkerboard whose unit square is the entire original big square, then each move changes the parity of the number of squares of each color. Next we may embed the grid into a torus and replace sliding by cyclic shifting of each row or column. Now if we number the squares in increasing order from top to bottom and left to right, we may check that each shift changes the parity of the number of inversions if $n$ is even and preserves the parity otherwise. Since the total number of shifts is even, the parity of the number of inversions is preserved, but swapping two squares creates an odd number of inversions so it is impossible.