This is my code now but won\'t print solution does not exist and also prints mor
ID: 3667585 • Letter: T
Question
This is my code now but won't print solution does not exist and also prints more than one solution. I need to fix these two issues. Thanks
#include<stdio.h>
#include<stdlib.h>
#include <unistd.h>
#include<math.h>
int a[20],count=1;
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(" Solution : ");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i]==j)
printf("Q ");
else
printf("- ");
}
printf(" ");
}
}
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;
//clrscr();
printf("Enter the number of Queens ");
scanf("%d",&n);
queen(n);
// printf(" Total solutions=%d",count);
//getch();
}
Explanation / Answer
/* This is a function to print solution */
void printthefinalSolution(int place_board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", place_board[i][j]);
printf(" ");
}
}
/* This is a function to check if a queen can
be placed on place_board[row][col]or not.This function is called when col queens are already placed in columns from 0 to col -1.
Therefore we need to check only left side for
attacking queens */
bool safety(int place_board[N][N], int row, int col)
{
int i, j;
/* In order to check this row on left side */
for (i = 0; i < col; i++)
if (place_board[row][i])
return false;
/*In order to check upper diagonal on left side */
for (i=row, j=col; i>=0 && j>=0; i--, j--)
if (place_board[i][j])
return false;
/* In order to check lower diagonal on left side */
for (i=row, j=col; j>=0 && i<N; i++, j--)
if (place_board[i][j])
return false;
return true;
}
/* A recursive function to solve n queen’s problem
*/
bool solveNQueen(int place_board[N][N], int col)
{
/*The base case: If all queens are placed already
then return true */
if (col >= N)
return true;
/* We will now consider this column and try placing
this queen in all rows one by one over here */
for (int i = 0; i < N; i++)
{
/*To check if queen can be placed on
place_board[i][col] */
if ( safety(place_board, i, col) )
{
/* Now we will place this queen in place_board[i][col] */
place_board[i][col] = 1;
/* we will now use recursion to place rest of the queens */
if ( solveNQueen(place_board, col + 1) )
return true;
/* However if by placing queen in place_board[i][col]
doesn't lead to a solution, then
remove queen from place_board[i][col] */
place_board[i][col] = 0; // This is known as backtracking
}
}
/* If queen can not be placed in any row in
this column col then return false */
return false;
}
/* This function solves the N Queen problem using
Backtracking. It mainly uses solveNQueen() to
solve the problem. It returns false if queens
cannot be placed, otherwise return true and
prints placement of queens in the form of 1s.
*/
bool solveNQqueenproblem()
{
int place_board[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if ( solveNQueen(place_board, 0) == false )
{
printf(" The solution does not exist in this case");
return false;
}
printthefinalSolution(place_board);
return true;
}
//This is the driver program to test above function
int main()
{
solveNQqueenproblem();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.