# N-queens problem

## Contents

### Description (from Rosetta Code)

 Solve the Eight queens puzzle. You can extend the problem to solve the puzzle with a board of size NxN. For the number of solutions for small values of N, see oeis.org sequence A170.

### Program

The same program when the flowchart package visualization is selected. Click/tap to enlarge

#### Explanation

This program:

• Is able to calculate solution for chessboards of any size.
• It does not calculate rotated or reflected solutions.

This is an example of backtracking.

##### Data structures

If a solution existed, then there must exist a queen in every row/column of the chessboard, because of:

• There cannot be more than one queen, because they would attack each other.
• There cannot be a row/column with no queen, because at the end we would be using less than the n queens.

Every position of the Pos array, initially set to zeroes, represents every row of a chessboard, and the valued is the column of such that row.

The Results array, initially empty, simply accumulates every calculated solution.

##### Main code

The main functionality is coded in the TestRow function:

Given a row, it goes through the zero position (out of the chessboard) to the right.

In every position it verifies:

• If the queen is under attack, it moves it to the right.
• If the queen is not under attack, it does the following:
• If the row is the last of the chessboard, a solution has been found, so the Pos array is copied to the Results array.
• If the row is not the last of the chessboard, the function calls itself (it is a recursive function) with the next row.
##### Detecting attacks

The IsAttacked function detects if a queen in a given position is attacked by the queens of previous rows.

### Results

The following shows the solutions for an 8 x 8 chessboard. There are 92 of them

### Showing results as boards

The following is a function to show the results as boards. It is not intended to show the alternate colors on a chessboard, but the position of the queens (in blue) over empty squares (in gray) of the board.

The following is the result. Only the first are shown.