Calculate number of ways to color matrix using inclusion-exclusion principle This was asked in a recent contest.
The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same color.
In other words, I want to count the number of different graph colorings of a grid graph: the graph of a $N \times M$ grid. The limits were $1 \le N,M \le 8$ and $1 \le K \le 1000000000$.

Is it possible to count the number of colors using the inclusion-exclusion principle, and if so, how? I saw another question that solves the special case (where $M=2$) using inclusion-exclusion, so I'm wondering if that kind of approach can be generalized here.
Not an answer, but related.

The number of colorings of a graph on $N$ vertices with $c$ colors is a polynomial of degree at most $N$ in $c$ known as the chromatic polynomial. As such, it can be calculated by evaluating it at $N+1$ points, say $c=0$ to $c=N$. Your program need $\binom{8+1}{2} = 36$ of these polynomial.

In some cases there are formulas for the chromatic polynomial, but in the case of grids it's an open question to find such a formula, see this question on math.se.