This eight queen problem is also a classic entry deep search topic ah, theoretically deep search can use the stack of data structure to simulate the computer internal stack operation. But here is really trouble, I used to do the solution of the notes out, while facilitating their own summary, while also to provide you with a way of thinking.

The title

The origin and problem of eight Queens The eight queens problem is an ancient and famous problem and a typical case of backtracking algorithm. The question was put forward by the international chess player Max Bethel in 1848: how many positions can be placed on an 8×8 square of chess with eight queens so that they cannot attack each other? That is, no two queens can be in the same row, column, or diagonal line? Gauss thinks there are 76 options. In 1854, different authors published 40 different solutions in the Chess Journal of Berlin, and later someone solved 92 results using graph theory. After the invention of computers, there are many computer languages to solve this problem.Copy the code

(Baidu Dafa adds literariness)

code

I didn’t use the easy to think of two-dimensional arrays here, because TLE, arrays are too big to waste time. Just use a few bit arrays to simulate, see the code for details.

#include<stdio.h>
// Save as a global variable for easy call
int n,l,size,Maxprint,col[100000],left[100000],right[100000],a[100000];
// Note that Maxprint is a global variable. Print is incremented each time it is called
// total number of solutions
/ / a line
/ / col column
//left saves the diagonal from bottom left to top right.
//right saves the diagonal from the bottom right to the top left.
void print(a)
{
    if(Maxprint<3)
    {
        for(int i=1; i<=size; i++)printf("%d ",a[i]);
        printf("\n");
        Maxprint++;
    }
    return ;
}
int Judge(int x,int y)
{
    if(col[y]==1||left[x+y]==1||right[x-y+10000] = =1)// Return 0 if occupied
        return 0;
    else
        return 1;
}
void search(int x)// Deep search,x is the starting search line
{
    if(x>size)
    {
        n++;// Add one to the total solution
        print();// Call the output function
        return ;
    }
    for(int i=1; i<=size; i++)// Traverse the columns from the initial search row x
        if(Judge(x,i)==1)
    {
        a[x]=i;
        col[i]=left[x+i]=right[x-i+10000] =1;
        search(x+1);
        col[i]=left[x+i]=right[x-i+10000] =0;/ / back}}int main(a)
{
    scanf("%d",&size);
    for(int i=0; i<10000; i++) a[i]=col[i]=left[i]=right[i]=0;
        // initialize the checkerboard
    search(1);// Start with the first line
    printf("%d",n);// Output total solutions
    return 0;

}

Copy the code