N皇后

是典型的回溯问题,不过做这个题目,花了周日一天的时间,这一天时间,大部分时间都在思考出现问题的原因。这里也通过leetcode的提交记录,来回顾下做这题的心路历程,顺别加深对此类问题的求解。

在第一次解答,没有沿用之前的思路,只想到了递归,对于递归之外的问题模糊不清,就提笔了,结果可想而知,前后碰壁,在leetcode上甚至没有通过第一个测试用例。主要问题是对递归的思想还是不清晰,对参数的了解还是理解的不够透彻。客观评价,甚至是没有递归的影子。

  • 很明显的,对于这类需要输出每个解的题目,都需要递归调用最后的结果参数,并且在golang中,这个参数必须是个指针;
  • 其次是单次的结果,对于golang来说,这个也是很重要的,每个单次的结果,不能直接在结果上进行append,这中操作发生了很多次,造成的结果就是每次产生结果都是一致的;
  • 最后,对于每次结果的输入和输出,都需要保持前后一次性,拿本题距离,放置一枚棋子,必然需要标记改换后影响的各个位置,遍历结束之后,收起此枚皇后,又需要还原此次产生的影响。

以上这三个点都是在递归问题中,必须每次严格的遵守的。
今天的皇后问题,就是在这之上,花费了太多的时间,做了很多无用功。
当然,N皇后问题也有它的难点,个人认为应该将时间都花在这些问题的处理上,而不是上面那些有实际模板的问题上。N皇后的问题难点就在于剪枝问题的处理上,对于剪枝问题上,笔者启先,简单的使用二维数组,简单的使用皇后规则,落子添加标记,起子删除标记,可是这明显存在bug,最后看了题解,处理方法是分别记录横竖,对角线这四个维度的标记。

今天是血泪教训的一天,下周继续,将挑战新的题目,依然是递归类型的。


发表评论

电子邮件地址不会被公开。 必填项已用*标注