当前位置: 首页 > article >正文

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


http://www.kler.cn/a/589051.html

相关文章:

  • 7、基于osg引擎实现读取vtk数据通过着色器实现简单体渲染(1)
  • go 安装swagger
  • 1.Qt SDK 的下载和安装
  • matlab 三维桥式起重机系统数学模型
  • 2025高频面试算法总结篇【递归回溯动态规划】
  • windows 下用docker 部署nginx
  • unity基础——Navigation导航系统
  • 网络安全设备系统集成方案 系统集成和网络安全
  • 命令行参数和环境变量【Linux操作系统】
  • 【论文笔记】Best Practices and Lessons Learned on Synthetic Data for Language Models
  • BigEvent项目后端学习笔记(一)用户管理模块 | 注册登录与用户信息全流程解析(含优化)
  • 数据增强常见问题与解决方案:提升AI模型性能的关键技巧
  • PyCharm如何有效地添加源与库?
  • CSS中固定定位
  • 错误记录: git 无法连接到github
  • Apache Pol (excel)
  • 算法——图论——关键活动
  • Python的那些事第四十五篇:继承自Nose的测试框架Nose2
  • 区间预测 | Matlab实现QRBiTCN分位数回归双向时间卷积神经网络注意力机制时序区间预测
  • Ubuntu 一站式初始化笔记