题目描述
八皇后问题的我自己的理解写在代码注释里面
还有另一种写法,我这蒟蒻就先不写了,掌握好这一个解法就已经”撑了”
样例
import java.util.*;
public class Main{
//因为推知每一行只能有一个皇后,所以每一行默认放一个,就少创建了一个行数组row[];只创建了列\对角线\反对角线数组.
//u(行)不需要row[]数组,直接从0~n-1遍历!!!
private static int N = 20,n;
private static char[][] g = new char[N][N];
private static boolean[] cal = new boolean[N];
private static boolean[] dg = new boolean[N];
private static boolean[] udg = new boolean[N];
public static void main(String[] args){//皇后问题与顺序有直接关系,所以考虑用Dfs
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
g[i][j] = '.';//初始化
dfs(0);
}
public static void dfs(int u){
if(u == n){//从头遍历到了底下
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();
return;
}
for(int i = 0 ; i < n ; i++){
if(!cal[i] && !dg[u + i] && !udg[i - u + n]){//没有被访问过(false),进~
//说明上一行if里面的操作:列对应的元素范围就是i的范围:0~n-1;一条y = x + b的对角线与逆对角线:y = -x + b(b为常数).
//因为操作y <==> i,x <==> u,又由于减法存在需要一个偏移量n来化为正数.
g[u][i] = 'Q';
cal[i] = dg[u + i] = udg[i - u + n] = true;
dfs(u + 1);
//一下物归原主的操作
cal[i] = dg[u + i] = udg[i - u + n] = false;
g[u][i] = '.';
}
}
}
}