# The N-queens Problem

In the following sections, we'll illustrate constraint programming (CP) by a combinatorial problem based on the game of chess. In chess, a queen can attack horizontally, vertically, and diagonally. The N-queens problem asks:

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

Below, you can see one possible solution to the N-queens problem for N = 4.

No two queens are on the same row, column, or diagonal.

Note that this isn't an optimization problem: we want to find all possible solutions, rather than one optimal solution, which makes it a natural candidate for constraint programming. The following sections describe the CP approach to the N-queens problem, and present programs that solve it using both the CP-SAT solver and the original CP solver.

## CP approach to the N-queens problem

A CP solver works by systematically trying all possible assignments of values to the variables in a problem, to find the feasible solutions. In the 4-queens problem, the solver starts at the leftmost column and successively places one queen in each column, at a location that is not attacked by any previously placed queens.

### Propagation and backtracking

There are two key elements to a constraint programming search:

• Propagation — Each time the solver assigns a value to a variable, the constraints add restrictions on the possible values of the unassigned variables. These restrictions propagate to future variable assignments. For example, in the 4-queens problem, each time the solver places a queen, it can't place any other queens on the row and diagonals the current queen is on. Propagation can speed up the search significantly by reducing the set of variable values the solver must explore.
• Backtracking occurs when either the solver can't assign a value to the next variable, due to the constraints, or it finds a solution. In either case, the solver backtracks to a previous stage and changes the value of the variable at that stage to a value that hasn't already been tried. In the 4-queens example, this means moving a queen to a new square on the current column.

Next, you'll see how constraint programming uses propagation and backtracking to solve the 4-queens problem.

Let's suppose the solver starts by arbitrarily placing a queen in the upper left corner. That's a hypothesis of sorts; perhaps it will turn out that no solution exists with a queen in the upper left corner.

Given this hypothesis, what constraints can we propagate? One constraint is that there can be only one queen in a column (the gray Xs below), and another constraint prohibits two queens on the same diagonal (the red Xs below).

Our third constraint prohibits queens on the same row:

Our constraints propagated, we can test out another hypothesis, and place a second queen on one of the available remaining squares. Our solver might decide to place in it the first available square in the second column:

After propagating the diagonal constraint, we can see that it leaves no available squares in either the third column or last row:

With no solutions possible at this stage, we need to backtrack. One option is for the solver to choose the other available square in the second column. However, constraint propagation then forces a queen into the second row of the third column, leaving no valid spots for the fourth queen:

And so the solver must backtrack again, this time all the way back to the placement of the first queen. We have now shown that no solution to the queens problem will occupy a corner square.

Since there can be no queen in the corner, the solver moves the first queen down by one, and propagates, leaving only one spot for the second queen:

Propagating again reveals only one spot left for the third queen:

And for the fourth and final queen:

We have our first solution! If we instructed our solver to stop after finding the first solution, it would end here. Otherwise, it would backtrack again and place the first queen in the third row of the first column.

## Solution using CP-SAT

The N-queens problem is ideally suited to constraint programming. In this section we'll walk through a short Python program that uses the CP-SAT solver to find all solutions to the problem.

### Import the libraries

The following code imports the required library.

### Python

```import sys
import time
from ortools.sat.python import cp_model```

### C++

```#include <stdlib.h>

#include <sstream>
#include <string>
#include <vector>

#include "absl/strings/numbers.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/sorted_interval_list.h"```

### Java

```import com.google.ortools.Loader;

### C#

```using System;

### Declare the model

The following code declares the CP-SAT model.

### Python

`model = cp_model.CpModel()`

### C++

`CpModelBuilder cp_model;`

### Java

`CpModel model = new CpModel();`

### C#

```        CpModel model = new CpModel();

int BoardSize = 8;
// There are `BoardSize` number of variables, one for a queen in each
// column of the board. The value of each variable is the row that the
// queen is in.
IntVar[] queens = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
queens[i] = model.NewIntVar(0, BoardSize - 1, \$"x{i}");
}

// Define constraints.
// All rows must be different.

// No two queens can be on the same diagonal.
LinearExpr[] diag1 = new LinearExpr[BoardSize];
LinearExpr[] diag2 = new LinearExpr[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
diag1[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/i);
diag2[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/-i);
}

// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
SolutionPrinter cb = new SolutionPrinter(queens);
// Search for all solutions.
solver.StringParameters = "enumerate_all_solutions:true";
// And solve.
solver.Solve(model, cb);

Console.WriteLine("Statistics");
Console.WriteLine(\$"  conflicts : {solver.NumConflicts()}");
Console.WriteLine(\$"  branches  : {solver.NumBranches()}");
Console.WriteLine(\$"  wall time : {solver.WallTime()} s");
Console.WriteLine(\$"  number of solutions found: {cb.SolutionCount()}");
}
}
```

