3. In an $n \times n$ grid $C$, the numbers $1,2, \ldots, n^{2}$ are written, with one number in each cell. If two cells share a common edge, they are called "adjacent." Now we calculate the difference between the numbers in any two adjacent cells, and denote the maximum of all these differences as $g$. Find the minimum possible value of $g$.


In summary, the minimum value of $g$ is $n$.
3, Solution: For convenience, we denote the square at the $i$-th row and $j$-th column as $A(i, j)$, and the number filled in $A(i, j)$ as $a_{ij}$.
We first prove: no matter how the numbers are filled, there must be two "adjacent" squares whose numbers differ by at least $n$.
If not, assume that the difference between the numbers in any two adjacent squares is no more than $n-1$. Consider the largest number in each row and the largest number in each column, and let the smallest of these $2n$ largest numbers be $a_{pq}$, and without loss of generality, assume $a_{pq}$ is the largest number in the $p$-th row.

For any $j \in \{1, 2, \ldots, n\}$, let the largest number in the $j$-th column be $a_{ij}$, then $a_{pj} \leq a_{pq} \leq a_{ij}$. Since the difference between the numbers in any two adjacent squares is no more than $n-1$, there must be some number in the square $A(p, j)$ that falls into the set $S = \{a_{pq}, a_{pq}+1, \ldots, a_{pq}+n-2\}$ when moving from $A(p, j)$ to $A(i, j)$ along the column. Thus, there is a number in each column that falls into the set $S$. Since $|S| = n-1$, by the pigeonhole principle, there must be some number in $S$ that appears in two different columns, meaning this number appears at least twice in the table, which is a contradiction.

Next, we take $a_{ij} = n(i-1) + j (1 \leq i, j \leq n)$, then the difference between the numbers in any two adjacent squares in the same row is 1, and the difference between the numbers in any two adjacent squares in the same column is $n$, in this case $g = n$.