n-皇后问题

算法思想

1. 每一行必有一个且且有一个皇后
2. 防止一个皇后前，检查是否冲突

算法模板

import java.util.*;

public class Main {
    static int N = 10;
    static char[][] g = new char[N][N];
    // col[i]存储第 i 行的使用情况
    // dg[i]存储第 i 个对角线的使用情况
    // udg[i]存储第 i 个反对角线的使用情况
    static boolean[] col = new boolean[N],
        dg = new boolean[N * 2],
        udg = new boolean[N * 2];
    static int n;
    
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < n; j ++ )
                g[i][j] = '.';
        
        dfs(0);
    }
    
    static void dfs(int u)
    {
        if(u == n)
        {
            print();
            return ;
        }
        for(int i = 0; i < n; i ++ )
        {
            // 对角线 y = x + a, a = y - x
            // a 可能小于零，使其必然大于0
            // a = a + n
            int a = i - u + n;
            // 反对角线 x + y = b
            int b = u + i;
            if(!col[i] && !dg[a] && !udg[b])
            {
                g[u][i] = 'Q';
                col[i] = true;
                dg[a] = true;
                udg[b] = true;
                
                dfs(u + 1);
                
                col[i] = false;
                dg[a] = false;
                udg[b] = false;
                g[u][i] = '.';
            }
        }
    }
    
    static void print()
    {
        for(int i = 0; i < n; i ++ )
        {
            for(int j = 0; j < n; j ++ )
            {
                System.out.print(g[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }
}

尝试所有可能

import java.util.*;
public class Main {
    static int N = 10;
    static char[][] g = new char[N][N];
    
    static boolean[] col = new boolean[N],
        row = new boolean[N],
        dg = new boolean[N * 2],
        udg = new boolean[N * 2];
    static int n;

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0, 0, 0);
    }
    
    // 遍历所有元素（位置），尝试每个元素的所有可能
    public static void dfs(int x, int y, int s)
    {
        // 指针已移动至行尾，转移到下一行
        if(y == n)
        {
            y = 0; x ++;
        }
        // 指针已遍历完所有元素或已放置完所有皇后
        if(x == n || s == n)
        {
            if(s == n) print(); 
            return ;
        }
        
        // 不再当前位置放置皇后
        g[x][y] = '.';
        dfs(x, y + 1, s);
        
        // 尝试在当前位置放置皇后
        if(!row[x] && !col[y] && !dg[y - x + n] && !udg[x + y])
        {
            g[x][y] = 'Q';
            setState(x, y, true);
            
            dfs(x, y + 1, s + 1);
            
            setState(x, y, false);
            g[x][y] = '.';
        }
    }
    
    public static void print()
    {
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < n; j ++)
            {
                System.out.print(g[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }
    
    public static void setState(int x, int y, boolean flag)
    {
        row[x] = flag;
        col[y] = flag;
        dg[y - x + n] = flag;
        udg[x + y] = flag;
    }
}