N-Queens

Construct a magic square nxn (using the numbers 1 to n2) and place n queens only on these cells which contain prime numbers, such that no queen can take any other queen.

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
.


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 nwith 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;
}
}
}


Optimal Queens is a classic problem in mathematics and computer science.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s