### Create the variables

The solver's creates the variables for the problem as an array named `queens`.

### Python

```# There are `board_size` number of variables, one for a queen in each column
# of the board. The value of each variable is the row that the queen is in.
queens = [model.new_int_var(0, board_size - 1, f"x_{i}") for i in range(board_size)]```

### C++

```// There are `board_size` number of variables, one for a queen in each column
// of the board. The value of each variable is the row that the queen is in.
std::vector<IntVar> queens;
queens.reserve(board_size);
Domain range(0, board_size - 1);
for (int i = 0; i < board_size; ++i) {
queens.push_back(
cp_model.NewIntVar(range).WithName("x" + std::to_string(i)));
}```

### Java

```int boardSize = 8;
// There are `BoardSize` number of variables, one for a queen in each column of the board. The
// value of each variable is the row that the queen is in.
IntVar[] queens = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
queens[i] = model.newIntVar(0, boardSize - 1, "x" + i);
}```

### C#

```int BoardSize = 8;
// There are `BoardSize` number of variables, one for a queen in each
// column of the board. The value of each variable is the row that the
// queen is in.
IntVar[] queens = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
queens[i] = model.NewIntVar(0, BoardSize - 1, \$"x{i}");
}```

Here we assume that `queens[j]` is the row number for the queen in column `j`. In other words, `queens[j] = i` means there is a queen in row `i` and column `j`.

### Create the constraints

Here's the code that creates the constraints for the problem.

### Python

```# All rows must be different.

# No two queens can be on the same diagonal.
model.add_all_different(queens[i] + i for i in range(board_size))
model.add_all_different(queens[i] - i for i in range(board_size))```

### C++

```// The following sets the constraint that all queens are in different rows.

// No two queens can be on the same diagonal.
std::vector<LinearExpr> diag_1;
diag_1.reserve(board_size);
std::vector<LinearExpr> diag_2;
diag_2.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
diag_1.push_back(queens[i] + i);
diag_2.push_back(queens[i] - i);
}

### Java

```// All rows must be different.

// No two queens can be on the same diagonal.
LinearExpr[] diag1 = new LinearExpr[boardSize];
LinearExpr[] diag2 = new LinearExpr[boardSize];
for (int i = 0; i < boardSize; ++i) {
}

### C#

```// All rows must be different.

// No two queens can be on the same diagonal.
LinearExpr[] diag1 = new LinearExpr[BoardSize];
LinearExpr[] diag2 = new LinearExpr[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
diag1[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/i);
diag2[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/-i);
}

The code uses the `AddAllDifferent` method, which requires all the elements of a variable array to be different.

Let's see how these constraints guarantee the three conditions for the N-queens problem (queens on different rows, columns, and diagonals).

#### No two queens on the same row

Applying the solver's `AllDifferent` method to `queens` forces the values of `queens[j]` to be different for each `j`, which means that all queens must be in different rows.

#### No two queens on the same column

This constraint is implicit in the definition of `queens`. Since no two elements of `queens` can have the same index, no two queens can be in the same column.

#### No two queens on the same diagonal

The diagonal constraint is a little trickier than the row and column constraints. First, if two queens lie on the same diagonal, one of the following conditions must be true:

• The row number plus the column number for each of the two queens are equal. In other words, `queens(j) + j` has the same value for two different indices `j`.
• The row number minus the column number for each of the two queens are equal. In this case, `queens(j) - j` has the same value for two different indices `j`.

One of these conditions means the queens lie on the same ascending diagonal ( going from left to right), while the other means they lie on the same descending diagonal. Which condition corresponds to ascending and which to descending depends on how you order the rows and columns. As mentioned in the previous section, the ordering has no effect on the set of solutions, just on how you visualize them.

So the diagonal constraint is that the values of `queens(j) + j` must all be different, and the values of `queens(j) - j` must all be different, for different `j`.

To apply the `AddAllDifferent` method to `queens(j) + j`, we put the N instances of the variable, for `j` from `0` to `N-1`, into an array, `diag1`, as follows:

```q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i)
diag1.append(q1)

Then we apply `AddAllDifferent` to `diag1`.

`model.AddAllDifferent(diag1)`

The constraint for `queens(j) - j` is created similarly.

### Create a solution printer

To print all solutions to the N-queens problem, you need to pass a callback, called a solution printer, to the CP-SAT solver. The callback prints each new solution as the solver finds it. The following code creates a solution printer.

### Python

