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

.

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

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

""" 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 size | Solutions | Time to find all solutions (ms) |
---|---|---|

1 | 1 | 0 |

2 | 0 | 0 |

3 | 0 | 0 |

4 | 2 | 0 |

5 | 10 | 0 |

6 | 4 | 0 |

7 | 40 | 3 |

8 | 92 | 9 |

9 | 352 | 35 |

10 | 724 | 95 |

11 | 2680 | 378 |

12 | 14200 | 2198 |

13 | 73712 | 11628 |

14 | 365596 | 62427 |

15 | 2279184 | 410701 |

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.