#include < stdio.h >
#include < math.h >
#include < process.h >
int board[20];
int count;
void main()
{
int n, i, j;
// n= number of queens
void queen(int row, int n);
printf("N-Queen's using Backtracking\n");
printf("Pick a number for Queen [preferably no less than 4]: ");
scanf("%d", &n);
queen(1, n);
//trace using backtrack
printf("\n\n\n\n\n");
}
/*Function to print solution of n-queen's problem*/
void print_board(int n)
{
int i, j;
printf("\n\n solution %d:\n\n", ++count);
//number of solution
for (i= 1; i<= n; i++)
{
printf("\t%d", i);
}
for (i= 1; i<= n; i++)
{
printf("\n\n%d", i);
for (j= 1; j<= n; j++)
//for n*n board
{
if (board[i] == j)
printf("\tQ");
//Queen at i,j position
else
printf("\t-");
//empty slot
}
}
}
/*Function to check for the conflicts for approaching location. returns 1 for no no conflict, 0 otherwise*/
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;
}
/*Function to reach and check next free slot for next possible location for the 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 board configuration
else //try with next position
queen(row +1, n);
}
}
}
special thanks to course mate: Sakib Shahid.
#include < math.h >
#include < process.h >
int board[20];
int count;
void main()
{
int n, i, j;
// n= number of queens
void queen(int row, int n);
printf("N-Queen's using Backtracking\n");
printf("Pick a number for Queen [preferably no less than 4]: ");
scanf("%d", &n);
queen(1, n);
//trace using backtrack
printf("\n\n\n\n\n");
}
/*Function to print solution of n-queen's problem*/
void print_board(int n)
{
int i, j;
printf("\n\n solution %d:\n\n", ++count);
//number of solution
for (i= 1; i<= n; i++)
{
printf("\t%d", i);
}
for (i= 1; i<= n; i++)
{
printf("\n\n%d", i);
for (j= 1; j<= n; j++)
//for n*n board
{
if (board[i] == j)
printf("\tQ");
//Queen at i,j position
else
printf("\t-");
//empty slot
}
}
}
/*Function to check for the conflicts for approaching location. returns 1 for no no conflict, 0 otherwise*/
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;
}
/*Function to reach and check next free slot for next possible location for the 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 board configuration
else //try with next position
queen(row +1, n);
}
}
}
special thanks to course mate: Sakib Shahid.