```class NQueenSolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""

def __init__(self, queens: list[cp_model.IntVar]):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__queens = queens
self.__solution_count = 0
self.__start_time = time.time()

@property
def solution_count(self) -> int:
return self.__solution_count

def on_solution_callback(self):
current_time = time.time()
print(
f"Solution {self.__solution_count}, "
f"time = {current_time - self.__start_time} s"
)
self.__solution_count += 1

all_queens = range(len(self.__queens))
for i in all_queens:
for j in all_queens:
if self.value(self.__queens[j]) == i:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()
```

### C++

```int num_solutions = 0;
Model model;
LOG(INFO) << "Solution " << num_solutions;
for (int i = 0; i < board_size; ++i) {
std::stringstream ss;
for (int j = 0; j < board_size; ++j) {
if (SolutionIntegerValue(response, queens[j]) == i) {
// There is a queen in column j, row i.
ss << "Q";
} else {
ss << "_";
}
if (j != board_size - 1) ss << " ";
}
LOG(INFO) << ss.str();
}
num_solutions++;
}));```

### Java

```static class SolutionPrinter extends CpSolverSolutionCallback {
public SolutionPrinter(IntVar[] queensIn) {
solutionCount = 0;
queens = queensIn;
}

@Override
public void onSolutionCallback() {
System.out.println("Solution " + solutionCount);
for (int i = 0; i < queens.length; ++i) {
for (int j = 0; j < queens.length; ++j) {
if (value(queens[j]) == i) {
System.out.print("Q");
} else {
System.out.print("_");
}
if (j != queens.length - 1) {
System.out.print(" ");
}
}
System.out.println();
}
solutionCount++;
}

public int getSolutionCount() {
return solutionCount;
}

private int solutionCount;
private final IntVar[] queens;
}```

### C#

```public class SolutionPrinter : CpSolverSolutionCallback
{
public SolutionPrinter(IntVar[] queens)
{
queens_ = queens;
}

public override void OnSolutionCallback()
{
Console.WriteLine(\$"Solution {SolutionCount_}");
for (int i = 0; i < queens_.Length; ++i)
{
for (int j = 0; j < queens_.Length; ++j)
{
if (Value(queens_[j]) == i)
{
Console.Write("Q");
}
else
{
Console.Write("_");
}
if (j != queens_.Length - 1)
Console.Write(" ");
}
Console.WriteLine("");
}
SolutionCount_++;
}

public int SolutionCount()
{
return SolutionCount_;
}

private int SolutionCount_;
private IntVar[] queens_;
}```

Note that the solution printer must be written as a Python class, due to the Python interface to the underlying C++ solver.

The solutions are printed by the following lines in the solution printer.

```for v in self.__variables:
print('%s = %i' % (v, self.Value(v)), end = ' ')```

In this example, `self.__variables` is the variable `queens`, and each `v` corresponds to one of the eight entries of `queens`. This prints a solution in the following form: `x0 = queens(0) x1 = queens(1) ... x7 = queens(7)` where `xi` is the column number of the queen in row `i`.

The next section shows an example of a solution.

### Call the solver and display the results

The following code runs the solver and displays the solutions.

### Python

```solver = cp_model.CpSolver()
solution_printer = NQueenSolutionPrinter(queens)
solver.parameters.enumerate_all_solutions = True
solver.solve(model, solution_printer)```

### C++

```// Tell the solver to enumerate all solutions.
SatParameters parameters;
parameters.set_enumerate_all_solutions(true);

const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
LOG(INFO) << "Number of solutions found: " << num_solutions;```

### Java

```CpSolver solver = new CpSolver();
SolutionPrinter cb = new SolutionPrinter(queens);
// Tell the solver to enumerate all solutions.
solver.getParameters().setEnumerateAllSolutions(true);
// And solve.
solver.solve(model, cb);```

### C#

```// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
SolutionPrinter cb = new SolutionPrinter(queens);
// Search for all solutions.
solver.StringParameters = "enumerate_all_solutions:true";
// And solve.
solver.Solve(model, cb);```

The program finds 92 different solutions for an 8x8 board. Here's the first one.

```        Q _ _ _ _ _ _ _
_ _ _ _ _ _ Q _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
...91 other solutions displayed...
Solutions found: 92```

You can solve the problem for a board of a different size by passing in N as a command-line argument. For example, if the program is named `queens`, `python nqueens_sat.py 6` solves the problem for a 6x6 board.

### The entire program

Here is the entire program for the N-queens program.

### Python

