C Program of N Queens Problem Solution using Backtracking

C program of N queens problem solution : The N Queens Puzzle is the problem of putting N chess queens on an N×N chessboard such that none of them is able to capture any other using the standard chess queen’s moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

Lets us consider an example of 8 queens problem. 8 Queens puzzle has 92 distinct solutions or patterns, where each queens can be placed such that no two queens would be able to attack each other. If we consider the symmetry of patterns into account then there will be 12 distinct solutions.

I have written a C program for solving  N Queen problem which displays the distinct solutions or patters of N queen puzzle. In my later code we will extend our logic to display only unique patterns i.e. symmetrical patterns excluded. But till that time lets see how to write a C program to solve N queen problem using C programming Language which take number of Queens as input and displays the Queens distinct placement patterns as output.

C program of N Queens Problem Solution using Backtracking :

#include<conio.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
/* For printing the Grid */
void print_grid(int n,int x[])
{
    char arr[20][20];
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1; j<=n; j++)
        {
            arr[i][j]='-';
        }
    }

    for(i=1;i<=n;i++)
    {
        arr[i][x[i]]='Q';
    }

    for( i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            printf("\t%c",arr[i][j]);
        }
            printf("\n");
    }

}

/* For checking Queens placement is safe or not */
int safetoplace(int x[],int k)
{       int i;
    for(i=1;i<k;i++)
    {
        if(x[i]==x[k]||i-x[i]==k-x[k]||i+x[i]==k+x[k])
        {
            return 0;  /* False*/
        }
    }
    return 1; /*true*/
}
/* For printing the Queens and Placing them in Grid */
void nqueens(int n)
{
    int x[20];
    int count=0;
    int k=1;

    x[k]=0;

    while(k!=0)
    {

        x[k]=x[k]+1;
        while((x[k]<=n)&&(!safetoplace(x,k)))
        {

            x[k]=x[k]+1;
        }
        if(x[k]<=n)
        {
            if(k==n)
            {
                count++;
                printf("\n\tPlacement %d  is : \n\n\n",count);
                print_grid(n,x);
                getch();

            }
            else
            {
                k++;
                x[k]=0;
                 }
        }
        else
        {
            k--;
        }
    }
    return;
}

/* Main Function */
int main()
{
    int n;
    printf("----------------------------------------------------\n");
    printf("-------------Made by C codechamp--------------------\n");
    printf("----------------------------------------------------\n\n");
    printf("\t C PROGRAM OF N-QUEEN PROBLEM\n\n");
    printf("\nEnter the no. of Queens : ");
    scanf("%d",&n);
    printf("\n\n\tUSING %d QUEEN'S STRATEGY \n\n",n);
    nqueens(n);
    system("pause");
    getch();
}

We hope that you all have enjoyed the C program of N Queens Problem Solution using Backtracking. If you have any issues with the logic or the code, ask us in form of comments.

Uniqueness is the key ! and Quality is what we deliver…