N-queens problem

From Fōrmulæ wiki
Jump to: navigation, search

This page is the answer to the task N-queens problem in the Rosetta Code.

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

NQueensCode.png

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

NQueensResult8.png

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.

NQueensBoard8.png

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

NQueensBoardResult8.png