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 + + + + + + + + + + + + + +