DFS在我看来就是一条路走到黑,直到无路可走的情况下,才会选择回头,然后重新选择一条路(官方说法即“优先考虑深度”)整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
public class Main{
static int []path=new int[10];// 从0到n-1共n个位置 存放一个排列
static boolean []sta=new boolean[10];
// 存放每个数字的使用状态 true表示使用了 false表示没使用过
static int n;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
dfs(0); // 在path[0]处开始填数
}
private static void dfs(int u) {
if(u==n){ // 一个排列填充完成
for (int i = 0; i < n; i++) {
System.out.print(path[i]+" ");
}
System.out.println();
return;
}
for(int i=1;i<=n;i++){
if (!sta[i]) {
path[u]=i; // 把 i 填入数字排列的位置上
sta[i]=true; // 表示该数字用过了 不能再用
dfs(u+1); // 这个位置的数填好 递归到右面一个位置
sta[i]=false; // 恢复现场 该数字后续可用
}
}
}
}
每一行必定有一个皇后,对行进行深度遍历。
对于第 r 行的第 i 个位置,判断每个点是否可以放皇后,如果可以,则放皇后,然后处理 r + 1 行。
直到 r = n,程序指行完毕。
import java.util.Scanner;
public class Main{
static int N=11,n;
static char [][]q=new char[N][N]; //存储棋盘
static boolean []cor=new boolean[N]; //判断列是否有皇后
static boolean []dg=new boolean[N*2]; //判断对角线是否有皇后,n * n的矩阵,存在r + i也就是行加上列求截距的操作,必须开两倍大否则就爆了
static boolean []udg=new boolean[N*2]; //判断反对角线是否有皇后
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
q[i][j]='.';
}
}
dfs(0);
}
private static void dfs(int r) {
if(r==n){ //代表棋盘处理完毕,是结束出口
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(q[i][j]);
}
System.out.println();
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) { //第r行,第i列是否可以放皇后
//对角线y1=x1+b1,y2=-x2+b2,那么b1=y1-x1,b2=y2+x2
//为了防止y1-x1是个负数,加上偏移量n
if(!cor[i] &&!dg[i+r] &&!udg[r-i+n]){
q[r][i]='Q';
cor[i]=dg[i+r]=udg[r-i+n]=true;
dfs(r+1); //去下一行遍历
cor[i]=dg[i+r]=udg[r-i+n]=false; //恢复现场
q[r][i]='.';
}
}
}
}
感谢你能看完,希望对你有帮助 ,如有错误欢迎指正,码字不易,给个赞呗