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

How to work with Ellipsis Operator in C Language?

In my last post, I was talking about the printf function and there I said that printf uses ellipsis operator. In this post I would like to elaborate on how to use ellipsis in C program.

a. Here are some important points on Ellipsis

b. Ellipsis operator is expressed only with three dots (…) within the argument list of a function

c. Ellipsis must be the last argument in the argument list

d. The argument list containing the ellipsis must have at least another argument (other than the ellipsis) in the list. Let us call it as “Mandatory Argument”.

This Mandatory Argument must be placed just before the ellipsis and this Mandatory Argument must reflect the number of variable arguments currently being passed explicitly or implicitly.

Here I mean to say, Mandatory Argument can explicitly say that currently n numbers of variable arguments are being passed; in this case the prototype of the function would be something like

void foo(int no_of_variable_arguments, …)

Otherwise Mandatory argument may hide this information within any sort of other data types. For example if the numbers of variable arguments is an element of a structure of type Info, then a valid prototype would be

void foo(struct Info str, …)

If the numbers of variable arguments are passed implicitly then it becomes the responsibility of foo to determine (within the body code of foo) what the value of n from the given container is.

Let us take some more examples

void foo(int var1, int num, …) is a valid usage of ellipsis. Here num is working as Mandatory argument and the numbers of variable arguments actually being passed must be explicitly / implicitly determined through num. var1 is nothing but the optional argument , which might be there for any good reasons.

void foo( char* str, …) is again valid. Here the numbers of variable arguments being passed must be hidden within string str. parsing of str will give you the required value of n. The logic of parsing must be maintained within foo

Let us do a case study on our good old friend printf

The signature of printf is like

int printf(const char* formatString, …)

Here Mandatory Argument does the trick to hide the numbers and types of variable arguments currently being passed.  For example if I call printf like printf(“The results are %d, %d and %f”, I,j,k); then the string  “The results are %d, %d and %f” will implicitly say that there are three variable arguments that are being passed now and they are i, j and k. The proper parsing algorithm in printf will be able to count the numbers of format specifiers like %d or %f and this obviously hides the data types of variable arguments also.  Parsing of “The results are %d, %d and %f” essentially says that there would be three variable arguments and out of these three variable arguments, first two are ints and the third one is float .

Now let us go straight to “how to write the body of the function containing ellipsis as an argument”.

Ellipsis works with four different macros to deal with variable number of arguments; and they are va_list, va_start, va_arg and va_end. The va_list stores the variable arguments. The list is declared like

va_list anyList;

The va_start takes two arguments, the va_list itself and the Mandatory Argument. If the Mandatory Argument passed to the experimental function be integer x, then the call to va_start would be

va_start( anyList, x );

va_start initializes the va_list.

Next va_arg also takes two arguments, va_list itself with a particular data type. For example

va_arg(anyList,float);

Calling of this macro returns the next float from the anyList. 

Ultimately, va_end(anyList) will clean up anyList.

CODE EXAMPLE

The following code example shows how to write a function with variable number of arguments. The

code is self explanatory through commenting. Please give proper attention to the comment in red.

#include<stdio.h>

#include<stdlib.h>

#include <stdarg.h>

//defining the function with variable number of arguments

float findAverage(int numArg, ...)

{

      float avg;

      int sum = 0;

      int arg;

      int index;

      va_list list; //creating the variable list

      va_start(list,numArg); // initializing the list with numAg number of arguments

      for( index = 0 ; index < numArg; index++ )

      {

                  arg = va_arg( list, int );//retrieving the arguments. The prior knowledge of the argument is mandatory. Here in this case it is “int”

                  sum = sum + arg; 

      }

      avg = sum / numArg;

      va_end(list); //clearing up the list

      return avg;

}

int main(void)

{

      //calling the function with variable number of arguments

      printf("\n The average of 3, 4, 5 = %f\n", findAverage(3,3,4,5) );

      printf("\n The average of 6,7,8,9,10 = %f\n", findAverage(5,6, 7, 8, 9, 10));

      return 0;        

}

In fresher interview technical round, you may get confused with some object oriented "look a like" features of C language.

Sometimes C looks like to follow object oriented paradigm. Don’t get carried away withis idea. Current post focuses on this.

Star (*) Operator in C language acts both as pointer and multiplication. Then could we say that C supports Operator Overloading?

C language certainly does not obey operator overloading. In operator overloading, the function of the operator becomes different, but the arity of  the operator never changes. Here when * acts as a multiplier it is binary in nature, but when it acts as a pointer, it acts as a unary operator. Hence this example never follows the condition of operator overloading regarding the arity of the operator and so by citing this example, we cannot say that C supports operator overloading.

In C language, printf function takes different number and different nature of arguments in every time. Is it the example of Function Overloading?

No way! C does not support function overloading at all. The functions print() is capable of accepting different numbers of arguments due to an operator ellipsis which is represented as … (just three dots, nothing else!)

If we look at the prototype of printf, it would say something like

int printf(const char*, …);

The second parameter is the ellipsis and it uses four different predefined macros va_list, va_start, va_arg and va_end.  Ellipsis essentially says that there could be any number of arguments. This what printf() is backed with, certainly this is not a valid example of function overloading. Because in function overloading the numbers of arguments are specific, for example a function accepting two parameters can be made to accept three parameters (or so), but the instances, two or three are specific. Again in function overloading, the type of parameters can be changed, but once again the set is fixed like a function can act to accept a float and an int, but any data type with function overloading? Just forget it out.

