Let's suppose we have three different colors of knights: red, yellow, and green.
What is the maximum number of knights that we can put on a chessboard, such that no knights of different colors attack each other, and there are equal numbers of all three colors (e.g., four red, four yellow, and four green knights)?
Design a linear program that will solve this problem.
My Attempt
I am trying this on a small 3x3 board first and will try to generalize later. So far, this is the objective function and constraints that I have.
I explained why I added each constraint in the picture. However, I am not sure if this is the right approach since it seems over complicated. Could I get some verification if I am going in the right direction? Thank you.
A better choice of decision variables (which will naturally lead to a linear formulation) is to let binary decision variable $x_{ijc}$ indicate whether square $(i,j)$ contains a knight of color $c$ and let nonnegative integer variable $k$ denote the number of knights of each color. The problem is to maximize $\sum_{i,j,c} x_{ijc}$ subject to \begin{align} \sum_c x_{ijc} &\le 1 &&\text{for all $(i,j)$} \\ \sum_{i,j} x_{ijc} &= k &&\text{for all $c$} \\ x_{i_1j_1c_1} + x_{i_2j_2c_2} &\le 1 &&\text{for $(i_1,j_1,c_1)$ and $(i_2,j_2,c_2)$ with $|(i_1-i_2)(j_1-j_2)|=2$ and $c_1 < c_2$} \end{align}