This is the first day of my participation in the More text Challenge. For details, see more text Challenge

Put N queens on an N by N board so that they can’t attack each other. Two queens can attack each other if and only if they’re on the same row, or the same column, or the same diagonal. Find out how many different ways to put it.

Solve the n queen problem recursively

Analysis: this is a classic backtracking procedure, is to use recursive implementation, in fact, can also use non-recursive implementation. Backtracking does not have to be implemented recursively.

As for conflicts, row conflicts definitely do not exist, mainly judging column conflicts and slash conflicts.

QueenPos [J]! = I, there will be no conflict

Through observation, it can be found that the positions of all queens in the collision on the slash are regular, that is, the absolute value of the subtractions of their rows and columns are equal, that is, abs(queenPos[j] -i) == abs(k-j)

#include <bits/stdc++.h>
const int N = 1e6 + 5;
#define ll long long
const ll inf = 0x3f3f3f3f3f3f;
#define mst(a, b) memset(a, b, sizeof(a))
#define ref(i, be, en) for (int i = be; i < en; ++i)
#define lowbit(x) (x & -x)
using namespace std;
int queenPos[105]; // In a certain way, each row takes the place of the queen.
int sum = 0;       // Total number of schemes
inline void print(int count)
{
    for (int i = 0; i < count; i++)
    {
        int k = queenPos[i];
        for (int j = 0; j < count; j++)
        {
            if (j == k)
                cout << i + 1 << ' ';
            else
            {
                cout << "0";
            }
        }
        cout<<endl;
    }
    cout<<"----------------\n";
}
inline void NQueen(int k, int n)
{
    // Query the position of the queen in row k. The queen in row 0~k-1 has been set. There are n queens in row 0~n-1

    if (n == k) // N are already set
    {
        print(n);// Indicate that a pendulum method has been completed and print
        sum++;
        return;
    }
    for (int i = 0; i < n; i++) // Try the KTH queen position gradually, n columns in total, each column will be tried. Whether it succeeds or not
    {
        int j;
        for (j = 0; j < k; j++) // Compare with the set,
        {
            if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k-j))// Conflict check
                break;
        }
        if (j == k)
        {                     // There is no conflict,
            queenPos[k] = i;  // Put the queen of row k in column I
            NQueen(k + 1, n); // Find the queen position in row k+1.}}}int main(a)
{
    int n;
    cin >> n;
    NQueen(0, n); // Start with queen in line 0.
    cout<<"The total number of schemes is:"<<sum<<endl;

    return 0;
}

Copy the code

Recursive backtracking method, easy to understand, but in the cost of time, but not small, here recommended a faster algorithm for time optimization.

The bit operation solves for the n queen
void test(int row, int ld, int rd) { intpos, p; if( row ! = upperlim ) { pos= upperlim & (~(row | ld | rd )); while( pos ) { p= pos & (~pos + 1); pos= pos - p; test(row| p, (ld | p) << 1, (rd | p) >> 1); } } else ++Ans; }Copy the code

Full code + detailed remarks:

#include "iostream"
using namespace std;
#include "time.h"
// count the number of different layouts that the queen has successfully placed; Upperlim is used to indicate that all columns have queens placed.
long sum = 0, upperlim = 1;    
// The heuristic algorithm starts with the rightmost column.
void test(long row, long ld, long rd)
{
         if(row ! = upperlim) {//row, ld, rd; //row, ld, rd;
// Select * from 'and' where the queen can be placed. Select * from 'and' where the queen can be placed
                   // Select the current column where the queen is placed
                   longpos = upperlim & ~(row | ld | rd);
                   while(pos)    // 0 -- Queen has no place to put, backtrack
                   {
                            // Copy the rightmost bit of pos to 1, and set the rest to 0
                            // Get the rightmost column where the queen can be placed
                            longp = pos & -pos;                                              
                            // Clear the rightmost bit of pos (1) to zero
                            // To get the next right-most available column,
                            // The program will go back to this position in the future to continue testing
                            pos-= p;                          
                            //row + p, set the current column to 1, indicating that the queen placed the column this time.
                            //(ld + p) << 1, indicating that the adjacent column to the left of the current queen does not allow the next queen to be placed.
                            //(ld + p) >> 1, indicating that the adjacent column to the right of the current queen does not allow the next queen to be placed.
                            // The shift operation here is actually recording the limitation on the diagonal, just because the problem is all reduced
                            // Work on a row of grids, so the constraints expressed as columns will do. Obviously, with the shift
                   // Before each column selection, a queen has been placed in the original N×N grid for its diagonal
                            // The restrictions are recorded
                            test(row+ p, (ld + p) << 1, (rd + p) >> 1); }}else  
         {
                   // All bits of the row are 1, i.e. a successful layout is found, backtracesum++; }}int main(int argc, char *argv[])
{
         clock_tstart,finish;
         intn;
         printf("Please enter the number of queens:");
         scanf("%d",&n);
         start= clock(a);printf("\n Using bit operation %d queen problem run \n",n);
     test(0.0.0);
         finish= clock(a);printf("Total %ld permutations, calculated time %.2fms\n", sum, (double) (finish - start));
         system("pause");
         return0;
}
Copy the code