acwing 843. N-queen problem

n− The Queen's problem means that n Put a queen in n×n On my chess board , So that the queen can't attack each other , That is, no two Queens can be in the same line 、 On the same column or slash .

Now, given an integer n, Please output all the pieces that meet the conditions .

Input format
All in one line , Contains integers n.

Output format
Each solution accounts for n That's ok , Each line outputs a length of n String , Used to represent the complete chessboard state .

among . Indicates that the grid status of a position is empty ,Q The queen is placed on the square indicating a certain position .

After the output of each scheme is completed , Output a blank line .

Be careful ： There must be no extra spaces at the end of the line .

The order of output schemes is arbitrary , As long as there is no repetition and no omission .

Data range
1≤n≤9
sample input ：
4
sample output ：
.Q…
…Q
Q…
…Q.

…Q.
Q…
…Q
.Q…

This question is also DFS, It can be arranged according to

solution 1： Enumerate by row （ It's also the same question Full Permutation Allied ）
It can be remembered as a template

#include <iostream>
using namespace std;
const int N = 20; 

// bool Array is used to determine whether the next location of the search is feasible 
// col Column ,dg Diagonals ,udg Anti diagonal 
// g[N][N] Used to save path 

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u) {
    
    // u == n  It means that we have searched n That's ok , So output this path 
    if (u == n) {
    
        for (int i = 0; i < n; i ++ ) puts(g[i]);   //  Equivalent to cout << g[i] << endl;
        puts("");  //  Line break 
        return;
    }
    
	//  enumeration u This business , Search for legal Columns , //  Here, we can regard line as y,  Column as x
    //  Here is the enumeration number u That's ok ,  The first i  Column ,  Whether to release the queen , u= y, i = x  after  ===》  The diagonal is  u + i、u - i + n
	for (int i = 0; i < n; i ++ )
		//  prune ( For points that do not meet the requirements , No more searching ) 
        if (!col[i] && !dg[u + i] && !udg[n - i + u])
        {
    
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - i + u] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - i + u] = false;
            g[u][i] = '.';   //  Restore the scene 
        }
}

int main() {
    
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}  

Method 2： Enumerate according to each element
Every position has 2 In this case , Put it or not , There is... In all n²

Time complexity ： O(2 Of n² Power ), I can't fight it out , Forgive me

Schematic diagram ： Draw like this

Ideas ： Search step by step according to each position .

code：

//  Different search order   Time complexity is different   So the search order is very important ！
#include <iostream>
using namespace std;
const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; //  Because it's a search , So I added row

// s Indicates the number of queens that have been put on 
void dfs(int x, int y, int s)
{
    
    //  Deal with situations beyond the boundary ,  Whether to put this directly in one line or not ,  After walking , Jump to the next line to start 
    if (y == n) y = 0, x ++ ;  

    if (x == n) {
     // x==n Description has been enumerated n^2 It's a place 
        if (s == n) {
     // s==n It means that it was successfully put on n A queen 
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    //  Branch 1： Put the queen 
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
    
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }

    //  Branch 2： Don't let the queen go 
    dfs(x, y + 1, s);
}


int main() {
    
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0, 0, 0);

    return 0;
}