[30. N-queen problem]

DFS Two cores

• to flash back
• prune ： It can be judged in advance that the scheme is illegal , So there is no need to continue searching , Directly subtract the following and directly backtrack .

subject

Two ways ：

• The first method ： By enumerating , There is only one queen in each line , When enumerating , Just make sure there is only one in each line , So there was no row[N]. Depth traversal of rows .
• The second method ： There are two situations in each position , Or put the queen , Or don't let the queen go

Method 1：

• For the first r OK, No i A place , Judge whether the queen can be placed at each point , If possible , Then release the queen , Then process r + 1 That's ok . until r = n, The program instruction line is completed .

#include <iostream>
using namespace std;

const int N = 20;      // Positive and negative diagonal , So it is 20

// bool Array is used to determine whether the next location of the search is feasible 
// col Column ,dg Diagonals ,udg Anti diagonal , The two slashes corresponding to the point and whether there is a queen on the column 
// g[N][N] Used to save path , Storage chessboard 
int n;
char g[N][N];
bool col[N], dg[N], udg[N];        // Indicates the status bit , Not occupied as false, Otherwise true

void dfs(int u )
{
    
    if (u == n)                   // Full of chessboard , Output chessboard , Already searched n That's ok , So output this path 
    {
    
        for (int i = 0; i < n; i ++)  puts(g[i]);
           
        puts("");                // Line break 
        return;
    }
    
  for (int i = 0; i < n; i ++)    // The first  u  That's ok , The first  i  Column   Whether to release the queen 
    {
    
        if (!col[i] && !dg[u + i] && !udg[n - u + i])       // No conflict , Put the queen 
        {
    
             g[u][i] = 'Q';
             col[i] = dg[u + i] = udg[n - u + i] = true;    // Corresponding   Column ,  Oblique line   State change 
             dfs(u + 1);                                    // Process next line 
             col[i] = dg[u + i] = udg[n - u + i] = false;   // Restore the scene 
             g[u][i] = '.';
        }
    }
    return;

  
}

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;
}

You can also write like this

 if (u == n)                   // Full of chessboard , Output chessboard , Already searched n That's ok , So output this path 
    {
    
        for (int i = 0; i < n; i ++)
        {
    
            for (int j = 0; j < n; j ++)
                cout << (g[i][j]);
           
            puts("");    // Line break  
        }
        cout << endl;
        return;
    }

The time complexity is O(n!)
Diagonals dg[u + i], Anti diagonal udg[n - u + i] Subscript in u+i+i and n−u+i It means intercept

• In the following analysis (x,y) Equivalent to (u,i)
  Anti diagonal y=x+b intercept b=y−x, Because we're going to b As an array subscript , obviously b Can't be negative , So we add +n （ actually +n+4,+2n Will do ）, To ensure that the result is positive , namely y - x + n
• And diagonals y=−x+b The intercept is b=y+x=, The intercept here must be positive , So you don't need to add an offset

Method 2：

• From the first row to the first column , Start putting queens in turn

//  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 
    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;
}