The N-queens Problem

Overview

Chessboard queens 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 a solution to the 4 queens problem.

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

On this page, you'll see how CP solvers use propagation and backtracking to solve problems, and then see a short Python program that solves the N queens problem with Google's constraint programming solver.

Propagation and backtracking

One common pattern in CP solvers is an alternation between propagation and backtracking. Propagation consists of taking some constraint—which might be a constraint of the original problem, or a constraint learned or hypothesized along the way—and applying it to variables.

Backtracking occurs when the solver, having made a wrong guess, reverts back to an earlier state and tries something else.

Let's see how these might work with the 4 queens problem. 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 our 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! (There are clearly other symmetrical solutions: just rotate the board.) 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.

Solving N-queens

The N-queens problem is ideally suited to constraint programming. In this section we'll walk through a short Python program that uses OR-Tools to solve N-queens for any value of N.

There are many ways to structure a problem like this. We'll focus on minimizing the length of the Python program:

  • Our variables will the queens, stored in an array with the index representing the row, and the value representing the column.
  • Each solution will be a filled-in array.
  • Our constraints will be:
    • No two values of the array can be the same (or else two queens would be on the same column)
    • The values plus the indices should be all different. Likewise, the values minus the indices should be all different. (This is a complicated but efficient way to ensure that no two queens are on the same diagonal.)

To see the program in its entirety, select the "Full program" tab below. The main steps are as follows:

  • Create the solver with pywrapcp.Solver.
  • Define our variables (as an array of solver.IntVar).
  • Add solver.AllDifferent constraints with solver.Add.
  • Tell the solver what to solve with solver.Phase.
  • Iterate through the solutions with solver.NewSearch, solver.NextSolution, and solver.EndSearch.
Setup
from ortools.constraint_solver import pywrapcp

def main(N):
  # Creates the solver.
  solver = pywrapcp.Solver("n-queens")
Variables
  # Creates the variables.
  # The array index is the column, and the value is the row.
  queens = [solver.IntVar(0, N - 1, "x%i" % i) for i in range(N)]
Constraints
  # Creates the constraints.

  # All rows must be different.
  solver.Add(solver.AllDifferent(queens))

  # All columns must be different because the indices of queens are all different.

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

Solution
  solver.NewSearch(db)

  # Iterates through the solutions, displaying each.
  num_solutions = 0

  while solver.NextSolution():
    # Displays the solution just computed.
    for i in range(N):
      for j in range(N):
        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()
Full program
"""
  OR-tools solution to the N-queens problem.
"""
from __future__ import print_function
import sys
from ortools.constraint_solver import pywrapcp

def main(N):
  # 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, N - 1, "x%i" % i) for i in range(N)]
  # Creates the constraints.

  # All rows must be different.
  solver.Add(solver.AllDifferent(queens))

  # All columns must be different because the indices of queens are all different.

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

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

  # Iterates through the solutions, displaying each.
  num_solutions = 0

  while solver.NextSolution():
    # Displays the solution just computed.
    for i in range(N):
      for j in range(N):
        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()

  print()
  print("Solutions found:", num_solutions)
  print("Time:", solver.WallTime(), "ms")

# By default, solve the 8x8 problem.
N = 8

if __name__ == "__main__":
  if len(sys.argv) > 1:
    N = int(sys.argv[1])
  main(N)

If you call this program queens.py and you're in the top level or-tools directory, you can run this code as follows:

$ PYTHONPATH=src python queens.py 8
_ _ _ Q _ _ _ _
_ Q _ _ _ _ _ _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ _ _ _ _ Q _ _
Q _ _ _ _ _ _ _
_ _ Q _ _ _ _ _
_ _ _ _ _ _ Q _

...91 other solutions displayed...

Solutions found: 92
Time: 9 ms

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.

Send feedback about...

Optimization
Optimization