n QUEENS PROBLEM USING BACKTRACKING

/*This program is to implement n-queens problem using backtracking*/
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<process.h>

int board[20];
int count;
void main()
{
int n,i,j;
void queen(int row, int n);
clrscr();
printf("
Program for queens using backtracking");
printf("Enter number of queens ");
scanf("%d",&n);
queen(1,n);                                      //trace using backtrack
getch();
 }


/*This function is for printing the solution to n-queens problem*/
void print_board(int n)
{
int i,j;
printf("

solution %d:

",++count);
//number of solution
for(i=1;i<=n;i++)
{
printf(" %d",i);
}
for(i=1;i<=n;i++)
{
printf("

%d",i);
for(j=1;j<=n;j++)        //for n*n board
{
if(board[i]==j)
printf(" Q");   //Queen at i,j position
else
printf(" -");   //empty slot
}
}
printf("
Press any key to continue.....");
getch();
}
/*This function is for checking for the conflicts.If there is no conflict for the desired position it returns 1 otherwise it returns 0*/
int place(int row ,int column)
{
int i;
for(i=1;i<=row-1;i++)
{
//checking for column and diagonal conflicts 
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
}
//no conflicts hence Queen can be placed
return 1;
}




/*By this function we try the next free slot and 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_board(n);    //printing the board configuration
else                     //try queen with next position
queen(row+1,n);
}
}
}

OUTPUT
Program for n-Queens using backtracking
Enter number of Queens 4

Solution 1:
      1     2     3     4
1    -     Q     -     -
2    -     -      -    Q
3   Q     -      -     -
4    -      -     Q    -

Press any key to continue........


Categories: , , , ,

Leave a Reply