Lesson 3

The \(n\)-queens problem can be formulated in terms of integer linear programming as follows. For each cell \([i,j]\) of the board, we introduce a 0/1-variable \(x_{i,j}\), which indicates whether we place a queen there or not. There are three types of inequalities for these variables.

• In each row \(0 \le i < n\) there is at least one queen: \[x_{i,0}+x_{i,1}+\dotsb+x_{i,n-1}\ge 1.\]


• In each column \(0 \le j < n\) there is at least one queen: \[x_{0,j}+x_{1,j}+\dotsb+x_{n-1,j}\ge 1.\]


• For any two cells \((i_{1},j_{1})\) and \((i_{2},j_{2})\) on the same diagonal (\(|i_{1}-i_{2}|=|j_{1}-j_{2}|\)), there is at most one queen: \[x_{i_1,j_1}+x_{i_2,j_2}\le 1.\]

from itertools import product
from mip import *

n = 30

model = Model(solver_name='cbc')
model.verbose = False

variables = [[model.add_var(var_type=BINARY) for _ in range(n)] for _ in range(n)]

for i in range(n):
    model += xsum(variables[i]) == 1

for j in range(n):
    model += xsum(variables[i][j] for i in range(n)) == 1

for i1, j1, i2, j2 in product(range(n), repeat=4):
    if i1 == i2:
        continue

    if abs(i1 - i2) == abs(j1 - j2):
        model += variables[i1][j1] + variables[i2][j2] <= 1

model.objective = maximize(xsum(variables[i][j] for i, j in product(range(n), repeat=2)))
model.optimize()

print(model.objective_value)

30.0