Article From:https://www.cnblogs.com/yuyu-blog/p/9046670.html

Description of the problem:

       The eight queen problem is a question of chess: how can you put eight queens on a 8 * 8 chess board so that any queen can’t eat other queens directly? To achieve this goal, no two empress can be on the same horizontal, vertical or diagonal line.

Backtracking:

       Backtracking is also called exploratory method. The basic practice of the backtracking method is the depth first search. That is to say, go forward from one road, go in and enter, do not enter, then retreat.

Source code:

#include<stdio.h>
#include<math.h>
int x[9]={0};
bool PLACE(int k)//Whether or not the queen of K can be put into a chessboard
{
    int i=1;
    while(i<k)
    {
        if(x[i]==x[k]||fabs(x[i]-x[k])==fabs(i-k))
            return false;
        i++;
    }
    return true;
}
void NQUEENS(int n)
{
    int i,k=1; //kFor the current line number
    x[1]=0;//x[k]The column number placed for the queen of line k
    while(k>0)
    {
        x[k]++;
        while(x[k]<=n&&!PLACE(k))//The line is not fit, then put in the next line
          x[k]++;
        if(x[k]<=n)
        {
            if(k==n)//Output x[]
            {
                for(i=1;i<=n;i++)
                    printf("x[%d]:%d  ",i,x[i]);
                printf("\n");
            }

            else//Judge the next line
            {
                k++; x[k]=0;
            }
        }
        else k--;//Not found, then backtracking
    }
    return ;
}
int main()
{
    NQUEENS(8);
    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *