12. (18 points) As shown in Figure 2, given a cube $A B C D E F G H$ with edge length 1, let $P$ be the set of its eight vertices. Define a sequence of $2 n+1$ ordered vertices $\left(A_{0} A_{1} \cdots A_{2 n}\right)$ such that point $A_{0}$ coincides with $A$, and for each $i \in\{0,1, \cdots, 2 n-1\}, A_{i+1}$ is an adjacent vertex to $A_{i}$ in the set $P$.
(1) Determine all possible positions of vertex $A_{2 n}$;
(2) Let $S_{2 n}$ be the number of all $2 n+1$ ordered vertex sequences $\left(A_{0} A_{1} \cdots A_{2 n}\right)$ such that $A_{2 n}=C$. Find $S_{2 n}$.
12. (1) Establish a spatial rectangular coordinate system with $A B$, $A D$, and $A E$ as the $x$, $y$, and $z$ axes, respectively. Then
$$
A(0,0,0), B(1,0,0), \cdots, H(0,1,1) \text {. }
$$

If $A_{i+1}$ and $A_{i}$ are adjacent vertices, then $A_{i+1}$ only changes one of the coordinates of $A_{i}$ from 0 to 1, or from 1 to 0.

Thus, the sum of the three coordinates of $A_{i+1}$ and $A_{i}$ have different parities.
Noting that $A_{0}=A(0,0,0)$.
Therefore, the sum of the three coordinates of $A_{2 n}$ must be even.
Hence, it can only be $A(0,0,0)$ or $C(1,1,0)$ or $F(1,0,1)$ or $H(0,1,1)$.
(2) Consider the relationship between $S_{2 n+2}$ and $S_{2 n}$.
Suppose $\left(A_{0} A_{1} \cdots A_{2 n} A_{2 n+1} A_{2 n+2}\right)$ is a sequence of $2 n+3$ ordered vertices satisfying the condition, i.e.,
$$
A_{0}=A, A_{2 n+2}=C \text {. }
$$

When $A_{2 n}=C$, there are $S_{2 n}$ sequences $\left(A_{0} A_{1} \cdots A_{2 n}\right)$, and $A_{2 n+1}$ has three possibilities, so there are $3 S_{2 n}$ such sequences of $2 n+3$ ordered vertices.

When $A_{2 n}$ is one of the vertices $A$, $F$, or $H$, $A_{2 n+1}$ has only two possibilities. Since there are $3^{2 n}$ sequences of $2 n+1$ ordered vertices $\left(A_{0} A_{1} \cdots A_{2 n}\right)$, there are $2\left(3^{2 n}-S_{2 n}\right)$ such sequences of $2 n+3$ ordered vertices.
Thus, $S_{2 n+2}=3 S_{2 n}+2\left(3^{2 n}-S_{2 n}\right)=S_{2 n}+2 \times 3^{2 n}$.
Given $S_{2}=2$, we have
$$
\begin{array}{l}
S_{2 n}=\left(S_{2 n}-S_{2 n-2}\right)+\cdots+\left(S_{4}-S_{2}\right)+S_{2} \\
=2\left(3^{2 n-2}+3^{2 n-4}+\cdots+3^{2}\right)+2 \\
=2\left(9^{n-1}+9^{n-2}+\cdots+1\right)=\frac{9^{n}-1}{4} .
\end{array}
$$
（Proposed by Li Dayuan, Liu Hongkun, Ye Shengyang, and Lian Shifan）