In how many ways can an $n \times n$ table be filled with positive integers from 1 to $n^{2}$ such that the difference between numbers written in adjacent cells is not greater than $(n+1)$? (Two cells are adjacent if they share an edge or a vertex.)
If $n=1$, then the table can only be filled out in one way, and if $n=2$, then any filling is obviously correct. This represents 4! = 24 possibilities if we distinguish between fillings that can be transformed into each other by rotation and reflection, and 24 / 8 = 3 otherwise. In the following, we will deal with the case $n \geq 3$.

$1987-12-440-1$. eps1.a figure

$1987-12-440-2$. eps

$1 . b$ figure

Figure 1/a shows a valid filling for the case $n=5$. In figure 1/b, the differences are visible for the four possible types of adjacency. The lower left and upper right corner cells have no diagonal neighbor, so the numbers here can be swapped with the ones next to them. We claim that there is no essentially different filling from the four obtained this way, that is, by reflection and rotation, every solution can be transformed into one of the above four.

Consider a valid filling, and let $D=n+1$. If $d(x, y)$ denotes the length of the shortest path between the cells $x$ and $y$ through adjacent cells (i.e., as a king moves on a chessboard), then obviously $1 \leq d(x, y) \leq n-1$, and from the filling, we get that

$$
d(x, y) \geq \frac{|x-y|}{D}
$$

If equality holds for two cells in (1), then moving from $x$ to $y$ along the shortest path ( $xn-2, \quad \text { i.e. } \quad d\left(n^{2}-1,1\right)=n-1
$$

thus $n^{2}-1$ is in the last row or the last column. We can assume that the first case is true, i.e., $n^{2}-1$ is in the last row.

Now we will prove by complete induction on $i$ that

A) if $(i-1) n+1 \leq x \leq i \cdot n$, then $x$ is in the $i$-th row and stands relative to the diagonal element, $a_{i}$, before or after it, depending on whether it is smaller or larger than $a_{i}$, as can be seen in the filling of figure 1.

For $i=1$, this means that if $x \leq n$, then $x$ is in the first row. Since

$$
d\left(n^{2}-1, x\right) \geq \frac{n^{2}-1-x}{n+1} \geq \frac{n^{2}-n-1}{n+1}>n-2
$$

therefore $d\left(n^{2}-1, x\right)=n-1$, and similarly we get that $d\left(n^{2}, x\right)=n-1$. Thus, from two different cells of the bottom row, there is no path shorter than $(n-1)$ to $x$, so it is indeed in the first row.

Now let $11$, so by the property of the rigid diagonal, the statement also holds for $i$. This proves statement B) as well.

Finally, if $i=n-1$, then it is also true that the maximum element in the second row, $M_{2}=2 n$, is in the last cell. Then, however, $d(n-1,2 n)=1$, so we can only state that the cells of $n-1$ and $2 n$ are adjacent, so in the first row, $n-1$ is in the second-to-last or the last cell.

Using the main diagonals starting from the cells of the bottom row, it can similarly be proven that the filling of the diagonals below the longest main diagonal can only be as shown in figure 1 (of course, it is possible to swap the first two elements of the last row). This completes our proof, indeed there is only the given type of solution to the problem.

By reflection and rotation, 8 solutions can be made from each of the four solutions, so if we distinguish these as well, then for $n>2$, there are 32 different valid fillings for the table.