3. In the Cartesian coordinate system, let the set of points be
$$
\begin{array}{l}
\left\{P_{1}, P_{2}, \cdots, P_{4 n+1}\right\} \\
=\{(x, y) \mid x, y \text { are integers, }|x| \leqslant n,|y| \leqslant n, x y=0\},
\end{array}
$$

where, $n \in \mathbf{N}_{+}$. Find
$$
\left(P_{1} P_{2}\right)^{2}+\left(P_{2} P_{3}\right)^{2}+\cdots+\left(P_{4 n} P_{4 n+1}\right)^{2}+\left(P_{4 n+1} P_{1}\right)^{2}
$$

the minimum value.
(Wang Xinmao, problem contributor)
3. First, prove a lemma.

Lemma Let real numbers $s_{1} \geqslant s_{2} \geqslant \cdots \geqslant s_{m}$, and
$$
\begin{array}{l}
f\left(s_{1}, s_{2}, \cdots, s_{m}\right) \\
=\min _{\left(t_{1}, t_{2}, \cdots, t_{m}\right)}\left\{\left|t_{1}-t_{2}\right|^{2}+\left|t_{2}-t_{3}\right|^{2}+\cdots+\right. \\
\left.\left|t_{m-1}-t_{m}\right|^{2}+\left|t_{m}-t_{1}\right|^{2}\right\},
\end{array}
$$

where, $\left(t_{1}, t_{2}, \cdots, t_{m}\right)$ takes all permutations of $\left(s_{1}, s_{2}, \cdots, s_{m}\right)$. Then
$$
\begin{array}{l}
f\left(s_{1}, s_{2}, \cdots, s_{m}\right) \\
\geqslant f\left(s_{2}, s_{3}, \cdots, s_{m}\right)+2\left(s_{1}-s_{2}\right)\left(s_{1}-s_{3}\right) .
\end{array}
$$

Proof of the lemma: Without loss of generality, assume $t_{1}=s_{1}$. Then
$$
\begin{aligned}
& \left|t_{1}-t_{2}\right|^{2}+\left|t_{2}-t_{3}\right|^{2}+\cdots+\left|t_{m-1}-t_{m}\right|^{2}+\left|t_{m}-t_{1}\right|^{2} \\
= & \left|t_{2}-t_{3}\right|^{2}+\cdots+\left|t_{m-1}-t_{m}\right|^{2}+\left|t_{m}-t_{2}\right|^{2}+ \\
& \left(\left|t_{1}-t_{2}\right|^{2}+\left|t_{m}-t_{1}\right|^{2}-\left|t_{m}-t_{2}\right|^{2}\right) \\
= & \left|t_{2}-t_{3}\right|^{2}+\cdots+\left|t_{m-1}-t_{m}\right|^{2}+ \\
& \left|t_{m}-t_{2}\right|^{2}+2\left(t_{1}-t_{2}\right)\left(t_{1}-t_{m}\right) \\
\geqslant & f\left(s_{2}, s_{3}, \cdots, s_{m}\right)+2\left(s_{1}-s_{2}\right)\left(s_{1}-s_{3}\right) .
\end{aligned}
$$

Back to the original problem.
Let $P_{i}=\left(x_{i}, y_{i}\right)(i=1,2, \cdots, 4 n+2)$, where $P_{4 n+2}=P_{1}$. Then
$$
\sum_{i=1}^{4 n+1} P_{i} P_{i+1}^{2}=\sum_{i=1}^{4 n+1}\left[\left(x_{i}-x_{i+1}\right)^{2}+\left(y_{i}-y_{i+1}\right)^{2}\right] .
$$

By the lemma, we have
$$
\begin{array}{l}
\sum_{i=1}^{4 n+1} P_{i} P_{i+1}^{2} \geqslant 2 f(n, \cdots, 1, \underbrace{0, \cdots, 0}_{2 n+1 \uparrow},-1, \cdots,-n) \\
\geqslant 2 f(n-1, \cdots, 1, \underbrace{1, \cdots, 0}_{2 n+1 \uparrow},-1, \cdots, 1-n)+16 \\
\geqslant \cdots \geqslant 2 f(1, \underbrace{0, \cdots, 0}_{2 n+1 \uparrow},-1)+16(n-1) \\
\quad 16 n-8 .
\end{array}
$$

When $P_{1}, P_{2}, \cdots, P_{4 n+1}$ are respectively
$$
\begin{array}{l}
(2,0),(4,0), \cdots,(n, 0), \cdots,(3,0), \\
(1,0),(0,2),(0,4), \cdots,(0, n), \cdots, \\
(0,3),(0,1),(-2,0),(-4,0), \cdots, \\
(-n, 0), \cdots,(-3,0),(-1,0),(0,-2), \\
(0,-4), \cdots,(0,-n), \cdots,(0,-3),(0,-1),(0,0)
\end{array}
$$

then $\sum_{i=1}^{4 n+1} P_{i} P_{i+1}^{2}=16 n-8$.
Therefore, the minimum value sought is $16 n-8$.