Like us on google+

Wednesday, 21 May 2014

Widgets

Nqueen Problem Iterative Approach(Backtracking).

#include<stdio.h>
void print(int x[],int n);
void queen(int n);
int place(int x[],int k);

int main()
{

printf("enter the number of queens\n");
int n;
scanf("%d",&n);
queen(n);
}


void queen(int n)
{
int x[10]; // array for holding the queen positions

int count=0; // number of solns

int k=1; // select frst queen

x[k]=0; // not placed on the chess board

while(k!=0) // while queen has been selected
{
x[k]+=1; //place it
while(x[k]<=n && !place(x,k))
{
x[k]+=1; // place in the next column
}


if(x[k]<=n) // queen successfully placed
{
if(k==n)
{
count++;
printf("soln %d is\n",count);
print(x,n);
}
else
{
k++; // select the next queen
x[k]=0; // but do not place
}
}
else
{
k--;
}
}
}



int place(int x[],int k)
{
int i;
for(i=1;i<k;i++)
{
if(x[i]==x[k] || i-x[i]==k-x[k] || i+x[i]==k+x[k])
return 0; // cannot be placed
}
return 1;// kth queen can be placed successfully
}

void print(int x[],int n)
{
int i,j;
char c[10][10];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
c[i][j]='X';


//place the queens on chess board
for(i=1;i<=n;i++)
{
c[i][x[i]]='Q';
}

//displaying
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%c",c[i][j]);
}
printf("\n");
}

}
------------------------------------------------------------------------------------------------------
OUTPUT:
enter the number of queens
4
soln 1 is
XQXX
XXXQ
QXXX
XXQX

soln 2 is
XXQX
QXXX
XXXQ
XQXX

SHARE THIS POST   

  • Facebook
  • Twitter
  • Myspace
  • Google Buzz
  • Reddit
  • Stumnleupon
  • Delicious
  • Digg
  • Technorati
About us:
Hi guys Sandesh and Rajesh here ... studing engineering in PESIT started this blog as a google contest and also we love blogging ...Hope u like it ...Encourage us by liking us on g+... Any queries dont hesitate to ask Read More →

0 comments: