NQueens
The nqueens problem is a classic combinatorial problem. It is required to place n queens on an n×n chess board so that no two queens threaten each other. Therefore no two queens can be on the same row, column or diagonal. There must be a queen on each column and all their row numbers must differ so a solution can be represented as a permutation of the rows. (Not all permutations are solutions.)

 
NQueens Examples (N=5). 

Note that not every permutation is a solution. A permutation generator can be turned into an nqueens solver by adding tests to check diagonals.
procedure Queens(unused, board, col, N) if col > N then print board else{ col <= N } for each row in unused do var safe := true; for c in 1..col1 do  safety check of if row = board[c]+colc  diag... or row = board[c]col+c then  ...onals safe := false; break end if end for; if safe then board[col] := row; Queens(unused{row}, board, col+1, N) <recursion end if end for end if end Queens  Queens({1..n}, board, 1, n) <initial call 
This program has been modified in a simple way from the permutation generator. The identifiers have been changed to reflect chess terminology. It is assumed that a partial solution, board[1..col1], is safe and an attempt is made to place a queen in column col. If this is impossible the routine returns. If it is possible and the new queen threatens no previous queen then the extended solution is safe and a recursive call is made to place the remaining queens. The process succeeds when all queens are placed. For all n greater than or equal to four there are solutions and in fact more than one solution for each value of n.
A search for solutions to a combinatorial problem carried out in this way is known as backtracking. This comes from the way that partial solutions are extended, backing up at blind alleys where the constraints cannot be satisfied, until one or more complete solutions are found.
Notes
 Although the nqueens problem might seem like just a toy puzzle, it is often used as an example of a Constraint Satisfaction problem because it is easy to state, and...
 ...it is related to Latin Squares and to Knut Vik Designs, which are definitely not toy problems, and have applications in statistics.
 There are variations on the nqueens problems, e.g.
 make the board wraparound (be a torus),
 superqueens  can move on generalised diagonals.
 Also see solutions by continuations [All88] and by circular programs [All89, All93].
References
 [All88] L. Allison, 'Some Applications of Continuations',
Computer Journal, 31(1), pp.911,
doi:10.1093/comjnl/31.1.9,
February 1988.
 All89] L. Allison, 'Circular Programs and SelfReferential Structures',
Software Practice and Experience, 19(2), pp.99109,
doi:10.1002/spe.4380190202,
February 1989.
 [All93] L. Allison, 'Applications of Recursively Defined Data Structures', Australian Computer Jurnal, 25(1), pp.1420, [arxiv:2206.12795, February 1993.