```"""OR-Tools solution to the N-queens problem."""
import sys
import time
from ortools.sat.python import cp_model

class NQueenSolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""

def __init__(self, queens: list[cp_model.IntVar]):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__queens = queens
self.__solution_count = 0
self.__start_time = time.time()

@property
def solution_count(self) -> int:
return self.__solution_count

def on_solution_callback(self):
current_time = time.time()
print(
f"Solution {self.__solution_count}, "
f"time = {current_time - self.__start_time} s"
)
self.__solution_count += 1

all_queens = range(len(self.__queens))
for i in all_queens:
for j in all_queens:
if self.value(self.__queens[j]) == i:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()

def main(board_size: int) -> None:
# Creates the solver.
model = cp_model.CpModel()

# Creates the variables.
# There are `board_size` number of variables, one for a queen in each column
# of the board. The value of each variable is the row that the queen is in.
queens = [model.new_int_var(0, board_size - 1, f"x_{i}") for i in range(board_size)]

# Creates the constraints.
# All rows must be different.

# No two queens can be on the same diagonal.
model.add_all_different(queens[i] + i for i in range(board_size))
model.add_all_different(queens[i] - i for i in range(board_size))

# Solve the model.
solver = cp_model.CpSolver()
solution_printer = NQueenSolutionPrinter(queens)
solver.parameters.enumerate_all_solutions = True
solver.solve(model, solution_printer)

# Statistics.
print("\nStatistics")
print(f"  conflicts      : {solver.num_conflicts}")
print(f"  branches       : {solver.num_branches}")
print(f"  wall time      : {solver.wall_time} s")
print(f"  solutions found: {solution_printer.solution_count}")

if __name__ == "__main__":
# By default, solve the 8x8 problem.
size = 8
if len(sys.argv) > 1:
size = int(sys.argv[1])
main(size)```

### C++

```// OR-Tools solution to the N-queens problem.
#include <stdlib.h>

#include <sstream>
#include <string>
#include <vector>

#include "absl/strings/numbers.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/util/sorted_interval_list.h"

namespace operations_research {
namespace sat {

void NQueensSat(const int board_size) {
// Instantiate the solver.
CpModelBuilder cp_model;

// There are `board_size` number of variables, one for a queen in each column
// of the board. The value of each variable is the row that the queen is in.
std::vector<IntVar> queens;
queens.reserve(board_size);
Domain range(0, board_size - 1);
for (int i = 0; i < board_size; ++i) {
queens.push_back(
cp_model.NewIntVar(range).WithName("x" + std::to_string(i)));
}

// Define constraints.
// The following sets the constraint that all queens are in different rows.

// No two queens can be on the same diagonal.
std::vector<LinearExpr> diag_1;
diag_1.reserve(board_size);
std::vector<LinearExpr> diag_2;
diag_2.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
diag_1.push_back(queens[i] + i);
diag_2.push_back(queens[i] - i);
}

int num_solutions = 0;
Model model;
LOG(INFO) << "Solution " << num_solutions;
for (int i = 0; i < board_size; ++i) {
std::stringstream ss;
for (int j = 0; j < board_size; ++j) {
if (SolutionIntegerValue(response, queens[j]) == i) {
// There is a queen in column j, row i.
ss << "Q";
} else {
ss << "_";
}
if (j != board_size - 1) ss << " ";
}
LOG(INFO) << ss.str();
}
num_solutions++;
}));

// Tell the solver to enumerate all solutions.
SatParameters parameters;
parameters.set_enumerate_all_solutions(true);

const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
LOG(INFO) << "Number of solutions found: " << num_solutions;

// Statistics.
LOG(INFO) << "Statistics";
LOG(INFO) << CpSolverResponseStats(response);
}

}  // namespace sat
}  // namespace operations_research

int main(int argc, char** argv) {
int board_size = 8;
if (argc > 1) {
if (!absl::SimpleAtoi(argv[1], &board_size)) {
LOG(INFO) << "Cannot parse '" << argv[1]
<< "', using the default value of 8.";
board_size = 8;
}
}
operations_research::sat::NQueensSat(board_size);
return EXIT_SUCCESS;
}```

### Java

```package com.google.ortools.sat.samples;

/** OR-Tools solution to the N-queens problem. */
public final class NQueensSat {
static class SolutionPrinter extends CpSolverSolutionCallback {
public SolutionPrinter(IntVar[] queensIn) {
solutionCount = 0;
queens = queensIn;
}

@Override
public void onSolutionCallback() {
System.out.println("Solution " + solutionCount);
for (int i = 0; i < queens.length; ++i) {
for (int j = 0; j < queens.length; ++j) {
if (value(queens[j]) == i) {
System.out.print("Q");
} else {
System.out.print("_");
}
if (j != queens.length - 1) {
System.out.print(" ");
}
}
System.out.println();
}
solutionCount++;
}

public int getSolutionCount() {
return solutionCount;
}

private int solutionCount;
private final IntVar[] queens;
}

public static void main(String[] args) {
// Create the model.
CpModel model = new CpModel();

int boardSize = 8;
// There are `BoardSize` number of variables, one for a queen in each column of the board. The
// value of each variable is the row that the queen is in.
IntVar[] queens = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
queens[i] = model.newIntVar(0, boardSize - 1, "x" + i);
}

// Define constraints.
// All rows must be different.

// No two queens can be on the same diagonal.
LinearExpr[] diag1 = new LinearExpr[boardSize];
LinearExpr[] diag2 = new LinearExpr[boardSize];
for (int i = 0; i < boardSize; ++i) {
}

// Create a solver and solve the model.
CpSolver solver = new CpSolver();
SolutionPrinter cb = new SolutionPrinter(queens);
// Tell the solver to enumerate all solutions.
solver.getParameters().setEnumerateAllSolutions(true);
// And solve.
solver.solve(model, cb);

// Statistics.
System.out.println("Statistics");
System.out.println("  conflicts : " + solver.numConflicts());
System.out.println("  branches  : " + solver.numBranches());
System.out.println("  wall time : " + solver.wallTime() + " s");
System.out.println("  solutions : " + cb.getSolutionCount());
}

private NQueensSat() {}
}```

