AcWing 843. n-皇后问题

# N 皇后问题 - DFS

#include <iostream>

using namespace std;

const int N = 20;

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

void dfs(int u){
	if(u == n){
		for(int i = 0; i < n; i++) puts(g[i]);
		puts("");
		return;
	}
	for(int i = 0; i < n; i++){
		if(!col[i] && !dg[u + i] && !udg[n - u + i]){
		//这个 偏移量 相当于 把 负数和 这个数 简单的映射了 一下
			g[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n - u + i] = true;
			dfs(u + 1);
			col[i] = dg[u + i] = udg[n - u + i] = false;
			g[u][i] = '.';
		}
	}
}
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;
}

# 为什么求截距就可以判断两个点在一条对角线或者反对角线呢？

因为b可以唯一确定一条直线，在同一条直线上面b都是相同的，所以以b为下标是可以繁殖对角线和反对角线上面放皇后的

#include <iostream>

using namespace std;

const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s){
	if(y == n){
		y = 0;
		x ++;
	}
	if(x == n){
		if(s == n){
			for(int i = 0; i < n; i++) puts(g[i]);
			puts("");
		}
		return;
	}
	//不放皇后
	dfs(x, y + 1, s);
	//放皇后
	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] = '.';
	}
}
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;
}

懒猫老师 - C 语言 - 递归函数 - 八皇后问题 (搜索，回溯)- 哔哩哔哩

<iframe src="http://player.bilibili.com/player.html?aid=76265320&bvid=BV1wJ411U7Gy&cid=130453660&page=1" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true" width="500px" height="500px"> </iframe>

![[Pasted image 20221225161908.png]]

//枚举方法1
// #include <iostream>

// using namespace std;

// const int N = 20;

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

// void dfs(int u){
//     if(u == n){
//         for(int i = 0;i < n; i++) puts(g[i]);
//         puts("");
//         return;
//     }
    
//     for(int i = 0; i < n; i++)
//         if(!col[i] && !dg[u+ i] && !udg[n - u + i]){//剪枝
//             g[u][i] = 'Q';
//             col[i] = dg[u + i] = udg[n - u + i] = true;//截距如下
//             //y = x + b                                                                                            y = -x + b
//             //b = y - x 因为 y - x 是负数，而数组下标不能为负数 所以给他加个偏移量 即 b = y - x + n                b =  y + x
//             dfs(u + 1);
//             col[i] = dg[u + i] = udg[n - u + i] = false;//恢复现场
//             g[u][i] = '.';
//         }
// }

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



//枚举方法2
#include <iostream>

using namespace std;

const int N = 20;

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

void dfs(int x, int y, int s){
    if(y == n) y = 0, x++;
    
    if(x == n){
        if(s == n){
            for(int i = 0; i < n; i++) puts(g[i]);
            puts("");
        }
        
        return;
        //这边return下面那个dfs也会return出去到dfs下面的if去的
    }
    
    //不放皇后
    dfs(x, y + 1, s);
    
    //放皇后
    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] = '.';
    }
}

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