Brandon Pelfrey Mathematics and Computational Curiosities

PULP, Linear Programming, and Fitting Lots of Chess Pieces on a Board

If you ignore color, would you believe you can place 14 bishop pieces on a chess board without any of them being able to attack each other? What if you could use any chess pieces you wanted, how many could you put on the board without any attacked each other?

While working on a set of optimization problems, I came across the wonderful Python library PULP and tried to come up with some silly optimizations to test it out. Since some co-workers and I had played chess recently, I decided it would be neat to find out exactly how many chess pieces can be fitted onto a standard 8x8 chess board without any of them attacking each other.

A Quick View of Linear Programming

The problem here was solved via Linear Programming with Integer Constraints. Linear programming refers to finding a vector $\mathbf x$ that maximizes the inner product $\mathbf x \cdot \mathbf c$ for some given vector $\mathbf c$ such that a set of constraints of the form $\mathbf a_i \cdot \mathbf x \leq \mathbf b_i$ are all satisfied. Phrased in a little bit more compact notation:

Though here we just use it to solve a silly toy problem, this general form encompasses many real-world problems and their exist mature and efficient software for solving problems for even hundreds of thousands of constraints.

If the constraints can be satisfied at all, the problem is called feasible and the constraints-satisfying variable assignments form a feasible solution. If it’s impossible to assign values to the solution vector that can satisfy all the constraints, then the problem is called infeasible.

In the above optimization problem, $\mathbf{A,b,c,x}$ are often $\mathbb R$eal-valued, but there are cases where we need some restrictions. One extra constraint which we will need in this article is the restriction that the vector $\mathbf x$ that the solver determines must have all integer-valued components. This particular restriction might sound relatively benign, but actually brings us into NP-Hard territory – Solving problems with integer constraints in general has no efficient solution, though in practice “small” problems we can usually get a solution fairly quickly. If you’d like to read more about how integer constraints are handled in solvers, read up on Branch and Bound.

When an integer variable is further constrained to be either $0$ or $1$, we call it a Binary Variable. In many optimization problems where entities need to be assigned to various possible places they are commonly used.

“Implying” a Value of Another Variable

(I definitely made up this term “implying”, but it makes sense to me.)

While creating our optimization problem, it can be useful to force one binary variable to be “on” or “off” based on whether or not another variable is on or off. For instance, if we have a binary variable $x$ which is on, we might want to force another binary variable to be off.

If we need to force $A = 1$ to force “B = 1” to also be true (i.e. $A \implies B$), then you can add the constraint

$A$ and $B$ can only take on values $0$ and $1$, so imagine all four possible assignments. In each case where $A$ is $1$, $B$ must also be $1$ or this constraint would be violated. Note that when $A$ is $0$, this doesn’t force $B$ to do anything at all.

Similarly, if we want $A=1$ to force $B=0$, we use the constraint

Analogous to before, you can look all four possible assignments of $A$ and $B$, and see that if $A$ is $1$, then $B$ must be $0$.

Basic PULP

# To install: pip install pulp
import pulp

# Create a problem with some name. Tell PULP we are going to
# maximize something.
problem = pulp.LpProblem('My Problem Name', pulp.LpMaximize)

# Create two real-valued variables which PULP will find optimal
# values for
x1 = pulp.LpVariable("x1", cat=pulp.LpContinuous)
x2 = pulp.LpVariable("x2", cat=pulp.LpContinuous)

# Adding an inequality to the problem is how we add constraints
problem += x1 + x2 <= 1.0
problem += x1 <= 0.25
problem += x1 >= 0
problem += x2 >= 0

# Adding a real-valued linear function of our variables to the
# problem is how we tell PULP what the objective is
problem += 1.0 * x1 + 2.5 * x2

# PULP can use other solvers, but we'll solve our problem with
# the built-in one. (msg=1 is used to show/hid the output of the
# solver on the terminal
solver = pulp.solvers.PULP_CBC_CMD(msg=1)
problem.solve(solver)

# At this point, assuming the problem solved successfully, we
# can get the optimal values of the variables that were found
# during optimization
print 'Optimal values: x1 = %s x2= %s' % (x1.varValue, x2.varValue)