### C#

```// OR-Tools solution to the N-queens problem.
using System;

public class NQueensSat
{
public class SolutionPrinter : CpSolverSolutionCallback
{
public SolutionPrinter(IntVar[] queens)
{
queens_ = queens;
}

public override void OnSolutionCallback()
{
Console.WriteLine(\$"Solution {SolutionCount_}");
for (int i = 0; i < queens_.Length; ++i)
{
for (int j = 0; j < queens_.Length; ++j)
{
if (Value(queens_[j]) == i)
{
Console.Write("Q");
}
else
{
Console.Write("_");
}
if (j != queens_.Length - 1)
Console.Write(" ");
}
Console.WriteLine("");
}
SolutionCount_++;
}

public int SolutionCount()
{
return SolutionCount_;
}

private int SolutionCount_;
private IntVar[] queens_;
}

static void Main()
{
// Constraint programming engine
CpModel model = new CpModel();

int BoardSize = 8;
// There are `BoardSize` number of variables, one for a queen in each
// column of the board. The value of each variable is the row that the
// queen is in.
IntVar[] queens = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
queens[i] = model.NewIntVar(0, BoardSize - 1, \$"x{i}");
}

// Define constraints.
// All rows must be different.

// No two queens can be on the same diagonal.
LinearExpr[] diag1 = new LinearExpr[BoardSize];
LinearExpr[] diag2 = new LinearExpr[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
diag1[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/i);
diag2[i] = LinearExpr.Affine(queens[i], /*coeff=*/1, /*offset=*/-i);
}

// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
SolutionPrinter cb = new SolutionPrinter(queens);
// Search for all solutions.
solver.StringParameters = "enumerate_all_solutions:true";
// And solve.
solver.Solve(model, cb);

Console.WriteLine("Statistics");
Console.WriteLine(\$"  conflicts : {solver.NumConflicts()}");
Console.WriteLine(\$"  branches  : {solver.NumBranches()}");
Console.WriteLine(\$"  wall time : {solver.WallTime()} s");
Console.WriteLine(\$"  number of solutions found: {cb.SolutionCount()}");
}
}```

## Solution using the original CP solver

The following sections present a Python program that solves N-queens using the original CP solver. (However, we recommend using the newer CP-SAT solver)

### Import the libraries

The following code imports the required library.

### Python

```import sys
from ortools.constraint_solver import pywrapcp```

### C++

```#include <cstdint>
#include <cstdlib>
#include <sstream>
#include <vector>

#include "ortools/base/logging.h"
#include "ortools/constraint_solver/constraint_solver.h"```

### Java

```import com.google.ortools.Loader;

### C#

```using System;

### Declare the solver

The following code declares the original CP solver.

### Python

`solver = pywrapcp.Solver("n-queens")`

### C++

`Solver solver("N-Queens");`

### Java

`Solver solver = new Solver("N-Queens");`

### C#

`Solver solver = new Solver("N-Queens");`

### Create the variables

The solver's `IntVar` method creates the variables for the problem as an array named `queens`.

### Python

```# The array index is the column, and the value is the row.
queens = [solver.IntVar(0, board_size - 1, f"x{i}") for i in range(board_size)]```

### C++

```std::vector<IntVar*> queens;
queens.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
queens.push_back(
solver.MakeIntVar(0, board_size - 1, absl::StrCat("x", i)));
}```

### Java

```int boardSize = 8;
IntVar[] queens = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
queens[i] = solver.makeIntVar(0, boardSize - 1, "x" + i);
}```

### C#

```const int BoardSize = 8;
IntVar[] queens = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
queens[i] = solver.MakeIntVar(0, BoardSize - 1, \$"x{i}");
}```

For any solution, `queens[j] = i` means there is a queen in column `j` and row `i`.

