Problem 1580

Answer: $3 \cdot 2^{n+2} - 24$.
Suppose there are at least three different colors $A, B, C$ in the first row. Then they occur consecutively, say in the order $ABC$. Then the cell below the $B$ has the fourth color $D$, and all other cells are determined by the first row, because three cells in a $2 \times 2$ square determine the other one, and we can fill the board from right to left and left to right, beginning at the $D$. Notice that the cells below $ABC$ are $CDA$, so the next row always has three different colors and can be filled. Finally, notice that the colors alternate in the columns in between $A, C$ and $B, D$, so all columns have two different colors. There are $\binom{4}{2} = 6$ ways to choose the two colors for the top two cells in the first column and $2^n$ ways to choose the two colors for the top two cells in each next column: if we chose $\{A, B\}$ for the first column, then we can choose $(A, B)$ or $(B, A)$ for the first column, $(C, D)$ or $(D, C)$ for the next column, $(A, B)$ or $(B, A)$ for the next column, and so on. We only need to exclude the cases where there are only two colors in the first row: in this case, we still have 6 choices for the first column, and 2 choices for each of the first two columns orders. The other orders are determined to be the same as the preceding ones, so to repeat the pattern. So we must exclude $6 \cdot 2 \cdot 2 = 24$ cases.
Now we deal with the case in which there are only two colors in the first row. There are $4 \cdot 3$ ways to choose the colors in the first row. Then each following row has the other two colors, alternated in one of two ways. So in this case we have $12 \cdot 2^{n-1}$ colorings.
So the grand total is $6 \cdot 2^n - 24 + 12 \cdot 2^{n-1} = 3 \cdot 2^{n+2} - 24$.