1. What is the smallest magic square (n) having solution?

2. Get one solution for the next three larger magic squares (n+1, n+2 & n+3)

3. Redo the exercises 1 & 2 with one additional condition: “*one of the diagonals should also contain prime numbers only*“.

# A survey of known results and research areas for n-queens

- Under an Elsevier user license

## Abstract

In this paper we survey known results for the n-queens problem of placing nnonattacking queens on an n×n chessboard and consider extensions of the problem, e.g. other board topologies and dimensions. For all solution constructions, we either give the construction, an outline of it, or a reference. In our analysis of the modular board, we give a simple result for finding the intersections of diagonals. We then investigate a number of open research areas for the problem, stating several existing and new conjectures. Along with the known results for n-queens that we discuss, we also give a history of the problem. In particular, we note that the first proof that n nonattacking queens can always be placed on an n×n board for n>3 is by E. Pauls, rather than by W. Ahrens who is typically cited. We have attempted in this paper to discuss all the mathematical literature in all languages on the n-queens problem. However, we look only briefly at computational approaches.

## Keywords

- n-queens problem;
- Modular n-queens problem;
- Queens graph;
- Chessboard graph;
- Chessboard problems

The **eight queens puzzle** is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general ** n-queens problem** of placing

*n*queens on an

*n*×

*n*chessboard, where solutions exist for all natural numbers

*n*with the exception of

*n*=2 and

*n*=3.

^{[1]}

N-Queens is an extension of the 8-Queens puzzle, both of which make use of trial-and-error methods and backtracking algorithms. Carl F. Gauss introduced the problem in 1850, but he was unable to completely solve it. The 8-Queens problem is stated as follows: Eight queens are to be placed on a chess board in such a way that no queen checks against any other queen. In other words, there can only be one queen per row, column, and diagonal.

### Niklaus Wirth’s algorithm

The data representation is as follows:

var x : |
array [1..n] of integer; |

a : |
array [1..n] of boolean; |

b : |
array [2..2n] of boolean; |

c : |
array [1-n..n-1] of boolean; |

where

*x*[i] denotes the position of the queen in the ith column;*a*[j] means no queen lies in the jth row;*b*[k] means no queen occupies the kth minor diagonal;*c*[k] means no queen occupies the kth major diagonal.

The following pseudocode explains how it works:

`function tryConfig(i: integer) {`

for j <- 1 to n do {

if safe then {

select jth candidate;

set queen;

if i < n then

tryConfig(i+1);

else

record solution;

remove queen;

}

}

}