### Create the constraints

Here's the code that creates the constraints for the problem.

### Python

```# All rows must be different.

# No two queens can be on the same diagonal.
solver.Add(solver.AllDifferent([queens[i] + i for i in range(board_size)]))
solver.Add(solver.AllDifferent([queens[i] - i for i in range(board_size)]))```

### C++

```// The following sets the constraint that all queens are in different rows.

// All columns must be different because the indices of queens are all
// different. No two queens can be on the same diagonal.
std::vector<IntVar*> diag_1;
diag_1.reserve(board_size);
std::vector<IntVar*> diag_2;
diag_2.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
diag_1.push_back(solver.MakeSum(queens[i], i)->Var());
diag_2.push_back(solver.MakeSum(queens[i], -i)->Var());
}

### Java

```// All rows must be different.

// All columns must be different because the indices of queens are all different.
// No two queens can be on the same diagonal.
IntVar[] diag1 = new IntVar[boardSize];
IntVar[] diag2 = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
diag1[i] = solver.makeSum(queens[i], i).var();
diag2[i] = solver.makeSum(queens[i], -i).var();
}

### C#

```// All rows must be different.

// All columns must be different because the indices of queens are all different.
// No two queens can be on the same diagonal.
IntVar[] diag1 = new IntVar[BoardSize];
IntVar[] diag2 = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
diag1[i] = solver.MakeSum(queens[i], i).Var();
diag2[i] = solver.MakeSum(queens[i], -i).Var();
}

These constraints guarantee the three conditions for the N-queens problem ( queens on different rows, columns, and diagonals).

#### No two queens on the same row

Applying the solver's `AllDifferent` method to `queens` forces the values of `queens[j]` to be different for each `j`, which means that all queens must be in different rows.

#### No two queens on the same column

This constraint is implicit in the definition of `queens`. Since no two elements of `queens` can have the same index, no two queens can be in the same column.

#### No two queens on the same diagonal

The diagonal constraint is a little trickier than the row and column constraints. First, if two queens lie on the same diagonal, one of the following must be true:

• If the diagonal is descending (going from left to right), the row number plus column number for each of the two queens are equal. So `queens(i) + i` has the same value for two different indices `i`.
• If the diagonal is ascending, the row number minus the column number for each of the two queens are equal. In this case, `queens(i) - i` has the same value for two different indices `i`.

So the diagonal constraint is that the values of `queens(i) + i` must all be different, and likewise the values of `queens(i) - i` must all be different, for different `i`.

The code above adds this constraint by applying the `AllDifferent` method to `queens[j]&nbsp;+&nbsp;j` and `queens[j]&nbsp;-&nbsp;j`, for each `i`.

The next step is to create a decision builder, which sets the search strategy for the problem. The search strategy can have a major impact on the search time, due to propagation of constraints, which reduces the number of variable values the solver has to explore. You have already seen an example of this in the 4-queens example.

The following code creates a decision builder using the solver's `Phase` method.

### Python

`db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)`

### C++

```DecisionBuilder* const db = solver.MakePhase(
queens, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);```

### Java

```// Create the decision builder to search for solutions.
final DecisionBuilder db =
solver.makePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);```

### C#

```// Create the decision builder to search for solutions.
DecisionBuilder db = solver.MakePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);```

See Decision builder for details on the input arguments to the `Phase` method.

#### How the decision builder works in the 4-queens example

Let's take a look at how decision builder directs the search in the 4-queens example. The solver begins with `queens[0]`, the first variable in the array, as directed by `CHOOSE_FIRST_UNBOUND`. The solver then assigns `queens[0]` the smallest value that hasn't already been tried, which is 0 at this stage, as directed by `ASSIGN_MIN_VALUE`. This places the first queen in the upper left corner of the board.

Next, the solver selects `queens[1]`, which is now the first unbound variable in `queens`. After propagating the constraints, there are two possible rows for a queen in column 1: row 2 or row 3. The `ASSIGN_MIN_VALUE` option directs the solver to assign `queens[1] = 2`. (If instead, you set `IntValueStrategy` to `ASSIGN_MAX_VALUE`, the solver would assign `queens[1] = 3`.)

You can check that the rest of the search follows the same rules.

### Call the solver and display the results

The following code runs the solver and displays the solution.

### Python

```# Iterates through the solutions, displaying each.
num_solutions = 0
solver.NewSearch(db)
while solver.NextSolution():
# Displays the solution just computed.
for i in range(board_size):
for j in range(board_size):
if queens[j].Value() == i:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()
num_solutions += 1
solver.EndSearch()```

### C++

```// Iterates through the solutions, displaying each.
int num_solutions = 0;

