N queens
Problem description
Place n queens on a n sized chessboard so that no two queens can attack each other. The most common n queens puzzle is the eight queens puzzle, with n = 8:
Constraints:

Use a chessboard of n columns and n rows.

Place n queens on the chessboard.

No two queens can attack each other. A queen can attack any other queen on the same horizontal, vertical or diagonal line.
This documentation heavily uses the four queens puzzle as the primary example.
A proposed solution could be:
The above solution is wrong because queens A1
and B0
can attack each other (so can queens B0
and D0
). Removing queen B0
would respect the "no two queens can attack each other" constraint, but would break the "place n queens" constraint.
Below is a correct solution:
All the constraints have been met, so the solution is correct.
Note that most n queens puzzles have multiple correct solutions. We will focus on finding a single correct solution for a given n, not on finding the number of possible correct solutions for a given n.
Problem size
4queens has 4 queens with a search space of 256.
8queens has 8 queens with a search space of 10^7.
16queens has 16 queens with a search space of 10^19.
32queens has 32 queens with a search space of 10^48.
64queens has 64 queens with a search space of 10^115.
256queens has 256 queens with a search space of 10^616.
The implementation of the n queens example has not been optimized because it functions as a beginner example. Nevertheless, it can easily handle 64 queens. With a few changes it has been shown to easily handle 5000 queens and more.
Domain model
This example uses the domain model to solve the four queens problem.

Creating a Domain Model A good domain model will make it easier to understand and solve your planning problem.
This is the domain model for the n queens example:
public class Column { private int index; // ... getters and setters }
public class Row { private int index; // ... getters and setters }
public class Queen { private Column column; private Row row; public int getAscendingDiagonalIndex() {...} public int getDescendingDiagonalIndex() {...} // ... getters and setters }

Calculating the Search Space.
A
Queen
instance has aColumn
(for example: 0 is column A, 1 is column B, …) and aRow
(its row, for example: 0 is row 0, 1 is row 1, …).The ascending diagonal line and the descending diagonal line can be calculated based on the column and the row.
The column and row indexes start from the upper left corner of the chessboard.
public class NQueens { private int n; private List<Column> columnList; private List<Row> rowList; private List<Queen> queenList; private SimpleScore score; // ... getters and setters }

Finding the Solution
A single
NQueens
instance contains a list of allQueen
instances. It is the solution implementation which is supplied to, solved by, and retrieved from theSolver
.
Notice that in the four queens example, NQueens’s getN()
method will always return four.
A solution  Queen  columnIndex  rowIndex  ascendingDiagonalIndex (columnIndex + rowIndex)  descendingDiagonalIndex (columnIndex  rowIndex) 

A1 
0 
1 
1 (**) 
1 

B0 
1 
0 (*) 
1 (**) 
1 

C2 
2 
2 
4 
0 

D0 
3 
0 (*) 
3 
3 
When two queens share the same column, row or diagonal line, such as (*) and (**), they can attack each other.