# 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
)  # 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  +  +  +  +  +  +  +  +  +  +  +  +  +  +
```