Determine number of ways to place n queens on an n x n chess board so that no queen threatens any other.
Number rows and columns of the board by 1...n. Use an array x[1...n], with x[i] containing the column number j of the queen in row i.
Obviously, in any solution to the n-Queens problem, there is exactly one queen in each column. So we will represent our possible solutions using an array x[1.. n], where x[i] indicates the square in column i that contains a queen, or 0 if no queen has yet been placed in column i. To find a solution, we will put queens on the board row by row, starting at the top.
A partial solution is an array x[1.. n] whose first r - 1 entries are positive and whose last n - r + 1 entries are all zeros, for some integer r. The following recursive algorithm recursively enumerates all complete n-queens solutions that are consistent with a given partial solution. The input parameter r is the first empty row. Thus, to compute all n-queens solutions with no restrictions, we would call NQueens(1, n).
Algorithm
This algorithm is called with parameters k=1 and n, i.e. NQueens(1, n).
Algorithm
Algorithm NQueens (k, n)
{
for i:=1 to n do
if Place(k,i) then
{
x[k]:=i;
if (k=n) then
write (x[1:n])
else
NQueens(k+1, n);
}
return true;
}
The following function returns true if a queen can be placed at [k, i] position. Here, x[] is a global array whose first (k-1) values have been set. Abs(r) returns the absolute value of r.
Algorithm
Algorithm Place (k, i)
{
for j:=1 to k-1 do
if ((x[j]=i) or (Abs(x[j]-i)=Abs(j-k)))
return false;
return true;
}
Implementation of N-Queens Problem using C Programming Language
#include <stdio.h>
#include <math.h>
int x[16], count;
void nqueen(int row, int n);
int place(int row, int column);
void print(int n);
int main()
{
int n, i, j;
printf("\nEnter number of Queens:");
scanf("%d", &n);
nqueen(1, n);
return 0;
}
void nqueen(int row,int n)
{
int column;
for(column=1;column <= n;++column)
{
if(place(row,column))
{
x[row]=column;
if(row==n)
print(n);
else
nqueen(row+1,n);
}
}
}
int place(int row,int column)
{
int i;
for(i = 1; i <= row - 1; ++i)
{
if(x[i] == column)
return 0;
else
if(abs(x[i]-column)==abs(i-row))
return 0;
}
return 1;
}
void print(int n)
{
int i, j;
printf("\n %d:\n", ++count);
for(i = 1; i <= n; ++i)
printf("\t%d", i);
for(i = 1; i <= n; ++i)
{
printf("\n%d", i);
for(j = 1; j <= n; ++j)
{
if(x[i] == j)
printf("\tQ");
else
printf("\t-");
}
}
}
Posts
No comments:
Post a Comment