EDIT: I have been working on this for a while now and I can say that a $2\times 2$ grid is such a deceiver because the maximum colors we can do for it is $2$. From $3$, everything breaks as there will always be adjacent cells colored.
Given a $K\times K$ grid of cells and $N$ distinct colors, in how many ways can we color the grid such that no two adjacent cells are colored. That said, if two colors touch horizontal or vertical to each other, they are adjacent. That is to be avoided, as some images below show. Of importance are cases where $N$$\le$$K^2$. As you might have imagined, the $K^2$ defines the possible spaces. It is undesirable to end up with a case where we have too many colors than is the square space. Waste of paint. Anyway, also, each color is used only once. Keeps everything neat.
Consider the following $7\times 7$ grid of cells where we are working with $2$ colors. The following coloring's acceptable;
How can this be solved?