solver.NewSearch(db);
while (solver.NextSolution()) {
// Displays the solution just computed.
LOG(INFO) << "Solution " << num_solutions;
for (int i = 0; i < board_size; ++i) {
std::stringstream ss;
for (int j = 0; j < board_size; ++j) {
if (queens[j]->Value() == i) {
// There is a queen in column j, row i.
ss << "Q";
} else {
ss << "_";
}
if (j != board_size - 1) ss << " ";
}
LOG(INFO) << ss.str();
}
num_solutions++;
}
solver.EndSearch();```

### Java

```int solutionCount = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
System.out.println("Solution " + solutionCount);
for (int i = 0; i < boardSize; ++i) {
for (int j = 0; j < boardSize; ++j) {
if (queens[j].value() == i) {
System.out.print("Q");
} else {
System.out.print("_");
}
if (j != boardSize - 1) {
System.out.print(" ");
}
}
System.out.println();
}
solutionCount++;
}
solver.endSearch();```

### C#

```// Iterates through the solutions, displaying each.
int SolutionCount = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
Console.WriteLine("Solution " + SolutionCount);
for (int i = 0; i < BoardSize; ++i)
{
for (int j = 0; j < BoardSize; ++j)
{
if (queens[j].Value() == i)
{
Console.Write("Q");
}
else
{
Console.Write("_");
}
if (j != BoardSize - 1)
Console.Write(" ");
}
Console.WriteLine("");
}
SolutionCount++;
}
solver.EndSearch();```

Here's the first solution found by the program for an 8x8 board.

```        Q _ _ _ _ _ _ _
_ _ _ _ _ _ Q _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
...91 other solutions displayed...
Statistics
failures: 304
branches: 790
wall time: 5 ms
Solutions found: 92```

You can solve the problem for a board of a different size by passing in N as a command-line argument. For example, `python nqueens_cp.py 6` solves the problem for a 6x6 board.

### The entire program

The complete program is shown below.

### Python

```"""OR-Tools solution to the N-queens problem."""
import sys
from ortools.constraint_solver import pywrapcp

def main(board_size):
# Creates the solver.
solver = pywrapcp.Solver("n-queens")

# Creates the variables.
# The array index is the column, and the value is the row.
queens = [solver.IntVar(0, board_size - 1, f"x{i}") for i in range(board_size)]

# Creates the constraints.
# All rows must be different.

# No two queens can be on the same diagonal.
solver.Add(solver.AllDifferent([queens[i] + i for i in range(board_size)]))
solver.Add(solver.AllDifferent([queens[i] - i for i in range(board_size)]))

db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)

# Iterates through the solutions, displaying each.
num_solutions = 0
solver.NewSearch(db)
while solver.NextSolution():
# Displays the solution just computed.
for i in range(board_size):
for j in range(board_size):
if queens[j].Value() == i:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()
num_solutions += 1
solver.EndSearch()

# Statistics.
print("\nStatistics")
print(f"  failures: {solver.Failures()}")
print(f"  branches: {solver.Branches()}")
print(f"  wall time: {solver.WallTime()} ms")
print(f"  Solutions found: {num_solutions}")

if __name__ == "__main__":
# By default, solve the 8x8 problem.
size = 8
if len(sys.argv) > 1:
size = int(sys.argv[1])
main(size)```

### C++

```// OR-Tools solution to the N-queens problem.
#include <cstdint>
#include <cstdlib>
#include <sstream>
#include <vector>

#include "ortools/base/logging.h"
#include "ortools/constraint_solver/constraint_solver.h"

namespace operations_research {

void NQueensCp(const int board_size) {
// Instantiate the solver.
Solver solver("N-Queens");

std::vector<IntVar*> queens;
queens.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
queens.push_back(
solver.MakeIntVar(0, board_size - 1, absl::StrCat("x", i)));
}

// Define constraints.
// The following sets the constraint that all queens are in different rows.

// All columns must be different because the indices of queens are all
// different. No two queens can be on the same diagonal.
std::vector<IntVar*> diag_1;
diag_1.reserve(board_size);
std::vector<IntVar*> diag_2;
diag_2.reserve(board_size);
for (int i = 0; i < board_size; ++i) {
diag_1.push_back(solver.MakeSum(queens[i], i)->Var());
diag_2.push_back(solver.MakeSum(queens[i], -i)->Var());
}

DecisionBuilder* const db = solver.MakePhase(
queens, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);

// Iterates through the solutions, displaying each.
int num_solutions = 0;

solver.NewSearch(db);
while (solver.NextSolution()) {
// Displays the solution just computed.
LOG(INFO) << "Solution " << num_solutions;
for (int i = 0; i < board_size; ++i) {
std::stringstream ss;
for (int j = 0; j < board_size; ++j) {
if (queens[j]->Value() == i) {
// There is a queen in column j, row i.
ss << "Q";
} else {
ss << "_";
}
if (j != board_size - 1) ss << " ";
}
LOG(INFO) << ss.str();
}
num_solutions++;
}
solver.EndSearch();

// Statistics.
LOG(INFO) << "Statistics";
LOG(INFO) << "  failures: " << solver.failures();
LOG(INFO) << "  branches: " << solver.branches();
LOG(INFO) << "  wall time: " << solver.wall_time() << " ms";
LOG(INFO) << "  Solutions found: " << num_solutions;
}

}  // namespace operations_research

