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;
This, too, is acceptable. Yes, the cells are adjacent, but not horizontally/vertically.
However, the coloring below is not acceptable;
This is also not acceptable;
How can this be solved?
Here are the results for small $K$ and $N$, without the factor of $N!$: \begin{equation} \begin{matrix} &K\backslash N &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 \\ &1 &1 \\ &2 &4 &2 &0 &0 \\ &3 &9 &24 &22 &6 &1 &0 &0 &0 &0 \\ &4 &16 &96 &276 &405 &304 &114 &20 &2 &0 &0 &0 &0 &0 &0 \\ &5 &25 &260 &1474 &5024 &10741 &14650 &12798 &7157 &2578 &618 &106 &14 &1 &0 \end{matrix} \end{equation} The count for $N=1$ is obviously $K^2$. The next few columns appear in OEIS as sequences involving placements of nonattacking wazirs on a chessboard: A172225 A172226 A172227 A172228