Suppose we have an $m \times n$ grid or table, with $m$ being the number of rows and $n$ being the number of columns. The user can select the number of colors (let's say $k$ colors) and how often each color is allowed to occur (i.e., we have a vector of numbers of occurrence of the colors $(i_1, i_2, \dots, i_k)$). The only constraints that apply are pretty obvious: $\sum_j i_j = nm$ and $i_j \leq ⌈nm/2⌉$ for $1 \leq j \leq k$.
I would like to color the vertices/cells in a way that no two adjacent vertices/cells have the same color (adjacence is defined as up, down, left or right; i.e., it is allowed to have the same color on a cell that is on the diagonal of the current cell). If possible, there should be no strict segregation of colors along the field, i.e., each color should be distributed over the field as "randomly" as possible.
So far I've implemented a brute force algorithm based on random selection of the coordinates of the colors. However, this approach is too inefficient.
One thought of mine was to first randomly arrange the colors in a linear list (i.e., as if we would have a $1 \times (nm)$ grid), then to take out the first $n$ elements and re-arrange them into the first row, randomly shuffling the colors until the condition is fulfilled. Then taking the next $n$ elements, arranging them as a second row and shuffling the elements until all conditions are fulfilled, and so on. This way, I would still have a random component, but at each step I would only need to deal with one row, and I might realise at an earlier time point that I got stuck and need to restart. However, I'm not sure whether this approach would really improve the performance.
Is there a better way to achieve the result? And is there a way to early determine whether a valid solution for a given input exists at all?