4. N Queen

• Add the explanation with equations
• Solution 1

from gurobipy import *
import os

n=8
x={}

model = Model()

for i in range(n):
    for j in range(n):
        x[i+1,j+1] = model.addVar(vtype=GRB.BINARY, obj=1, name="x_{}{}".format(i+1,j+1))


model.update()

model.addConstr(quicksum(x[i+1,j+1] for i in range(n) for j in range(n)) == n)

for i in range(n):
    model.addConstr(quicksum(x[i+1,j+1] for j in range(n)) <= 1)

for j in range(n):
    model.addConstr(quicksum(x[i+1,j+1] for i in range(n)) <= 1)

for k in range(1-n, n):
    model.addConstr(quicksum(x[i+1,j+1] for i in range(n) for j in range(n) if i-j == k) <= 1)

for l in range(0, 2*n-1):
    model.addConstr(quicksum(x[i+1,j+1] for i in range(n) for j in range(n) if i+j == l) <= 1)


# Gurobi Settings
model.params.LogToConsole = 0         # Quiet Gurobi
model.params.PoolSearchMode = 2       # Force Gurobi to search for multiple optimal solutions
model.params.PoolSolutions = 10**8    # Store max 10**8 Solutions in the solution pool
model.params.PoolGap = 0              # All Solutions in the pool have 0 % Gap = optimal solutions
model.optimize()

print(x)
print(f"For n = {n} there are {model.SolCount} possible solutions")

# if model.status == GRB.status.OPTIMAL:
#     model.write("Queens.lp")
#     os.system("imshow Queens.lp")
#     model.write("Queens.sol")
#     os.system("imshow Queens.sol")
# elif model.status == GRB.status.INFEASIBLE:
#     model.computeIIS() # IIS tells you which constraints, when removed, makes the model feasible
#     model.write('inf.ilp')

• Solution 2 Fastest Solution can handle large values of n

import gurobipy as gp
from gurobipy import GRB

n = 8  # Size of the chessboard

# Create a Gurobi model
model = gp.Model("nqueens")

# Define binary decision variables
x = model.addMVar((n, n), vtype=GRB.BINARY, name="x")

# At most one queen per row; this adds n linear constraints
model.addConstr(x.sum(axis=1) <= 1, name="row_constraints")

# At most one queen per column; this adds n linear constraints
model.addConstr(x.sum(axis=0) <= 1, name="col_constraints")

# At most one queen on each diagonal
for i in range(-n + 1, n):
    # At most one queen on diagonal i
    model.addConstr(x.diagonal(i).sum() <= 1, name=f"diag_pos_{i}")

for i in range(-n + 1, n):
    # At most one queen on anti-diagonal i
    model.addConstr(x[:, ::-1].diagonal(i).sum() <= 1, name=f"diag_neg_{i}")

# Objective function (maximize number of queens placed)
model.setObjective(x.sum(), GRB.MAXIMIZE)

# Solve the model
model.optimize()

# Print the solution
if model.status == GRB.OPTIMAL:
    print("Solution found:")
    print("Board View")
    print(x.X)
    print(f"Queens position on board:")
    for i in range(n):
        for j in range(n):
            if x[i, j].X > 0.5:
                print(f"({i+1}, {j+1})")
else:
    print("No solution found.")

Comments