Let \(N\) be an odd number.

Paint each cell \((i, j)\) \(N\times N\) black if \(i+j\) is even, and white if it is odd. Assign numbers from \(1\) through \(\displaystyle\frac{N^2+1}2\) to the black cells in lexicographical order of \((i,j)\), and to the white cells too.

Let \(\displaystyle v_1,v_2,\ldots,v_{N^2}\) be the cells visited by the \((N^2-1)\) moves, starting from \((1,1)\).

For \(\displaystyle i=1,2,\ldots,\frac{N^2-1}2\), consider placing a domino occupying cells \(v_{2i-1}\) and \(v_{2i}\). These \(\displaystyle \frac{N^2-1}2\) do not overlap with each other, and cover all cells except for \((N,N)\). For this arrangement of dominoes \(M\), let \(f(M)\) be the inversion number of \(P\), where \(P_i\) is the index of the black cell covered by the domino covering the \(i\)-th white cell.

Let \(g(M)\) be the number of horizontal dominoes that have a black cell to the left. We claim that the parity of \(f(M)+g(M)\) is independent of \(M\).

Proof:

Any arrangement of dominoes can be transformed from one to another by repeatedly replacing two horizontal dominoes adjacent vertically with two vertical dominoes adjacent horizontally, and vice versa. Thus, it is sufficient to assert that these two operations do not change the parity of \(f(M)+g(M)\).

Proof of the reachability:

Consider an \(N\times N\) grid lacking cell \((N,N)\).

Assign a direction to the edges of the grid. Specifically, assign counterclockwise directions to the four cells around a black cell, and clockwise around a white cell.

Also assign a weight to each lattice point of the grid, so that the weight of \((1,1)\) is \(0\), and the weight \(h(x)\) of a lattice point \(h(x)\) satisfies:

• For an edge directed \(x \to y\), let \(h(y)-h(x)=3\) if a domino is striding over the edge, and \(h(y)-h(x)=-1\) otherwise.

This definition is well-defined because every cell is covered exactly once. Moreover, the weight of the lattice points on the circumference is independent of the arrangement of the dominoes, because no domino strides over the circumference.

Consider two different arrangement \(M\) and \(M'\). Let \(h(x)\) and \(h'(x)\) be the weights of the lattice points. Moreover, let \(d(x)=h(x)-h'(x)\).

A lattice point on the circumference satisfies \(d(x) = 0\), and for any edge \(x\to y\), \(h(y)-h(x)\) and \(h'(y)-h'(x)\) are either \(-1\) or \(3\), so \(d(y)-d(x)\) is one of \(-4\), \(0\), and \(4\). Thus, \(d(x)\) turns out to be always a multiple of \(4\).

Since \(M\) and \(M'\) are different arrangements, there always exist \(x\) with \(d(x)\neq 0\). Take an \(x\) maximizing \(d(x)\) for those with \(d(x)>0\); if there are multiple such \(x\), take one maximizing \(h(x)\). If there is no such \(x\), swapping \(M\) and \(M'\) leads to the same discussion. \(x\) is a lattice point inside the interior of the grid.

Take one lattice point \(y\) adjacent to \(x\) (in other words, take a \(y\) for which there exists an edge \(x\to y\) or \(y\to x\)). If \(d(y)=d(x)\), then the choice of \(x\) guarantees \(h(y) < h(x)\). If \(d(y) < d(x)\), then \(d(y) \le d(x)-4\) because \(d\) is a multiple of \(4\). This means \(h(y)-h(x) =h'(y)-h'(x)+d(y)-d(x) \le 3-4 < 0\), which again implies \(h(y) < h(x)\). In any case \(h(y) < h(x)\), so \(h(x)\) is locally maximum.

Advancing in any of the four directions decreases \(h(x)\), implying that the each of the two edges, pointing \(x\) and facing each other, must have a domino striding over. In other words, the \(2\times 2\) region centered at \(x\) is covered by two parallel dominoes. Flipping these two dominoes decreases \(d(x)\) by four, without changing \(d(y)\) for \(y\neq x\).

Hence, repeating this operation eventually makes \(d(x) = 0\) for all \(x\), making \(M\) match \(M'\).

These operations applies a transposition to the permutation used in the definition of \(f(M)\), always flipping the parity of \(f(M)\). Turning two vertical dominoes into two horizontals increases \(g(M)\) by \(1\), and the reverse decreases it by \(1\), changing the parity of \(f(M)\) and \(g(M)\). Thus, the parity of \(f(M)\) and \(g(M)\) remains invariant.

Now that we saw that the parity is an invariant, we will now find the parity.

(The remaining part will be translated later.)