N-Queens

Description: How can N queens be placed on an NxN chessboard so that no two of them attack each other?

Tags: amplpy, constraint-programming, highlights

Notebook author: Gleb Belov <gleb@ampl.com>

# Install dependencies
%pip install -q amplpy

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["highs"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Modeling N-Queens with alldiff

N-Queens: How can N queens be placed on an NxN chessboard so that no two of them attack each other?

Constraint alldiff enforces a set of integer variables to take distinct values. Using alldiff, we can model N-Queens as follows:

%%ampl_eval
reset;
param n integer > 0; # N-queens
var Row {1..n} integer >= 1 <= n;
s.t. row_attacks: alldiff ({j in 1..n} Row[j]);
s.t. diag_attacks: alldiff ({j in 1..n} Row[j]+j);
s.t. rdiag_attacks: alldiff ({j in 1..n} Row[j]-j);

Solving with HiGHS and displaying the solution

n = 20
ampl.param["n"] = n
ampl.option["solver"] = "highs"
ampl.option["highs_options"] = "outlev=0"
ampl.solve()
solution = ampl.get_data("Row").to_dict()
queens = set((int(r) - 1, int(c) - 1) for c, r in solution.items())
print("Solution")
for r in range(n):
    print("".join([" Q " if (r, c) in queens else " + " for c in range(n)]))

HiGHS 1.4.0: tech:outlev=0
0; Iter: Time   3.219e-07; average =   3.219e-08; Bound =   3.312e-05
HiGHS 1.4.0: optimal solution
0 simplex iterations
1 branching nodes
Objective = find a feasible point.
Solution
 +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  Q  +  + 
 +  +  +  +  +  +  +  +  +  +  +  +  +  Q  +  +  +  +  +  + 
 +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  Q  + 
 +  +  +  +  +  +  +  +  Q  +  +  +  +  +  +  +  +  +  +  + 
 +  +  +  +  +  +  +  +  +  +  +  +  Q  +  +  +  +  +  +  + 
 +  +  +  +  +  +  +  Q  +  +  +  +  +  +  +  +  +  +  +  + 
 +  +  +  Q  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  + 
 Q  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  + 
 +  +  Q  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  + 
 +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  Q  +  +  + 
 +  +  +  +  +  +  +  +  +  Q  +  +  +  +  +  +  +  +  +  + 
 +  +  +  +  +  +  +  +  +  +  +  Q  +  +  +  +  +  +  +  + 
 +  Q  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  + 
 +  +  +  +  +  +  +  +  +  +  +  +  +  +  Q  +  +  +  +  + 
 +  +  +  +  Q  +  +  +  +  +  +  +  +  +  +  +  +  +  +  + 
 +  +  +  +  +  +  Q  +  +  +  +  +  +  +  +  +  +  +  +  + 
 +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  Q 
 +  +  +  +  +  +  +  +  +  +  +  +  +  +  +  Q  +  +  +  + 
 +  +  +  +  +  +  +  +  +  +  Q  +  +  +  +  +  +  +  +  + 
 +  +  +  +  +  Q  +  +  +  +  +  +  +  +  +  +  +  +  +  + 

previous

Multicommodity transportation problem

next

NFL Team Rating