Counting Colorings of a Grid
For every graph $G$ on $n$ vertices there is a degree $n$ polynomial $\chi_G$ such that $\chi_G(k)$ is the number of valid $k$-colorings of the graph. This polynomial is known as the chromatic polynomial, and can be found in exponential time. The easiest solution to the programming challenge is to precompute the chromatic polynomials. For example, denoting the $n \times m$ grid by $G(n,m)$, we have
$$
\begin{align*}
\chi_{G(1,1)} &amp;= x \\
\chi_{G(1,2)} &amp;= x^2 - x \\
\chi_{G(2,2)} &amp;= x^4 - 4x^3 + 6x^2 - 3x \\
\chi_{G(1,3)} &amp;= x^3 - 2x^2 + x \\
\chi_{G(2,3)} &amp;= x^6 - 7x^5 + 21x^4 - 33x^3 + 27x^2 - 9x \\
\chi_{G(3,3)} &amp;= x^9 - 12x^8 + 66x^7 - 216x^6 + 459x^5 - 648x^4 + 594x^3 - 323x^2 + 79x
\end{align*}
$$