Turns out linear programming is not fast... Takes about 90 minutes to find the optimal solution for any board configuration.