int main(int argc, char** argv) {
int board_size = 8;
if (argc > 1) {
board_size = std::atoi(argv[1]);
}
operations_research::NQueensCp(board_size);
return EXIT_SUCCESS;
}```

### Java

```// OR-Tools solution to the N-queens problem.

/** N-Queens Problem. */
public final class NQueensCp {
public static void main(String[] args) {
// Instantiate the solver.
Solver solver = new Solver("N-Queens");

int boardSize = 8;
IntVar[] queens = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
queens[i] = solver.makeIntVar(0, boardSize - 1, "x" + i);
}

// Define constraints.
// All rows must be different.

// All columns must be different because the indices of queens are all different.
// No two queens can be on the same diagonal.
IntVar[] diag1 = new IntVar[boardSize];
IntVar[] diag2 = new IntVar[boardSize];
for (int i = 0; i < boardSize; ++i) {
diag1[i] = solver.makeSum(queens[i], i).var();
diag2[i] = solver.makeSum(queens[i], -i).var();
}

// Create the decision builder to search for solutions.
final DecisionBuilder db =
solver.makePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

int solutionCount = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
System.out.println("Solution " + solutionCount);
for (int i = 0; i < boardSize; ++i) {
for (int j = 0; j < boardSize; ++j) {
if (queens[j].value() == i) {
System.out.print("Q");
} else {
System.out.print("_");
}
if (j != boardSize - 1) {
System.out.print(" ");
}
}
System.out.println();
}
solutionCount++;
}
solver.endSearch();

// Statistics.
System.out.println("Statistics");
System.out.println("  failures: " + solver.failures());
System.out.println("  branches: " + solver.branches());
System.out.println("  wall time: " + solver.wallTime() + "ms");
System.out.println("  Solutions found: " + solutionCount);
}

private NQueensCp() {}
}```

### C#

```// OR-Tools solution to the N-queens problem.
using System;

public class NQueensCp
{
public static void Main(String[] args)
{
// Instantiate the solver.
Solver solver = new Solver("N-Queens");

const int BoardSize = 8;
IntVar[] queens = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
queens[i] = solver.MakeIntVar(0, BoardSize - 1, \$"x{i}");
}

// Define constraints.
// All rows must be different.

// All columns must be different because the indices of queens are all different.
// No two queens can be on the same diagonal.
IntVar[] diag1 = new IntVar[BoardSize];
IntVar[] diag2 = new IntVar[BoardSize];
for (int i = 0; i < BoardSize; ++i)
{
diag1[i] = solver.MakeSum(queens[i], i).Var();
diag2[i] = solver.MakeSum(queens[i], -i).Var();
}

// Create the decision builder to search for solutions.
DecisionBuilder db = solver.MakePhase(queens, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

// Iterates through the solutions, displaying each.
int SolutionCount = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
Console.WriteLine("Solution " + SolutionCount);
for (int i = 0; i < BoardSize; ++i)
{
for (int j = 0; j < BoardSize; ++j)
{
if (queens[j].Value() == i)
{
Console.Write("Q");
}
else
{
Console.Write("_");
}
if (j != BoardSize - 1)
Console.Write(" ");
}
Console.WriteLine("");
}
SolutionCount++;
}
solver.EndSearch();

// Statistics.
Console.WriteLine("Statistics");
Console.WriteLine(\$"  failures: {solver.Failures()}");
Console.WriteLine(\$"  branches: {solver.Branches()}");
Console.WriteLine(\$"  wall time: {solver.WallTime()} ms");
Console.WriteLine(\$"  Solutions found: {SolutionCount}");
}
}```

## Number of solutions

The number of solutions goes up roughly exponentially with the size of the board:

Board sizeSolutionsTime to find all solutions (ms)
110
200
300
420
5100
640
7403
8929
935235
1072495
112680378
12142002198
137371211628
1436559662427
152279184410701

Many solutions are just rotations of others, and a technique called symmetry breaking can be used to reduce the amount of computation needed. We don't use that here; our solution above isn't intended to be fast, just simple. Of course, we could make it much faster if we wanted to only find one solution instead of all of them: no more than a few milliseconds for board sizes up to 50.

[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]