N皇后问题——dfs解法(回溯+减枝+深搜)

一.题目

这是一道很经典的题，首先分析一下题目，就是在棋盘上下棋，但是同一行，同一列，对角线上不能有棋子，否则无法落子，那这些信息也就是约束条件，模拟这些信息就是减枝函数的内容

既然它落子没有规律，只有位置有约束条件，那么我们就可以根据位置来考虑，不能同一行，同一列，同一对角线，那么我们就可以一行下一个，然后判断同一列，同一对角线是否有棋子，同理按其中三个随便一个约束条件来进行搜索，只需要满足其他两个约束条件就可以

代码如下：

public class Main {public static int sum = 0; public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();if(n<=2)//首先把临界状况写出来{if(n==1)System.out.println(1);elseSystem.out.println(0);return;}boolean[][] mark = new boolean[n][n];for(int i = 0;i<n;i++)//这里主要mark是数组,是引用类型变量,在方法中会对它的值进行改变,
//但是我们进行了回溯操作,每次调用完都会回到初始值,所以不用担心递归污染{dfs(0,i,mark,1);//这里在第一行已经落子,所以index初始值为1}System.out.println(sum);scan.close();}public static void dfs(int x,int y,boolean[][]mark,int index){if(!cheak(x,y,mark))//不满足约束条件return;if(index == mark.length)//下够n个直接return{sum++;return;}mark[x][y] = true;for(int i = 0;i<mark.length;i++)dfs(x+1,i,mark,index+1);//x+1代表继续搜索下一行mark[x][y] = false;//回溯语句}public static boolean cheak(int x,int y,boolean[][]mark)//减枝函数{if(x<0||x>=mark.length||y<0||y>=mark.length)//是否在棋盘范围内return false;for(int i = 0;i<mark.length;i++)//是否在同一列{if(mark[i][y]==true)return false;}//是否在同一对角线for(int i = x,j = y;i>=0&&i<mark.length&&j>=0&&j<mark.length;i--,j--){if(mark[i][j]==true)return false;}for(int i = x,j = y;i>=0&&i<mark.length&&j>=0&&j<mark.length;i--,j++){if(mark[i][j]==true)return false;}//如果都满足就可以落子return true;}
}

本题犯错：

1.当n为1时判断错误,是有一种情况的，而非0种，思考不够全面

2.我们这里是对行进行搜索，在cheak里面应该对列进行判断，写成行了，粗心问题

3.本题其实还可以优化，懒得改了，测试用例全部通过

4.在主函数调用dfs时实际上第一行已经落子了，一开始将index写成0了，粗心问题

5.一开始的逻辑思考方向有问题，题目只给了约束条件，应该从约束条件进行思考，而非落子规律