Different ways of coloring a $4 \times 4$ game board In how many ways a $4 \times 4$ game board can be colored using four colors (red, green, blue, yellow) in such a way that each small square has a single color and the board looks exactly the same from all sides?
For this particular problem since the board's dimension is $4 \times 4$ we could probably check by brute-forcing but I am inquisitive about how to solve this one for a $n \times n$ board with $n$ or $\space x$ colors?
 A: Each equivalence class of squares under rotation can be colored in $x$ different ways.  For even side length $n=2k$, there are $k^2$ equivalence classes of size $4$ (represented by the $k \times k$ squares in the upper left, say); for odd side length $n=2k+1$, there are $k^2+k$ classes of size $4$ (represented by the $k \times (k+1)$ squares in the upper left) and one of size $1$ (the center square).  The number of symmetric colorings is therefore $x^{k^2}$ for $n=2k$ and $x^{k^2+k+1}$ for $n=2k+1$.
A: Let $T(n)$ denote the number of ways of coloring a $n \times n$ board with $x$ colors in such a way that each small square has a single color and the board looks exactly the same from all sides.
Let us now start from the squares which are close to the edges. There are $n$ squares on each side close to the edge. Consider any edge and start coloring from left to right. Each square has $x$ options till the $(n-1)^{th}$ square. However once we color the $n-1$ squares starting from left to right the colors on the other edges are automatically fixed. Hence, the number of ways of coloring the outermost set of squares is $x^{n-1}$. But once we do this, we now need to repeat this procedure for a $(n-2) \times (n-2)$ board.
Hence, $T(n)$ satisfies the recurrence, $$T(n) = x^{n-1} T(n-2)$$ where $T(1) = x$ and $T(2) = x$.
Hence, $$T(2n) = x^{(2n-1) + (2n-3) + (2n-5) + \cdots + 1} = x^{n^2}$$ and $$T(2n+1) = x^{2n + (2n-2) + (2n-4) + \cdots + 4 + 2}x = x^{n^2 + n + 1}$$
