Example 6 Let $n$ be a given positive integer. Consider the set of points in the Cartesian coordinate system $x O y$
$$
T=\{(x, y) \mid | x|=| y | \leqslant n, x \rtimes y \in \mathbf{Z}\} .
$$

For two points $P, Q$ in $T$, $P, Q$ are called "adjacent" if and only if $|P Q|=\sqrt{2}$ or $P Q$ is parallel to one of the coordinate axes. Each point in $T$ is colored with one of three colors: red, blue, or green, such that any two adjacent points are colored differently. Find the number of coloring ways.
$(2018$, Shanghai High School Mathematics Competition)
For $k=1,2, \cdots, n$, let
$A_{k}(-k, k), B_{k}(k, k), C_{k}(k,-k), D_{k}(-k,-k)$
and denote $S_{k}=\left\{A_{k}, B_{k}, C_{k}, D_{k}\right\}$,
$T_{k}=\{O\} \cup S_{1} \cup S_{2} \cup \cdots \cup S_{k}$,

In particular, $T_{n}=T$.
Under the coloring requirements for the point set $T$, consider the number of colors $m_{k}$ contained in the four points of $S_{k}$. If $m_{k}=3$, then $S_{k}$ is called "X-type", at this time, the square $A_{k} B_{k} C_{k} D_{k}$ has one pair of opposite vertices with different colors, and the other pair of opposite vertices are colored with the remaining color; if $m_{k}=2$, then $S_{k}$ is called "Y-type", at this time, each pair of opposite vertices of the square $A_{k} B_{k} C_{k} D_{k}$ are the same color. Clearly, $m_{k}$ cannot be 1.

Let the number of coloring methods for $T_{k}$ be $t_{k}$, where the number of coloring methods that make $S_{k}$ X-type and Y-type are $x_{k}, y_{k}$, respectively. Then
$x_{k}+y_{k}=t_{k}$.
When coloring $T_{1}$, the colors of $O, A_{1}$ have $3 \times 2 = 6$ choices, the remaining $B_{1}, D_{1}$ can only be colored with the remaining color, and thus, $C_{1}$ can only be colored the same as $A_{1}$. This indicates that
$x_{1}=0, y_{1}=6$.
Next, we seek the relationship between $x_{k}, y_{k}$ and $x_{k+1}, y_{k+1}$.
For clarity, the colors of $A_{k}, B_{k}, C_{k}, D_{k}$ can be written in the matrix $\left(\begin{array}{ll}a & b \\ d & c\end{array}\right)$ at the positions of $a, b, c, d$.
(1) For any coloring method of $T_{k}$ that makes $S_{k}$ X-type, by symmetry, we can assume the coloring of $S_{k}$ is $\left(\begin{array}{ll}\alpha & \beta \\ \gamma & \alpha\end{array}\right)$.

If $B_{k+1}$ in $S_{k+1}$ is colored $\gamma$, then $A_{k+1}, C_{k+1}$ cannot be colored $\alpha, \gamma$. Hence, they can only be colored $\beta$. Consequently, $D_{k+1}$ cannot be colored $\beta, \gamma$. Thus, we get one X-type coloring of $S_{k+1}$: $\left(\begin{array}{ll}\beta & \gamma \\ \alpha & \beta\end{array}\right)$.

Similarly, if $D_{k+1}$ in $S_{k+1}$ is colored $\beta$, then we get one X-type coloring of $S_{k+1}$: $\left(\begin{array}{ll}\gamma & \alpha \\ \beta & \gamma\end{array}\right)$.

In other cases, $B_{k+1}, D_{k+1}$ can only be colored $\alpha$, thus, we get two X-type colorings of $S_{k+1}$: $\left(\begin{array}{ll}\beta & \alpha \\ \alpha & \gamma\end{array}\right)$, $\left(\begin{array}{ll}\gamma & \alpha \\ \alpha & \beta\end{array}\right)$ and two Y-type colorings: $\left(\begin{array}{ll}\beta & \alpha \\ \alpha & \beta\end{array}\right)$, $\left(\begin{array}{ll}\gamma & \alpha \\ \alpha & \gamma\end{array}\right)$.

