The N-queens Problem  |  OR-Tools  |  Google for Developers (2024)

In the following sections, we'll illustrate constraint programming (CP) by acombinatorial problem based on the game of chess. In chess, a queen can attackhorizontally, 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 possiblesolutions, rather than one optimal solution, which makes it a natural candidatefor constraint programming.The following sections describe the CP approach to the N-queens problem, andpresent programs that solve it using both the CP-SAT solver and the original CPsolver.

CP approach to the N-queens problem

A CP solver works by systematically trying allpossible assignments of values to the variables in a problem, to find thefeasible solutions. In the 4-queens problem, the solver starts at the leftmostcolumn and successively places one queen in each column, at a location that isnot 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, theconstraints add restrictions on the possible values of the unassignedvariables. These restrictions propagate to future variable assignments.For example, in the 4-queens problem, each time the solver places a queen, itcan'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 ofvariable values the solver must explore.
• Backtracking occurs when either the solver can't assign a value to the nextvariable, due to the constraints, or it finds a solution. In either case, thesolver backtracks to a previous stage and changes the value of the variable atthat 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 tosolve the 4-queens problem.

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

Given this hypothesis, what constraints can we propagate? One constraint is thatthere can be only one queen in a column (the gray Xs below), and anotherconstraint 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 asecond queen on one of the available remaining squares. Our solver might decideto place in it the first available square in the second column:

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

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

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

Since there can be no queen in the corner, the solver moves the first queen downby 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 findingthe first solution, it would end here. Otherwise, it would backtrack again andplace 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 thissection we'll walk through a short Python program that uses the CP-SAT solver tofind all solutions to the problem.

Import the libraries

The following code imports the required library.

import sysimport timefrom ortools.sat.python import cp_model

#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"

import com.google.ortools.Loader;import com.google.ortools.sat.CpModel;import com.google.ortools.sat.CpSolver;import com.google.ortools.sat.CpSolverSolutionCallback;import com.google.ortools.sat.IntVar;import com.google.ortools.sat.LinearExpr;

using System;using Google.OrTools.Sat;

Declare the model

The following code declares the CP-SAT model.

model = cp_model.CpModel()

CpModelBuilder cp_model;

CpModel model = new CpModel();

 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. model.AddAllDifferent(queens); // 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); } model.AddAllDifferent(diag1); model.AddAllDifferent(diag2); // 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.

# 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)]

// 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)));}

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);}

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.

# All rows must be different.model.add_all_different(queens)# 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))

// The following sets the constraint that all queens are in different rows.cp_model.AddAllDifferent(queens);// 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);}cp_model.AddAllDifferent(diag_1);cp_model.AddAllDifferent(diag_2);

// All rows must be different.model.addAllDifferent(queens);// 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.newBuilder().add(queens[i]).add(i).build(); diag2[i] = LinearExpr.newBuilder().add(queens[i]).add(-i).build();}model.addAllDifferent(diag1);model.addAllDifferent(diag2);

// All rows must be different.model.AddAllDifferent(queens);// 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);}model.AddAllDifferent(diag1);model.AddAllDifferent(diag2);

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

Let's see how these constraints guarantee the three conditions for the N-queensproblem (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 ofqueens[j] to be different for each j, which means that all queens must be indifferent 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 bein 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 conditionsmust 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 indicesj.
• 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 descendingdiagonal. Which condition corresponds to ascending and which to descendingdepends on how you order the rows and columns. As mentioned in theprevious section, the ordering has no effect on the set ofsolutions, just on how you visualize them.

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

To apply the AddAllDifferent method to queens(j) + j, we put the N instancesof 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)model.Add(q1 == queens[j] + j)

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 eachnew solution as the solver finds it. The following code creates a solutionprinter.

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()

int num_solutions = 0;Model model;model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) { 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++;}));

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 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 thePython 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 vcorresponds to one of the eight entries of queens. This prints a solution inthe following form: x0 = queens(0) x1 = queens(1) ... x7 = queens(7) wherexi 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.

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

// Tell the solver to enumerate all solutions.SatParameters parameters;parameters.set_enumerate_all_solutions(true);model.Add(NewSatParameters(parameters));const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);LOG(INFO) << "Number of solutions found: " << num_solutions;

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);

// 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 acommand-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.

"""OR-Tools solution to the N-queens problem."""import sysimport timefrom ortools.sat.python import cp_modelclass 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. model.add_all_different(queens) # 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)

// 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. cp_model.AddAllDifferent(queens); // 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); } cp_model.AddAllDifferent(diag_1); cp_model.AddAllDifferent(diag_2); int num_solutions = 0; Model model; model.Add(NewFeasibleSolutionObserver([&](const CpSolverResponse& response) { 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); model.Add(NewSatParameters(parameters)); 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_researchint 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;}

