题目描述
n皇后问题
java 代码
import java.util.Scanner;
/**
* @author LSN
* @Date 2022/2/21
*/
public class Main {
public static int map[];
public static boolean exist[];
public static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
map = new int[n+1];
exist = new boolean[n+1];
dfs(1);
}
//深度优先遍历
public static void dfs(int step){
//到了第n+1步(放满了前n行)
if(step==n+1){
printMap();
return;
}
//尝试第一行的1-n每个位置
for(int pos=1;pos<=n;pos++){
if(exist[pos]==false){
int j=1;
//检查是否与前面step-1个皇后冲突
while(j<step){
if(pos==map[j] || Math.abs(pos-map[j])==Math.abs(step-j)){
break;
}
j++;
}
//如果都不冲突
if(j==step){
//在[step,pos]处落子
map[step]=pos;
exist[pos]=true;
dfs(step+1);
exist[pos]=false;
}
}
}
}
//打印符合要求的棋盘
public static void printMap(){
for(int i=1;i<=n;i++){
int q = map[i];
for(int j=1;j<=n;j++){
if(q!=j) System.out.print(".");
else System.out.print("Q");
}
System.out.println();
}
System.out.println();
}
}