From Wikipedia:
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 or n=3.
We will be using Gurobi to try to solve this problem:
In [ ]:
import gurobipy as gurobi
The first step is to define the decision variables. One possible choice is to define the binary variables $x_{ij}$ which is equal to 1 if, and only if, a queen is placed on cell $(i,j)$ of the board. Here, $i$ is used as index for rows and $j$ for columns.
So, let's put this into a Gurobi model, assuming a square board of size $N = 8$:
In [ ]:
model = gurobi.Model("N-Queens")
N = 8 # Size of the board
x = {}
# Adding all the variables:
for i in range(N):
for j in range(N):
varName = 'x_' + str(i) + str(j)
x[i,j] = model.addVar(vtype = gurobi.GRB.BINARY, name = varName) # Adding the binary variables
model.update()
model
So far we have a model with 64 ($ N^2 $) variables and zero constraints, so let's start adding some constraints.
In order to prevent vertical and horizontal attacks each row and column can only have, at most, one queen placed on it. Which give us:
$$ \sum_{j = 1}^N x_{ij} \leq 1, \qquad i \in \{1, ..., N\}, $$$$ \sum_{i = 1}^N x_{ij} \leq 1, \qquad j \in \{1, ..., N\}. $$Which can be implemented in the same loop...
In [ ]:
for a in range(N):
model.addConstr(gurobi.quicksum(x[a,j] for j in range(N)) <= 1)
model.addConstr(gurobi.quicksum(x[i,a] for i in range(N)) <= 1)
model.update()
model
Now, we can see that our model have 16 ($ 2N $) more constraints, one for each row and column.
The next step is to guarantee that there is only one queen at each diagonal. This is a bit trickier and one way to do it is to account for the directions separately. That is, to guarantee there isn't another queen on the top-left/bottom-right diagonal we need:
$$ \sum_{m=1}^{i+m < N, j+m < N} x_{i+m, j+m} + \sum_{m=1}^{i-m \geq 0, j-m \geq 0} x_{i-m, j-m} \leq 1, \qquad (i,j) \in B, $$in which $(i,j) \in B$ is the set of all squares in the board. Now, we need another set of constraints to account for the bottom-left/top-right diagonal:
$$ \sum_{m=1}^{i+m < N, j-m \geq 0} x_{i+m, j-m} + \sum_{m=1}^{i-m \geq 0, j+m < N} x_{i-m, j+m} \leq 1, \qquad (i,j) \in B, $$If you are having trouble understading the upper limits of the summations, try thinking about the limits of the board in the correspondent direction.
And now, the code for both sets of equations:
In [ ]:
for i in range(N):
for j in range(N):
expr = gurobi.LinExpr(x[i,j])
m = 1
while i + m < N and j + m < N: # Going to bottom right of the board
expr.add(x[i + m,j + m])
m += 1
m = 1
while 0 <= i - m and 0 <= j - m: # Going to top left of the board
expr.add(x[i - m, j - m])
m += 1
model.addConstr(expr <= 1)
expr = gurobi.LinExpr(x[i,j])
m = 1
while i + m < N and 0 <= j - m: # Going to bottom left of the board
expr.add(x[i + m, j - m])
m += 1
m = 1
while 0 <= i - m and j + m < N: # Going to top right of the board
expr.add(x[i - m, j + m])
m += 1
model.addConstr(expr <= 1)
model.update()
model
Also, we need to guarantee that there are N queens on the board:
$$\sum_{i=1}^N \sum_{j=1}^N x_{ij} = N $$
In [ ]:
model.addConstr(gurobi.quicksum(x[i,j] for i in range(N) for j in range(N)) == N)
model.update()
model
Which give us a model with 64 variables and 422 restrictions for a 8x8 board. Time to get the solution, hopefully...
In [ ]:
model.optimize()
And, printing it in a lazy way. The "Q" character marks a position where a queen can be placed and "-" marks an empty place on the board.
In [ ]:
toPrint = ''
for i in range(N):
toPrint += '\n\t'
for j in range(N):
if x[i,j].x > 0.5:
toPrint += 'Q '
else:
toPrint += '- '
print toPrint