C Program of N Queens Problem Solution using Backtracking

C Program of N Queens Problem Solution using Backtracking

1596
7
SHARE

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 to solve N queen problem using 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 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…

7 COMMENTS

  1. wonderful points altogether, you simply gained a brand new reader. What may you recommend about your submit that you simply made a few days in the past? Any sure?

  2. I’ve been browsing online more than three hours these days, yet I never discovered any fascinating article like yours. Itˇ¦s beautiful price enough for me. In my opinion, if all web owners and bloggers made excellent content material as you probably did, the web will likely be much more helpful than ever before.

LEAVE A REPLY