Implementation of NQueen Algorithm with Backtracking Principle - C Code Example

#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");
    }
}