Im trying N queens Problem by backtracking. My code doesnt give output a Q in last column . Why So ??
#include
#include<stdio.h>
#define n 8
using namespace std;
int abs(int x)
{
if(x<0)
x=-x;
return x;
}
bool is_safe(char sol[n][n],int x,int y)
{
if(x>=0&&n>x&&y>=0&&n>y)
{
// check rows
for(int i=0;i<n;i++)
{
if(sol[x][i]=='Q')
return false;
}
// diagonals checking
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(abs(i+j)==abs(x+y) || abs(i-j)==abs(x-y))
{
if(sol[i][j]=='Q')
return false;
}
}
}
return true;
}
// Printing Board
void print_board(char sol[n][n])
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf(" %c ",sol[i][j]);
printf("\n");
}
}
bool recursive_function(char board[n][n],int column);
bool solve_N_Queens()
{
char board[n][n];
// Initialise
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
board[i][j]='*';
if(recursive_function(board,0)==false)
{printf("No Solution exists !!!"); return false;}
else
{ printf("\n\n");
print_board(board);
return true;}
}
bool recursive_function(char board[n][n],int column)
{
if(column==n)
return true;
printf("%d",column);
int row=0;
for(row=0;row<n;row++)
{
if(is_safe(board,row,column))
{
board[row][column]='Q';
if(recursive_function(board,column+1))
return true;
else
board[row][column]='*';
}
}
return false;
}
int main()
{
solve_N_Queens();
return 0;
}