#include<stdio.h>
#include<stdlib.h>
//global variable to keep track of numbers of solutions
int solNum = 0;
void initBoard(int, char**); //initializes the boardvoid nqueen(int, int, char**, int); //puts the queen
//following backtrack method
int eraseQueen(int, int, char**);//erases a queen at the
//time of backtrack and gets its column positionint feasible(int,int,int,char**); //checks whether placing
// of a queen in a particular position is feasible or not
void showBoard(int, char**);//shows the board
int main(void)
{
int num,i,startingRow;
char** board;
printf("\n Enter the number of Queens::");
scanf("%d", &num);
board=(char**)malloc(num*sizeof(char*));
for(i=0;i<num;i++)
board[i]=(char*)malloc(num*sizeof(char));
printf("\n Board is allocated Successfully");
initBoard(num, board);
startingRow = 0;
nqueen(startingRow, num, board,0);
return 0;
}
//board gets initialized with a X
void initBoard(int size, char** brd)
{
int i, j;
for(i=0;i<size;i++)
for(j=0;j<size;j++)
brd[i][j]='X';
printf("\n Board is initialized successfully");
}
//puts queen with backtrack in current row, it tries to put
//the queen starting from start column
void nqueen(int currRow, int size, char** brd, int startCol)
{
int col, count = 0, prevQueenCol;
if(currRow == 0 && startCol == size) // All queens have been //placed
//or all positions have been checked exit(0);
if(startCol == size) // If you need to place a queen which is
//out of the board in a row, that is queen in the previous //row
//must be changed (Backtrack)
{
prevQueenCol = eraseQueen(currRow -1, size, brd); //get //the column
//of previous queen nqueen(currRow - 1, size, brd, prevQueenCol + 1);// calls //nqueen for the
//previous row, and column just got + 1
}
//oterwise -- normal scenario for(col = startCol; col<size; col++)
{
if(feasible(currRow,col,size,brd)==0){ //if the queen can //be
//placed at current row ith column
brd[currRow][col]='Q'; //place the queen if(currRow == size - 1) //if current row is the last //row
//that is queen is placed in the last row, one //solution is
//found
{
solNum = solNum + 1; //solution count increased
printf("\n Solution #%d\n", solNum);
showBoard(size, brd); //show the solution
brd[currRow][col] = 'X'; //initialize the position again
//to search for any other solution count = count + 1; //Assume as it is a failure //(for he
//next solutions
}
else //if the row is not the last row, try to place the
//queen in the next row
nqueen(currRow+1,size,brd,0);
}else{ // queen placing not feasible, so failure count = count + 1; //increase failure count
}
}
//backtracking starts
if(count == size - startCol) // if failure for all the column
{
prevQueenCol = eraseQueen(currRow -1, size, brd); // get //the column
// of previous queen in previous column
nqueen(currRow - 1, size, brd, prevQueenCol + 1); //that //placing was wrong
//try to place the queen in the previous row starting //from the next column
}
}
//erases the queen
int eraseQueen(int currRow, int size, char** brd)
{
int col;
for(col = 0; col<size; col++)
{
if(brd[currRow][col] == 'Q')
{
brd[currRow][col] = 'X';
return col;
}
}
}
//test feasibility of queen placing
int feasible(int row,int col,int size, char** brd)
{
int i, j;
for(i = 0; i < size; i++)
{
for(j = 0; j < size; j++)
{
if(brd[i][j] == 'Q')
{
if(i == row || j == col || abs(i - row) == abs(j - col))//If no two Queens are placed in same row, column or //diagonals
return 1;
}
}
}
return 0;
}
//Shows board
void showBoard(int size, char** brd)
{
int i, j;
for(i = 0; i < size; i++)
{
for(j = 0; j < size; j++)
{
printf("%c ", brd[i][j]);
}
printf("\n");
}
}
#include<stdlib.h>
//global variable to keep track of numbers of solutions
int solNum = 0;
void initBoard(int, char**); //initializes the boardvoid nqueen(int, int, char**, int); //puts the queen
//following backtrack method
int eraseQueen(int, int, char**);//erases a queen at the
//time of backtrack and gets its column positionint feasible(int,int,int,char**); //checks whether placing
// of a queen in a particular position is feasible or not
void showBoard(int, char**);//shows the board
int main(void)
{
int num,i,startingRow;
char** board;
printf("\n Enter the number of Queens::");
scanf("%d", &num);
board=(char**)malloc(num*sizeof(char*));
for(i=0;i<num;i++)
board[i]=(char*)malloc(num*sizeof(char));
printf("\n Board is allocated Successfully");
initBoard(num, board);
startingRow = 0;
nqueen(startingRow, num, board,0);
return 0;
}
//board gets initialized with a X
void initBoard(int size, char** brd)
{
int i, j;
for(i=0;i<size;i++)
for(j=0;j<size;j++)
brd[i][j]='X';
printf("\n Board is initialized successfully");
}
//puts queen with backtrack in current row, it tries to put
//the queen starting from start column
void nqueen(int currRow, int size, char** brd, int startCol)
{
int col, count = 0, prevQueenCol;
if(currRow == 0 && startCol == size) // All queens have been //placed
//or all positions have been checked exit(0);
if(startCol == size) // If you need to place a queen which is
//out of the board in a row, that is queen in the previous //row
//must be changed (Backtrack)
{
prevQueenCol = eraseQueen(currRow -1, size, brd); //get //the column
//of previous queen nqueen(currRow - 1, size, brd, prevQueenCol + 1);// calls //nqueen for the
//previous row, and column just got + 1
}
//oterwise -- normal scenario for(col = startCol; col<size; col++)
{
if(feasible(currRow,col,size,brd)==0){ //if the queen can //be
//placed at current row ith column
brd[currRow][col]='Q'; //place the queen if(currRow == size - 1) //if current row is the last //row
//that is queen is placed in the last row, one //solution is
//found
{
solNum = solNum + 1; //solution count increased
printf("\n Solution #%d\n", solNum);
showBoard(size, brd); //show the solution
brd[currRow][col] = 'X'; //initialize the position again
//to search for any other solution count = count + 1; //Assume as it is a failure //(for he
//next solutions
}
else //if the row is not the last row, try to place the
//queen in the next row
nqueen(currRow+1,size,brd,0);
}else{ // queen placing not feasible, so failure count = count + 1; //increase failure count
}
}
//backtracking starts
if(count == size - startCol) // if failure for all the column
{
prevQueenCol = eraseQueen(currRow -1, size, brd); // get //the column
// of previous queen in previous column
nqueen(currRow - 1, size, brd, prevQueenCol + 1); //that //placing was wrong
//try to place the queen in the previous row starting //from the next column
}
}
//erases the queen
int eraseQueen(int currRow, int size, char** brd)
{
int col;
for(col = 0; col<size; col++)
{
if(brd[currRow][col] == 'Q')
{
brd[currRow][col] = 'X';
return col;
}
}
}
//test feasibility of queen placing
int feasible(int row,int col,int size, char** brd)
{
int i, j;
for(i = 0; i < size; i++)
{
for(j = 0; j < size; j++)
{
if(brd[i][j] == 'Q')
{
if(i == row || j == col || abs(i - row) == abs(j - col))//If no two Queens are placed in same row, column or //diagonals
return 1;
}
}
}
return 0;
}
//Shows board
void showBoard(int size, char** brd)
{
int i, j;
for(i = 0; i < size; i++)
{
for(j = 0; j < size; j++)
{
printf("%c ", brd[i][j]);
}
printf("\n");
}
}