摘要本文以4皇后问题为例用通俗易懂的大白话讲解了回溯算法的核心思想。文章首先介绍了N皇后问题的规则在N×N棋盘上每行摆一个皇后要求任意两个皇后不在同一行、同一列和同一对角线上。随后通过逐步手撕4皇后问题的过程演示了尝试→失败→回溯→再尝试的完整流程最终得出两种合法摆法并总结出镜像对称的规律以减少重复计算。最后结合2015年上半年软考真题将回溯思想应用于实际考试题目分析帮助读者理解回溯算法在算法设计与考试中的应用。目录一.先直接看一个例子(可大白话理解)二.手撕上述“4皇后问题”纯大白话包你理解1.先说一下核心思路2.开始手撕方案一第一行的棋子摆到第一列①第一行直接摆第一列②第二行找到第一个能摆放的位置③第三行所有位置都摆不下了此时第三行无解④关键动作由于此时第三行无解所以我们“回溯”到第二行重新摆一下第二行的棋子⑤第三行找到能摆放的第一个位置⑥第四行所有位置都摆不下此时第四行无解⑦由于此时第四行无解所以我们“回溯”到第三行重新摆一下第三行的棋子⑧此时第三行也无解了回溯到第二行⑨第二行也无解了只能回溯到第一行重新摆一下第一行的棋子。方案二第一行的棋子摆到第二列①第一行摆到第二列②第二行发现只能摆到第四列③第三行摆到第一列能摆就先摆下至于后面几列能不能摆放后续会回来考虑④第四行摆到第三列此时得出第一个成功案例⑤再试试第四行后面的列发现不行⑥回溯到第三行试试后面的几列能不能摆发现不行⑦回溯到第二行由于第二行的棋子已经在最后一列退无可退所以也不能贪了⑧回溯到第一行摆放到其他列方案三方案三和方案二是镜像水平翻转所以不用摆就知道成功案例就是方案二的成功案例的水平镜像方案四方案四和方案一是镜像水平翻转所以不用摆就知道方案四也没有成功案例3.总结“4皇后问题”得到以下两种摆法4.感悟实战软考真题(2015-上半年)1.题目2.问题3.分析4.官方答案一.先直接看一个例子(可大白话理解)如下图我要声明几点N皇后问题要求棋盘必须是正方形下图是一个正方形棋盘由于长宽4所以此时就可以叫“4皇后问题”每一行要摆一个棋子由于一共有4行所以我们要摆4个棋子摆放的要求每个棋子之间要满足下面三个需求①任意两个棋子不能在同一行②任意两个棋子不能在同一列③任意两个棋子不能在同一对角线二.手撕上述“4皇后问题”纯大白话包你理解1.先说一下核心思路我们直接一行一行遍历一行只摆一个多了不摆。这样天然就可以防止两个棋子在同一行因为我们自己规定一行只能摆一个2.开始手撕方案一第一行的棋子摆到第一列①第一行直接摆第一列②第二行找到第一个能摆放的位置叉号表示违反了我们上述说的规矩即不能同一列、不能同一对角线③第三行所有位置都摆不下了此时第三行无解④关键动作由于此时第三行无解所以我们“回溯”到第二行重新摆一下第二行的棋子⑤第三行找到能摆放的第一个位置⑥第四行所有位置都摆不下此时第四行无解⑦由于此时第四行无解所以我们“回溯”到第三行重新摆一下第三行的棋子可见即使回溯到第三行第三行也没有其他位置可以摆放了只能回溯到第二行了⑧此时第三行也无解了回溯到第二行由于此时第二行的棋子已经摆放到了最后一个位置退无可退所以第二行也无解⑨第二行也无解了只能回溯到第一行重新摆一下第一行的棋子。由于第一行的棋子摆到第一列时没有符合规则的方案所以方案一无效。因此只能将第一行的棋子摆到第二列试试开启方案二方案二第一行的棋子摆到第二列①第一行摆到第二列②第二行发现只能摆到第四列③第三行摆到第一列能摆就先摆下至于后面几列能不能摆放后续会回来考虑④第四行摆到第三列此时得出第一个成功案例⑤再试试第四行后面的列发现不行可见此时第四行的第四列也不能摆所以我们再回头试试第三行的后面几列⑥回溯到第三行试试后面的几列能不能摆发现不行⑦回溯到第二行由于第二行的棋子已经在最后一列退无可退所以也不能贪了⑧回溯到第一行摆放到其他列由于第一行的棋子要摆到下一列此时就不属于方案二的范畴了开启方案三。方案三方案三和方案二是镜像水平翻转所以不用摆就知道成功案例就是方案二的成功案例的水平镜像方案四方案四和方案一是镜像水平翻转所以不用摆就知道方案四也没有成功案例3.总结“4皇后问题”得到以下两种摆法4.感悟其实经过上述手撕该过程不难发现第一行的棋子分别摆放在第1、2、3、4列分别对应四个方案四个方案中方案一、方案四是镜像水平翻转的关系。所以一个有成功案例另一个肯定有成功案例一个没有成功案例另一个也没有成功案例方案二、方案三是镜像水平翻转的关系。所以一个有成功案例另一个肯定有成功案例一个没有成功案例另一个也没有成功案例实战软考真题(2015-上半年)1.题目2.问题3.分析举个例子吧在4皇后问题中假设pos[i]这个一维数组的值是[2, 4, 1, 3]则表示第1~4行的棋子分别摆放在了2、4、1、3列。说白了就是下标就是行元素的值就是列注意我们这个pos数组是直接人为略过下标0因为用着不舒服和棋盘对不上。举例pos [2, 4, 1, 3]那么下标1即第一行的值是2说明棋子摆到了第二列。就这么简单。这也是为什么一维数组就能表示棋盘的摆法的原因。4.官方答案以上就是本篇文章的全部内容喜欢的话可以留个免费的关注呦~~~