N queen problem (backtracking, permutation tree)

n A queen , Every two queens cannot be in the same line , The same column , On the same diagonal
（i,Xi）,（j,Xj） Not on the same main diagonal is Xi-i！=Xj-j, namely Xi-Xj！=i-j;
                    Not on the same negative diagonal Xi+i！=Xj+j, namely Xi-Xj！=j-i;
Merge into abs（Xi-Xj）！=（i-j）

/*
 n A queen , Every two queens cannot be in the same line , The same column , On the same diagonal 
（i,Xi）,（j,Xj） Not on the same main diagonal is Xi-i！=Xj-j, namely Xi-Xj！=i-j;
                     Not on the same negative diagonal Xi+i！=Xj+j, namely Xi-Xj！=j-i;
 Merge into abs（Xi-Xj）！=（i-j）
*/
// The first solution 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=200;
int p[maxn],ans=0;
bool hashTable[maxn]={0};
void fullper(int index,int n);
int temp1=0,temp2=0,temp3=0,temp4=0,temp5=0;

int main()
{
    int n;
    printf(" Enter a positive integer :\n");
    scanf("%d",&n);
    fullper(1,n);
    cout << ans << endl;
    cout << "temp1: " << temp1 << endl;
    cout << "temp2: " << temp2 << endl;
    cout << "temp3: " << temp3 << endl;
    cout << "temp4: " << temp4 << endl;
    cout << "temp5: " << temp5 << endl;
    return 0;
}

void fullper(int index,int n)
{
    if(index==n+1)
    {
        ++ans;
        cout << ans << "th:\n";
        for(int i=1;i<=n;++i)
        {
            cout << p[i];
            if(i<n)
                cout << ' ';
            else
                cout << endl;
        }
    }
    else
    {
        for(int i=1;i<=n;++i)
        {
            ++temp1;
            if(hashTable[i]==0)
            {
                ++temp2;
                bool flag=true;
                for(int j=1;j<index;++j)
                {
                    ++temp3;
                    if(abs(i-p[j])==abs(index-j))
                    {
                        ++temp4;
                        flag=false;
                        break;
                    }
                }
                if(flag)
                {
                    ++temp5;
                    p[index]=i;
                    hashTable[i]=1;
                    fullper(index+1,n);
                    hashTable[i]=0;   // Clean up the site , Release the previously occupied position 
                }
            }
        }
    }
}

The second solution
（x,y） The equation on the main diagonal is y=x+b, therefore y-x=b;y-x For the range of [-n+1,n-1];
        The equation on the negative diagonal is y=-x+b, therefore y+x=b;y+x For the range of [2,2*n];
        So use i-j+n [1,2*n-1] Number the main diagonal , use i+j [2,2*n] Negative diagonal number .

/**
 The second solution 
（x,y） The equation on the main diagonal is y=x+b, therefore y-x=b;y-x For the range of [-n+1,n-1];
         The equation on the negative diagonal is y=-x+b, therefore y+x=b;y+x For the range of [2,2*n];
         So use i-j+n [1,2*n-1] Number the main diagonal , use i+j [2,2*n] Negative diagonal number .
*/

/**
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=20;
int p[maxn],c[2*maxn]={0},d[2*maxn]={0};
bool hashTable[maxn]={0};
int n,ans=0;
void fullper(int index);
void output();
int temp_min=0,temp_max=0;

int main()
{
    printf(" Enter a positive integer :\n");
    scanf("%d",&n);
    fullper(1);
    cout << ans << endl;
    cout << "temp_max: " << temp_max << endl;
    cout << "temp_min: " << temp_min << endl;
    return 0;
}

void fullper(int index)
{
    for(int j=1;j<=n;++j)
    {
        ++temp_max;
        if(hashTable[j]==0&&c[index-j+n]==0&&d[index+j]==0)
        {
            ++temp_min;
            p[index]=j;
            hashTable[j]=1;
            c[index-j+n]=1;
            d[index+j]=1;
            if(index<n)
                fullper(index+1);
            else
                output();
            hashTable[j]=0;     // The following three sentences are cleaning up the scene 
            c[index-j+n]=0;
            d[index+j]=0;
        }
    }
}

void output()
{
    ++ans;
    cout << ans << "th:\n";
    for(int i=1;i<=n;++i)
    {
        cout << p[i];
        if(i<n)
            cout << ' ';
        else
            cout << endl;
    }
}
*/

The third solution ：
First, we give the total permutation of solutions , Only exchange the values of two numbers at a time , Until the conditions are met ,
These algorithms can judge whether the conditions are met one by one , Much better
（x,y） The equation on the main diagonal is y=x+b, therefore y-x=b;y-x For the range of [-n+1,n-1];
        The equation on the negative diagonal is y=-x+b, therefore y+x=b;y+x For the range of [2,2*n];
        So use i-j+n [1,2*n-1] Number the main diagonal , use i+j [2,2*n] Negative diagonal number .

/**
 The third solution ：
 First, we give the total permutation of solutions , Only exchange the values of two numbers at a time , Until the conditions are met ,
 These algorithms can judge whether the conditions are met one by one , Much better 
（x,y） The equation on the main diagonal is y=x+b, therefore y-x=b;y-x For the range of [-n+1,n-1];
         The equation on the negative diagonal is y=-x+b, therefore y+x=b;y+x For the range of [2,2*n];
         So use i-j+n [1,2*n-1] Number the main diagonal , use i+j [2,2*n] Negative diagonal number .
*/

/**
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=20;
int p[maxn],c[2*maxn]={0},d[2*maxn]={0};
bool hashTable[maxn]={0};
int n,ans=0;
void fullper(int index);
void output();
int temp_min=0,temp_max=0;

int main()
{
    printf(" Enter a positive integer :\n");
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        p[i]=i;
    fullper(1);
    cout << "total: " << ans << endl;
    cout << "temp_max: " << temp_max << endl;
    cout << "temp_min: " << temp_min << endl;
    return 0;
}

void fullper(int index)
{
    for(int j=index;j<=n;++j)
    {
        ++temp_max;
        swap(p[index],p[j]);
        if(c[index-p[index]+n]==0&&d[index+p[index]]==0)
        {
            ++temp_min;
            c[index-p[index]+n]=1;
            d[index+p[index]]=1;
            if(index<n)
                fullper(index+1);
            else
                output();
            c[index-p[index]+n]=0;  // The following three sentences are cleaning up the scene 
            d[index+p[index]]=0;
        }
       swap(p[index],p[j]);
    }
}

void output()
{
    ++ans;
    cout << ans << "th:\n";
    for(int i=1;i<=n;++i)
    {
        cout << p[i];
        if(i<n)
            cout << ' ';
        else
            cout << endl;
    }
}
*/