Putnam 2005 A2

Let $\mathbf{S} = \{(a,b) | a = 1, 2, \dots,n, b = 1,2,3\}$. A rook tour of $\mathbf{S}$ is a polygonal path made up of line segments connecting points $p_1, p_2, \dots, p_{3n}$ in sequence such that

(i) $p_i \in \mathbf{S}$,

(ii) $p_i$ and $p_{i+1}$ are a unit distance apart, for $1 \leq i <3n$,

(iii) for each $p \in \mathbf{S}$ there is a unique $i$ such that $p_i = p$. How many rook tours are there that begin at $(1,1)$ and end at $(n,1)$?

(An example of such a rook tour for $n=5$ was depicted in the original.)