A rock travelled through an n x n board, stepping at each turn to the cell neighbouring the previous one by a side, so that each cell was visited once. Bob has put the integer numbers from 1 to n^2 into the cells, corresponding to the order in which the rook has passed them. Let M be the greatest difference of the numbers in neighbouring by side cells. What is the minimal possible value of M?
To find the minimal possible value of \( M \), the greatest difference of the numbers in neighboring cells, we need to consider the movement of the rook on an \( n \times n \) board. The rook can move horizontally or vertically to an adjacent cell. We aim to minimize the maximum difference between the numbers in these adjacent cells.

1. **Zig-Zag Pattern:**
   Consider a zig-zag pattern where the rook travels through the board. For an \( n \times n \) board, the rook starts at the top-left corner and moves right until it reaches the end of the row, then moves down to the next row and moves left, and so on. This pattern ensures that each cell is visited exactly once.

2. **Numbering the Cells:**
   Number the cells in the order the rook visits them. For example, in a \( 3 \times 3 \) board, the numbering would be:
   \[
   \begin{array}{ccc}
   1 & 2 & 3 \\
   6 & 5 & 4 \\
   7 & 8 & 9 \\
   \end{array}
   \]

3. **Calculating Differences:**
   In this pattern, the difference between numbers in neighboring cells is either 1 (horizontal movement) or \( 2n-1 \) (vertical movement between rows). For example, in the \( 3 \times 3 \) board:
   - Horizontal differences: \( |2-1| = 1 \), \( |3-2| = 1 \), \( |5-6| = 1 \), etc.
   - Vertical differences: \( |6-3| = 3 \), \( |7-6| = 1 \), etc.

4. **Generalizing for \( n \times n \) Board:**
   For an \( n \times n \) board, the maximum difference in the zig-zag pattern occurs when moving from the end of one row to the start of the next row. This difference is \( 2n-1 \).

5. **Proof of Minimality:**
   To prove that \( 2n-1 \) is the minimal possible value of \( M \), consider any other pattern of movement. Any pattern must visit each cell exactly once, and the maximum difference will always be at least \( 2n-1 \) due to the need to transition between rows. Therefore, the zig-zag pattern provides the minimal possible value of \( M \).

\(\blacksquare\)

The final answer is \( \boxed{ 2n-1 } \).