Setting up the Optimization Problem

It turns out the actual statement of this “Cram as many chess pieces on a board as possible without any attacking any others” as a mathematical optimization problem is fairly simple if you’ve seen a couple examples of how to represent things.

We will need a lot of binary variables. For each (square, piece type) combination, we will have a binary variable $B(s, p)$, where $B$ just refers to the fact this is a binary variable, $s$ is any particular square on the chess board, and $p$ is any piece type (e.g. a King, a Pawn, etc.). Remember we are ignoring color in this problem. Since these are binary variables they can only be $1$ or $0$. If one of these variables is $1$, it indicates that a piece of that type $p$ is assigned to that particular square $s$.

We will additionally need a variable $B(s)$ which simply says if there is a piece assigned to square $s$, regardless of whatever type it is.

Constraints: Putting a Piece Down Means it Covers Multiple Squares

In the code, we need a way of saying “if I put these kind of piece on this square, then all the squares it would attack would essentially be occupied as well”. There are two related sets of constraints that help enforce this behavior.

First, if a given piece type $p$ is placed on a square $s_i$, and that would mean there are some other squares $s_j$ that it attacks, and for each pair we want to add a constraint so that if $B(s_i, p)$ is set then there can’t be a piece on the square it’s attacking $s_j$:

The accompanying constraint to this is that if we place a piece of type $p$ on $s_i$, then we should mark that some piece is assigned there in the $B(s_i)$ variable:

This way if any piece of any type is assigned to this square, it will cause $B(s_i)$ to be $1$. Pairing this with the first constraint we can ensure that no assignment would cause another piece to be assigned.

Constraints: We Cannot Place More Than One Piece on a Square

A couple of obvious constraints are needed. We need to make sure that we don’t assign more than one piece to a square (and it’s also fine to have no pieces on a square):

Constraints: Two-way Coupling of $B(s,p)$ and $B(s)$

We made sure that $B(s,p) = 1 \implies B(s) = 1$, but we also need to make sure that if $B(s)$ is $1$, that some some assignment of piece was made (otherwise there is nothing stopping $B(s_i)$ from being $1$ without us actually making assignment).

This, combined with the first constraints, effectively makes $B(s_i)$ be equal to the logical OR of the B(s_i,p)$ variables.

Objective: Maximize the Number of Pieces On the Board

Since we have variables tracking if there is an assignment to a square, $B(s_i)$, we can just sum these up to get an expression for how many squares have assignments. This is exactly our objective which we are trying to maximize:

Code

The full code for this little project can be found as a gist on Github.

Some examples

(Remember P=Pawn, K=King, N=Knight, B=Bishop, Q=Queen, R=Rook).

We can maximize the number of pieces on the board that don’t attack each other considering all pieces on an 8x8 board (36 pieces):

P P P P P P P P
. . . . . . . .
P P P P P P P P
. . . . . . . .
P P P P P P P P
. . . . . . . .
P . P . P . P .
P N P N P N P N

… or just Bishops (14)

. . . . . B . B
B . . . . . . B
B . . . . . . .
B . . . . . . B
B . . . . . . B
. . . . . . . B
B . . . . . . B
. . B . . . . B

… or the classic N-Queens problem (8)

. . . . Q . . .
. Q . . . . . .
. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . Q
. . . . . Q . .
Q . . . . . . .

… or Kings on a 16x16 board (64)

. . K . . . K . K . . . . . . .
K . . . K . . . . . . K . K . K
. . . . . . K . . K . . . . . .
K . K . K . . . . . . K . K . K
. . . . . . K . K . . . . . . .
K . K . K . . . . . K . K . K .
. . . . . . K . . . . . . . . .
K . K . K . . . K . K . . K . K
. . . . . . . . . . . . . . . .
K . K . K . K . K . K . . K . K
. . . . . . . . . . . . . . . .
. K . K . K . K . K . K . K . K
. . . . . . . . . . . . . . . .
. K . K . K . K . K . K . K . K
. . . . . . . . . . . . . . . .
. K . K . K . K . K . K . K . K