This is not a homework problem. What's the best way to approach the following? 0-1 ILP works, but there might be something better:
Imagine you have a checkers board and a bag of black pieces. You want to place the pieces on the chess board so that there are no 4 in a row diagonally, vertically, or horizontally. What is the maximum number of pieces you can put on the board?
No matter what n is, the answer to this problem on an n*n chessboard is basically cn^2. Due to the finitness of this problem, the optimal solution will repeat in a certain pattern in two directions. Additionally, c should be slightly smaller than 3/4, between 5/8 and 3/4.