package com.google.ortools.sat.samples;import com.google.ortools.Loader;import com.google.ortools.sat.CpModel;import com.google.ortools.sat.CpSolver;import com.google.ortools.sat.CpSolverSolutionCallback;import com.google.ortools.sat.IntVar;import com.google.ortools.sat.LinearExpr;/** 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) { Loader.loadNativeLibraries(); // 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. model.addAllDifferent(queens); // 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.newBuilder().add(queens[i]).add(i).build(); diag2[i] = LinearExpr.newBuilder().add(queens[i]).add(-i).build(); } model.addAllDifferent(diag1); model.addAllDifferent(diag2); // 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() {}}

// OR-Tools solution to the N-queens problem.using System;using Google.OrTools.Sat;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. model.AddAllDifferent(queens); // 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); } model.AddAllDifferent(diag1); model.AddAllDifferent(diag2); // 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 theoriginal CP solver.(However, we recommend using the newer CP-SAT solver)

Import the libraries

The following code imports the required library.

import sysfrom ortools.constraint_solver import pywrapcp

#include <cstdint>#include <cstdlib>#include <sstream>#include <vector>#include "ortools/base/logging.h"#include "ortools/constraint_solver/constraint_solver.h"

import com.google.ortools.Loader;import com.google.ortools.constraintsolver.DecisionBuilder;import com.google.ortools.constraintsolver.IntVar;import com.google.ortools.constraintsolver.Solver;

using System;using Google.OrTools.ConstraintSolver;

Declare the solver

The following code declares the original CP solver.

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

Solver solver("N-Queens");

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

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

Create the variables

The solver's IntVar method creates the variables for the problem as an arraynamed queens.

# 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)]

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)));}

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

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 rowi.

Create the constraints

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

# All rows must be different.solver.Add(solver.AllDifferent(queens))# 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)]))

// The following sets the constraint that all queens are in different rows.solver.AddConstraint(solver.MakeAllDifferent(queens));// 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());}solver.AddConstraint(solver.MakeAllDifferent(diag_1));solver.AddConstraint(solver.MakeAllDifferent(diag_2));

// All rows must be different.solver.addConstraint(solver.makeAllDifferent(queens));// 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();}solver.addConstraint(solver.makeAllDifferent(diag1));solver.addConstraint(solver.makeAllDifferent(diag2));

// All rows must be different.solver.Add(queens.AllDifferent());// 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();}solver.Add(diag1.AllDifferent());solver.Add(diag2.AllDifferent());

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 indifferent 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 bein 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 pluscolumn number for each of the two queens are equal. So queens(i) + i has thesame value for two different indices i.
• If the diagonal is ascending, the row number minus the column number for eachof the two queens are equal. In this case, queens(i) - i has the same valuefor two different indices i.

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

The code above adds this constraint by applying theAllDifferentmethod to queens[j] + j and queens[j] - j, for each i.

Add the decision builder

The next step is to create a decision builder, which sets the search strategyfor 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 valuesthe solver has to explore. You have already seen an example of this in the4-queens example.

The following code creates a decision builder using the solver'sPhasemethod.

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

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

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

// 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 theinput 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 the4-queens example.The solver begins with queens[0], the first variable in the array, as directedby CHOOSE_FIRST_UNBOUND. The solver then assigns queens[0] the smallestvalue that hasn't already been tried, which is 0 at this stage, as directed byASSIGN_MIN_VALUE. This places the first queen in the upper left corner of theboard.

Next, the solver selects queens[1], which is now the first unbound variable inqueens. After propagating the constraints, there are two possible rows for aqueen in column 1: row 2 or row 3. The ASSIGN_MIN_VALUE option directs thesolver to assign queens[1] = 2. (If instead, you set IntValueStrategy toASSIGN_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.

# Iterates through the solutions, displaying each.num_solutions = 0solver.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 += 1solver.EndSearch()

// 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();

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();

// 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 acommand-line argument. For example, python nqueens_cp.py 6 solves the problemfor a 6x6 board.

The entire program

The complete program is shown below.

"""OR-Tools solution to the N-queens problem."""import sysfrom ortools.constraint_solver import pywrapcpdef 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. solver.Add(solver.AllDifferent(queens)) # 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)

// 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. solver.AddConstraint(solver.MakeAllDifferent(queens)); // 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()); } solver.AddConstraint(solver.MakeAllDifferent(diag_1)); solver.AddConstraint(solver.MakeAllDifferent(diag_2)); 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_researchint 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;}

// OR-Tools solution to the N-queens problem.package com.google.ortools.constraintsolver.samples;import com.google.ortools.Loader;import com.google.ortools.constraintsolver.DecisionBuilder;import com.google.ortools.constraintsolver.IntVar;import com.google.ortools.constraintsolver.Solver;/** N-Queens Problem. */public final class NQueensCp { public static void main(String[] args) { Loader.loadNativeLibraries(); // 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. solver.addConstraint(solver.makeAllDifferent(queens)); // 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(); } solver.addConstraint(solver.makeAllDifferent(diag1)); solver.addConstraint(solver.makeAllDifferent(diag2)); // 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() {}}

// OR-Tools solution to the N-queens problem.using System;using Google.OrTools.ConstraintSolver;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. solver.Add(queens.AllDifferent()); // 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(); } solver.Add(diag1.AllDifferent()); solver.Add(diag2.AllDifferent()); // 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:

Many solutions are just rotations of others, and a technique called symmetrybreaking can be used to reduce the amount of computation needed. We don't usethat 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 ofall of them: no more than a few milliseconds for board sizes up to 50.