So we are left with to demystify how printf() can accept any data type! This is done by parsing the first parameter of the printf that is const char* which is a string essentially. As we all know, this string contains different format specifiers like %d, %f etc, these specifiers peels out the knowledge that what is type of corresponding argument.

For example if we use

printf(“The results are = %d %f”, i_val, f_val);    

Then in the va_list macro, that is in the list of (v)ariable (a)rgument, there will be two arguments. By parsing the mandatory format string, the type of the first argument is computed as int and the second argument is fixed as float.

Now the question is where is this parsing algorithm present? This algorithm has been implanted within the definition of printf().

In the following post I will show how to use ellipsis operator with code examples.

Can we store different data types in a stack?

Yesterday, one of my Facebook friend asked me this question. My answer is "yes", and in this post I will discuss how could we do this.

I am a great supporter of working with unions and I will be using union for it.

If you are to implement the stack with arrays, then within the stack array you need to maintain a union so that you can store different data types. Along with this you need to have stack top variable and an array to keep track of data type of each array position.

Here is the code. I have written it in great hurry and therefore the code is not fully optimized..but it is running obviously.

#include<stdio.h>
#include<stdlib.h>
#define CHARACTER 1
#define INTEGER 2
#define UNKNOWN 3
#define INVALID_INT -99
#define INVALID_CHAR '~'

union Data
{
    int ival;
    char cval;
};
struct STACK
{
    union Data* arr;
    int topVal;
    int* topType;        
};

struct POPVAL
{
    int pival;
    char pcval;
};
struct STACK* initStack(int size)
{
    int i;
    struct STACK* p;
    p =(struct STACK*)malloc(sizeof(struct STACK));
    p->arr = (union Data*)malloc (size*sizeof(union Data));
   
    p->topVal = -1;
   
    p->topType = (int *)malloc (size*sizeof(int));
    for(i = 0; i<size; i++)
        p->topType[i] = UNKNOWN;
    printf("\n Stack is initialized...");
    return p;    
}

void pushChar(struct STACK* p, int size)
{
   
    if(p->topVal == size - 1)
        printf("\n Overflow Condition Appears.... No Push Posible....");
    else
    {
        p->topVal = p->topVal + 1;
        fflush(stdin);
        printf("\n Enter the character to push:");
        scanf("%c", &p->arr[p->topVal].cval);
        p->topType[p->topVal] = CHARACTER;
        printf("\n Character Push Done....");
    }
}

void pushInt(struct STACK* p, int size)
{
    if(p->topVal == size - 1)
        printf("\n Overflow Condition Appears.... No Push Posible....");
    else
    {
        p->topVal = p->topVal + 1;
        printf("\n Enter the integer to push:");
        scanf("%d", &p->arr[p->topVal].ival);
        p->topType[p->topVal] = INTEGER;
        printf("\n Integer Push Done....");
    }    
}

struct POPVAL* pop(struct STACK* p)
{
    struct POPVAL* poppedVal = NULL;
    if(p->topVal != -1)
    {
        poppedVal = (struct POPVAL*)malloc(sizeof(struct POPVAL));
        poppedVal->pival = INVALID_INT;
        poppedVal->pcval = INVALID_CHAR;
        if(p->topType[p->topVal] == CHARACTER)
        {
            poppedVal->pcval = p->arr[p->topVal].cval;
        }
        if(p->topType[p->topVal] == INTEGER)
        {
            poppedVal->pival = p->arr[p->topVal].ival;
        }
        p->topVal = p->topVal - 1;
    }
    return poppedVal;
            
}
void displayStack(struct STACK* p, int size)
{
    int i;
    printf("\n Displaying Stack ...\n");
    for(i = 0; i<=p->topVal; i++)
    {
        if(p->topType[i] == CHARACTER)
            printf(" %c ", p->arr[i].cval);
        if(p->topType[i] == INTEGER)
            printf(" %d ", p->arr[i].ival);        
    }
}

int main(void)
{
    int maxSize,choice;
    struct STACK* stack;
    struct POPVAL* popstruct;
    printf("What is the max size of the array ?");
    scanf("%d", &maxSize);
    stack = initStack(maxSize);
    do
    {
        printf("\n *************** Menu ***************\n");
        printf("\n 1. Push Character to the Stack");
        printf("\n 2. Push Integer to the Stack");
        printf("\n 3. Pop From the Stack");
        printf("\n 4. Display Stack");
        printf("\n 5. Exit");
        printf("\n\n Enter Your Choice::");
        scanf("%d", &choice);
        switch(choice)
        {
            case 1:
                    pushChar(stack,maxSize);
                    break;
            case 2:
                    pushInt(stack,maxSize);
                    break;
            case 3:
                    popstruct = pop(stack);
                    if(popstruct == NULL)
                        printf("\n Underflow Condition Appears... No Pop Possible....");
                    else
                    {
                        if(popstruct->pival != INVALID_INT)
                            printf("\n Integer Pop Done With Value = %d",popstruct->pival);
                        else
                            printf("\n Character Pop Done With Value = %c",popstruct->pcval);    
                    }
                    break;                                                                
            case 4:
                    displayStack(stack, maxSize);
                    break;
            
            case 5:
                    printf("\n Exiting From The Program...");
                    break;            
            default:
                    printf("\n Enter A Valid Choice...");
        }
        
    }while(choice!=5);
    printf("\n Thanks for using BunksAllowed Code....\n\n");
    return 0;
}

The same thing you need to do if you are to implement the stack with a linked list. In this case, the nodes of the linked list must contain a union to store different data types, along with a typical next pointer and a special variable to inform which node is containing which data type.

Happy Learning!