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);
else
System.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.一开始的逻辑思考方向有问题,题目只给了约束条件,应该从约束条件进行思考,而非落子规律