代码随想录算法训练营第三十天| 51. N皇后 37. 解数独 总结

发布时间 2023-09-03 21:33:28作者: 银河小船儿
       卡哥建议:今天这三道题都非常难,那么这么难的题,为啥一天做三道? 因为 一刷 也不求大家能把这么难的问题解决,所以 大家一刷的时候,就了解一下题目的要求,了解一下解题思路,不求能直接写出代码,先大概熟悉一下这些题,二刷的时候,随着对回溯算法的深入理解,再去解决如下三题。 大家今天的任务,其实是 对回溯算法章节做一个总结就行。 
重点是看 回溯算法总结篇:
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

51. N皇后(可跳过) 

https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html

   视频讲解:https://www.bilibili.com/video/BV1Rd4y1c7Bq

   做题思路:

   可以用动画的方式理解。

   首先来看一下皇后们的约束条件:

  1. 不能同行
  2. 不能同列
  3. 不能同斜线

   确定完约束条件,来看看究竟要怎么去搜索皇后们的位置,其实搜索皇后的位置,可以抽象为一棵树。

   下面我用一个 3 * 3 的棋盘,将搜索过程抽象为一棵树,如图:

 

 

    从图中,可以看出,二维矩阵中矩阵的高就是这棵树的高度,矩阵的宽就是树形结构中每一个节点的宽度。

    那么我们用皇后们的约束条件,来回溯搜索这棵树,只要搜索到了树的叶子节点,说明就找到了皇后们的合理位置了。

 

37. 解数独(可跳过) 

https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html

    视频讲解:https://www.bilibili.com/video/BV1TW4y1471V