The N Queens puzzle is the problem of placing eight chess queens on an n×n 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 number of rotationally and reflectively distinct solutions for the first few N are 1, 0, 0, 2, 10, 4, 40, 92,...
Example: The graphical demonstrations for the 8 queens problem:
Method 1:
#include<stdio.h>
#include<math.h>
int
board[20],count;
int
main(){
int
n,i,j;
void
queen(int row,int n);
printf("****
N Queens Problem Solved Using Backtracking ****");
printf("\n\n\tEnter
The Number Of Queens: ");
scanf("%d",&n);
queen(1,n);
printf("\n\n\nTotal
Solutions = %d\n\n",count);
return
0;
}
//function
for printing the solution
void
print(int n) {
int
i,j;
printf("\n\nSolution
%d: ",++count);
for(i=1;i<=n;++i){
printf("\n\n");
for(j=1;j<=n;++j)
{ //for nxn board
if(board[i]==j)
printf("\tQ");
//queen at i,j position
else
printf("\t.");
//empty slot
}}}
/*
funtion to check conflicts if no conflict for desired postion returns 1
otherwise returns 0 */
int
place(int row,int column) {
int
i;
for(i=1;i<=row-1;++i){
//checking
column and digonal conflicts
if(board[i]==column)
return
0;
else
if(abs(board[i]-column)==abs(i-row))
return
0;
}
return
1; //no conflicts
}
//function
to check for proper positioning of queen
void
queen(int row,int n) {
int
column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column;
//no conflicts so place queen
if(row==n)
//dead end
print(n);
//printing the board configuration
else
//try queen with next position
queen(row+1,n);
}}}
Method 2:
#include<stdio.h>
#include<conio.h>
#include<math.h>
int
a[30],count=0;
int
place(int pos) {
int
i;
for(i=1;i<pos;i++)
{
if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))
return
0;
}
return
1;
}
void
print_sol(int n) {
int
i,j;
count++;
printf("\n\nSolution
%d: ",count);
for(i=1;i<=n;i++)
{
printf("\n\n");
for(j=1;j<=n;j++)
{
if(a[i]==j)
printf("\tQ");
else
printf("\t.");
}}}
void
queen(int n) {
int
k=1;
a[k]=0;
while(k!=0){
a[k]=a[k]+1;
while((a[k]<=n)&&!place(k))
a[k]++;
if(a[k]<=n)
{
if(k==n)
print_sol(n);
else
{
k++;
a[k]=0;
}}
else
k--;
}}
void
main() {
int
i,n;
printf("*****
N Queens Problem *****");
printf("\n\nEnter
The Number Of Queens: ");
scanf("%d",&n);
queen(n);
printf("\n\nTotal
Solutions = %d ",count);
getch();
}
Method 3:
#include
<stdio.h>
int
is_safe(int rows[5], int x, int y) {
int
i;
if
(y == 0)
return
1;
for
(i=0; i < y; ++i) {
if
(rows[i] == x || rows[i] == x + y - i || rows[i] == x - y +i)
return
0;
}
return
1;
}
void
putboard(int rows[5]){
static
int s = 0;
int
x, y;
printf("\nSolution
#%d:\n-----------------------\n", ++s);
for
(y=0; y < 5; ++y) {
for
(x=0; x < 5; ++x)
printf(x
== rows[y] ? "| Q " : "|
");
printf("|\n-----------------------\n");
}}
void
queens_helper(int rows[5], int y) {
int
x;
for
(x=0; x < 5; ++x) {
if
(is_safe(rows, x, y)) {
rows[y]
= x;
if
(y == 4)
putboard(rows);
else
queens_helper(rows,
y+1);
}}}
int
main() {
printf("****
N Queens Problem Solved Using Backtracking Depth First Search (DFS)
****\n");
int
rows[5];
queens_helper(rows,
0);
return
0;
}