n-queens problem

  subject ：

Eight queens question ：
Put eight queens on a chess board , Make no two queens attack each other , Find out all
Cloth chess method of . Run the machine and check the results .
reflection ： Extend this question to N The Queen's situation , The test is in N In large cases , For example N=16 When the
Hou , Can your program get the result quickly , If not , Think about how to optimize the algorithm .

#include <iostream>
using namespace std;

#define max 50
int x[max + 1];// The first i The queen of the line is on the x[i] On the column 
int n;// The width of the chessboard and the number of queens 
int sum = 0;// Calculate the number of solutions 


// The coordinates of the queen to be placed are （row,col）, Judge whether it can be placed 
bool Place(int row, int col) {
    for (int i = 1; i < row; i++)  // Before the comparison row -1 Line has been placed queen aax
    {
        if (col == x[i] || abs(row - i) == abs(col - x[i]))  // Judge whether the queen to be released and the existing queens are in the same column or the same slash 
            return false;
    }
    return true;
}

// Recursive backtracking function , If the conditions are met, recursion down , If the conditions are not met , Then go back 
void Backtrack(int t, int n) {
    if (t == n + 1)  // Successfully traverse all chessboards once , Formed a solution 
        sum++;
    else {
       //  If this line traverses to n Still can't place the queen , Then go back 
        for (int i = 1; i <= n; i++) {
            x[t] = i;
            if (Place(t, x[t]))// Judge whether the queen can be placed 
                Backtrack(t + 1, n);// If the queen can be placed in this line , Then recurse to the next line 
        }
    }
}

int main()
{
    cout << " Please enter the number of queens : ";
    cin >> n;
    Backtrack(1, n);
    cout << " The number of solutions is : " << sum << endl;

    return 0;
}

Test chart ：