This indicates that the contributions of $x_{k}$ to $x_{k+1}$ and $y_{k+1}$ are $4 x_{k}$ and $2 x_{k}$, respectively.
(2) For any coloring method of $T_{k}$ that makes $S_{k}$ Y-type, by symmetry, we can assume the coloring of $S_{k}$ is $\left(\begin{array}{ll}\alpha & \beta \\ \beta & \alpha\end{array}\right)$.

In the coloring of $S_{k+1}$, if $B_{k+1}, D_{k+1}$ contain $\gamma$, then $A_{k+1}, C_{k+1}$ must be $\beta$. Thus, we get two X-type colorings: $\left(\begin{array}{ll}\beta & \gamma \\ \alpha & \beta\end{array}\right)$, $\left(\begin{array}{ll}\beta & \alpha \\ \gamma & \beta\end{array}\right)$ and one Y-type coloring: $\left(\begin{array}{ll}\beta & \gamma \\ \gamma & \beta\end{array}\right)$.

Similarly, if $A_{k+1}, C_{k+1}$ contain $\gamma$, then we get two X-type colorings: $\left(\begin{array}{ll}\gamma & \alpha \\ \alpha & \beta\end{array}\right)$, $\left(\begin{array}{ll}\beta & \alpha \\ \alpha & \gamma\end{array}\right)$ and one Y-type coloring: $\left(\begin{array}{ll}\gamma & \alpha \\ \alpha & \gamma\end{array}\right)$.
In other cases, there is only one Y-type coloring: $\left(\begin{array}{ll}\beta & \alpha \\ \alpha & \beta\end{array}\right)$. This indicates that the contributions of $y_{k}$ to $x_{k+1}$ and $y_{k+1}$ are $4 y_{k}$ and $3 y_{k}$, respectively.
Combining (1) and (2), we get
$x_{k+1}=4 x_{k}+4 y_{k}, y_{k+1}=2 x_{k}+3 y_{k}$.
From conclusions (1) and (2), we know $x_{2}=24, y_{2}=18$.
Thus, $t_{1}=x_{1}+y_{1}=6, t_{2}=x_{2}+y_{2}=42$.
From conclusion (2), we get
$t_{k+1}=x_{k+1}+y_{k+1}=6 x_{k}+7 y_{k}$
$=7 t_{k}-x_{k}=7 t_{k}-4 t_{k-1}(k \geqslant 2)$.
The characteristic equation of this recurrence relation is $x^{2}-7 x+4=0$,

with roots $\frac{7 \pm \sqrt{33}}{2}$.
We can set $t_{n}=\left(\frac{7+\sqrt{33}}{2}\right)^{n} \lambda+\left(\frac{7-\sqrt{33}}{2}\right)^{n} \mu$
For computational convenience, we define $t_{0}$ such that
$t_{2}=7 t_{1}-4 t_{0}$.
Given $t_{1}=6, t_{2}=42$, we know $t_{0}=0$.
Thus, from equation (3), we get
$\lambda+\mu=t_{0}=0$,
$\left(\frac{7+\sqrt{33}}{2}\right) \lambda+\left(\frac{7-\sqrt{33}}{2}\right) \mu=t_{1}=6$.
Solving, we get $\lambda=-\mu=\frac{6}{\sqrt{33}}=\frac{2 \sqrt{33}}{11}$.
Therefore, the number of coloring methods is
$$
t_{n}=\frac{2 \sqrt{33}}{11}\left(\left(\frac{7+\sqrt{33}}{2}\right)^{n}-\left(\frac{7-\sqrt{33}}{2}\right)^{n}\right) .
$$

[Note] In the coloring process, it is observed that from $k=2$ onwards, each layer $S_{k}$ can contain three colors (essentially only one such type) or two colors (essentially only one such type), and the color distribution of $S_{k}$ affects the number of coloring methods for the adjacent layer $S_{k+1}$. It is natural to distinguish between the two types and use a recursive method for counting.