$$\color{Red}{n-皇后问题 三种语言}$$

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

思路

N皇后问题所引出的——对主对角线和副对角线的映射问题

if (!col[i] && !dg[u + i] && !udg[n - u + i]) //加上n是为了防止下标越界
这里采用数形结合的思想，主要的目的是把相同对角线所对应的元素找到一个统一的映射方法（截距）

java 代码

import java.io.*;

public class Main {
    static int N = 10, n;
    static char[][] path = new char[N][N];
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[2 * N];
    static boolean[] udg = new boolean[2 * N];
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void dfs(int x) throws IOException {
        if (x == n) {
            for (int i=0; i<n; i++) {
                bw.write(path[i], 0, n);
                bw.newLine();
            }
            bw.newLine();
            bw.flush();
            return;
        }
        for(int i=0; i<n; i++)
            if (!col[i] && !dg[i + x] && !udg[i - x + n]) {
                path[x][i] = 'Q';
                col[i] = dg[i+x] = udg[i-x+n] = true;
                dfs(x+1);
                col[i] = dg[i+x] = udg[i-x+n] = false;
                path[x][i] = '.';
            }

    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                path[i][j] = '.';
        dfs(0);
    }
}

python3 代码

N = int(10)
path = [['.']*N for i in range(N)]
col = [1] * N     
dg = [1] * (2*N) 
udg = [1] * (2*N) 

n = int(input())

def dfs(x):
    if x == n:
        for i in range(n):
            for j in range(n):
                print(path[i][j], end = '')
            print()
        print()
        return 

    for i in range(n):
        if col[i] and dg[x+i] and udg[x-i+n]:
            path[x][i] = 'Q'
            col[i] = dg[x+i] = udg[x-i+n] = 0
            dfs(x+1)
            col[i] = dg[x+i] = udg[x-i+n] = 1
            path[x][i] = '.'

dfs(0)

C++代码

#include <iostream>

using namespace std;

const int N = 10;
char g[N][N];
int n;
bool col[N], dg[N * 2], udg[N * 2];

//dfs(n)代表下标为n的行号，for进入对该行每位的判断
//不符合条件的情况，就不进入后续递归———俗称剪枝
void dfs(int x)
{
    if(x == n)
    {
        //put可以对这个二维数组对应行数开始一直输出
        //当遇到'/0'则停止，且自动换行
        for(int i=0; i<n; i++)  puts(g[i]);
        puts("");
        //这里return可以删除 因为后面的剪枝———
        //即所谓的if语句根本不会进
        return;
    }
    for(int i=0; i<n; i++)
    {
        //x代表着行数，也就是对应y值,那么i代表着换列判断
        //那我们就当成x（其实我们可以颠倒看，因为我们最终
        //目的都是使得产生一组映射关系，使得我们可以锁定
        //对应的对角线）
        //对于y = x + n, y = -x + n,移项即可得到对应的n值
        if(!col[i] && !dg[i + x] && !udg[x - i + n])
        //剪枝——不符合条件的我们就不递归到深层
        {
            g[x][i] = 'Q';
            col[i] = dg[i + x] = udg[x - i + n] = true;
            //符合条件的我们就递归下一行，一旦后续进行不下去
            //也会一层层跳回最初的dfs，再进行现场还原
            //然后根据外层dfs进入下一树分支
            dfs(x+1);
            col[i] = dg[i + x] = udg[x - i + n] = false;
            g[x][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;
}