正则表达式(回溯法密码问题)
正则表达式(回溯法密码问题)
首先我们要了解正则表达式是什么，它是一种匹配模式， 不仅能匹配匹配字符，还能匹配位置 ，不少人忽略了匹配字符这个作用，往往碰到这种问题就手足无措。
如果正则只有精确匹配是没有多大意义的，比如：
正则表达式的强大之处在于它的模糊匹配，分为横向模糊和纵向模糊
横向模糊：一个正则可匹配的字符串的长度不是固定的，可以是多种情况的
其实现的方式是使用量词：
比如：
横向模糊匹配到了多种情况，案例中用的正则是/ab{2,5}c/g，后面多了g，它是正则的一个修饰符。表示全局匹配，即在目标字符串中按顺序找到满足匹配模式的所有子串，强调的是“所有”，而不只是“第一个”。
纵向模糊：一个正则匹配的字符串，具体到某一位字符时，它可以不是某个确定的字符，可以有多种可能
其实现的方式是使用范围类
-表示连字符，在此处作特殊用处，但是如果我要匹配'a-z'这三个字符呢？可以这么写：
这样引擎就不会认为它们是一个氛围了， 符号在范围类中起取反的作用， a表示除了a的所有字符。
系统根据范围类又预定义了一些类方便我们使用：
不加g就是惰性匹配，我匹配完一个就不敢了，懒得再干其他事儿了，加了g就是贪婪模式了,我现在精力无限，会尽可能的干事儿，但是我还有些理智，不会干超出能力之外的事儿，比如你给我的范围是{2,5}，我会尽可能做5件事儿，但是不会超过5件事,反正只要在能力范围内，越多越好
此时我既想尽可能的匹配又想让它不那么贪婪有没有办法呢？办法是有的, 贪婪模式一般作用在量词这里，限制在量词这里就好了 ，可以在量词这里加一个？即可搞定。
其中/\d{2,5}?/表示，虽然2到5次都行，当2个就够的时候，就不在往下尝试了。
此时就达到了我们的要求,不过这里完全是为了讲解贪婪模式和惰性模式，并不推荐这么做，我完全可以将{2,5}改成{2}，一样的效果
知道了惰性模式的原理，我们完全可以鼓捣出其他的各式各样的情形：
一个模式可以实现横向和纵向模糊匹配。而多选分支可以支持多个子模式任选其一
具体形式如下：(p1|p2|p3)，其中p1、p2和p3是子模式，用“|”（管道符）分隔，表示其中任何之一
但有个事实我们应该注意，比如我用/good|goodbye/，去匹配"goodbye"字符串时，结果是"good"
而把正则改成/goodbye|good/，结果是
也就是说，分支结构也是惰性的，即当前面的分支匹配上了，后面的就不再尝试了
并且，使用分支的时候注意使用括号，
匹配字符，无非就是范围类、量词和分支结构的组合使用罢了
分析：
表示一个16进制字符，可以用范围类[0-9a-fA-F]
其中字符可以出现3或6次，需要是用量词和分支结构
使用分支结构时，需要注意顺序(惰性)
分析：
对每个地方的数字进行分析：
共4位数字，第一位数字可以为[0-2]。
当第1位为2时，第2位可以为[0-3]，其他情况时，第2位为[0-9]。
第3位数字为[0-5]，第4位为[0-9]
如果也要求匹配7:9，也就是说时分前面的0可以省略:
分析：
年，四位数字即可，可用[0-9]{4}。
月，共12个月，分两种情况01、02、……、09和10、11、12，可用(0[1-9]|1[0-2])。
日，最大31天，可用(0[1-9]|[12][0-9]|3[01])
分析：
整体模式是: 盘符:\文件夹\文件夹\文件夹
其中匹配F:\，需要使用[a-zA-Z]:\，其中盘符不区分大小写，注意\字符需要转义。
文件名或者文件夹名，不能包含一些特殊字符，此时我们需要排除范围类[ \:*|"?\r\n/]来表示合法字符。另外不能为空名，至少有一个字符，也就是要使用量词+。因此匹配“文件夹\”，可用[ \:*|"?\r\n/]+\。
另外“文件夹\”，可以出现任意次。也就是([^\: |"?\r\n/]+\) 。其中括号提供子表达式。
路径的最后一部分可以是“文件夹”，没有\，因此需要添加([^\:*|"?\r\n/]+)?。
最后拼接成了一个看起来比较复杂的正则：
用到了惰性匹配，防止把class也提取出来
优化：
^（脱字符）匹配开头，在多行匹配中匹配行开头。
$（美元符号）匹配结尾，在多行匹配中匹配行结尾
比如我们把字符串的开头和结尾用"#"替换（位置可以替换成字符的！）：
多行匹配模式时，二者是行的概念，这个需要我们的注意
\b是单词边界，具体就是\w和\W之间的位置，也包括\w和^之间的位置，也包括\w和$之间的位置
首先，我们知道，\w是范围类[0-9a-zA-Z_]的简写形式，即\w是字母数字或者下划线的中任何一个字符。而\W是排除范围类[^0-9a-zA-Z_]的简写形式，即\W是\w以外的任何一个字符
此时我们可以看看"[#JS#] #Lesson_01#.#mp4#"中的每一个"#"，是怎么来的。
第一个"#"，两边是"["与"J"，是\W和\w之间的位置。
第二个"#"，两边是"S"与"]"，也就是\w和\W之间的位置。
第三个"#"，两边是空格与"L"，也就是\W和\w之间的位置。
第四个"#"，两边是"1"与"."，也就是\w和\W之间的位置。
第五个"#"，两边是"."与"m"，也就是\W和\w之间的位置。
第六个"#"，其对应的位置是结尾，但其前面的字符"4"是\w，即\w和$之间的位置。
知道了\b的概念后，那么\B也就相对好理解了。
\B就是\b的反面的意思，非单词边界。例如在字符串中所有位置中，扣掉\b，剩下的都是\B的。
具体说来就是\w与\w、\W与\W、^与\W，\W与$之间的位置
exp1(?=exp2) 表达式会匹配exp1表达式，但只有其后面内容是exp2的时候才会匹配
exp1(?=exp2) 表达式会匹配exp1表达式，但只有其后面内容不是exp2的时候才会匹配
(?=p)，其中p是一个子模式，即p前面的位置
比如(?=l)，表示'l'字符前面的位置，例如：
而(?!p)就是(?=p)的反面意思
对于位置的理解，我们可以理解成空字符""
因此，把/ hello$/写成/ ^hello$$$/，是没有任何问题的：
也就是说字符之间的位置，可以写成多个。
把位置理解空字符，是对位置非常有效的理解方式
此正则要求只有一个字符，但该字符后面是开头。
比如把"12345678"，变成"12,345,678"。
可见是需要把相应的位置替换成","
使用(?=\d{3}$)就可以做到：
因为逗号出现的位置，要求后面3个数字一组，也就是\d{3}至少出现一次。
此时可以使用量词+：
此时会出现问题：
上面的正则，仅仅表示把从结尾向前数，一但是3的倍数，就把其前面的位置替换成逗号
怎么解决呢？我们要求匹配的到这个位置不能是开头。
我们知道匹配开头可以使用^，但要求这个位置不是开头怎么办？
easy，(?!^)
如果要把"12345678 123456789"替换成"12,345,678 123,456,789"。
此时我们需要修改正则，把里面的开头^和结尾$，替换成\b
其中(?!\b)怎么理解呢？
要求当前是一个位置，但不是\b前面的位置，其实(?!\b)说的就是\B。
因此最终正则变成了：/\B(?=(\d{3})+\b)/g
此题，如果写成多个正则来判断，比较容易。但要写成一个正则就比较困难。
那么，我们就来挑战一下。看看我们对位置的理解是否深刻
我们可以把原题变成下列几种情况之一：
1.同时包含数字和小写字母
2.同时包含数字和大写字母
3.同时包含小写字母和大写字母
4.同时包含数字、小写字母和大写字母
上面的正则看起来比较复杂，只要理解了第二步，其余就全部理解了。
/(?=.*[0-9])^[0-9A-Za-z]{6,12}$/
对于这个正则，我们只需要弄明白(?=.*[0-9])^即可。
分开来看就是(?=.*[0-9])和^。
表示开头前面还有个位置（当然也是开头，即同一个位置，想想之前的空字符类比）。
(?=. [0-9])表示该位置后面的字符匹配. [0-9]，即，有任何多个任意字符，后面再跟个数字。
另一种解法：
“至少包含两种字符”的意思就是说，不能全部都是数字，也不能全部都是小写字母，也不能全部都是大写字母。
那么要求“不能全部都是数字”，怎么做呢？(?!p)出马！
三种'都不能'呢？
1.分组和分支结构
括号是提供分组功能，使量词'+'作用于z和这个整体
而在多选分支结构(p1|p2)中，此处括号的作用也是不言而喻的，提供了子表达式的所有可能
而要使用它带来的好处，必须配合使用实现环境的API
以日期为例。假设格式是yyyy-mm-dd的
提取数据：
match返回的一个数组，第一个元素是整体匹配结果，然后是各个分组（括号里）匹配的内容，然后是匹配下标，最后是输入的文本
可以使用正则对象的exec方法：
也可以使用构造函数的全局属性$1至$9来获取：
替换:
想把yyyy-mm-dd格式，替换成mm/dd/yyyy怎么做？
反向引用:
比如要写一个正则支持匹配如下三种格式：
注意里面的\1，表示的引用之前的那个分组(-|/|.)。不管它匹配到什么（比如-），\1都匹配那个同样的具体某个字符
括号嵌套怎么办？
以左括号（开括号）为准
\10是表示第10个分组，还是\1和0呢？答案是前者，虽然一个正则里出现\10比较罕见
引用不存在的分组会怎样？
因为反向引用，是引用前面的分组，但我们在正则里引用了不存在的分组时，此时正则不会报错，只是匹配反向引用的字符本身。例如\2，就匹配"\2"。注意"\2"表示对2进行了转意
非捕获分组:
之前文中出现的分组，都会捕获它们匹配到的数据，以便后续引用，因此也称他们是捕获型分组。
如果只想要括号最原始的功能，但不会引用它，即，既不在API里引用，也不在正则里反向引用。此时可以使用非捕获分组(?:p)
第二种，匹配整个字符串，然后用引用来提取出相应的数据
思路是找到每个单词的首字母，当然这里不使用非捕获匹配也是可以的
首字母不会转化为大写的。其中分组(.)表示首字母，单词的界定，前面的字符可以是多个连字符、下划线以及空白符。正则后面的?的目的，是为了应对str尾部的字符可能不是单词字符，比如str是'-moz-transform '
通过key获取相应的分组引用，然后作为对象的键
匹配一个开标签，可以使用正则[^]+，
匹配一个闭标签，可以使用/[^]+，
但是要求匹配成对标签，那就需要使用反向引用
其中开标签[ ]+改成([ ]+)，使用括号的目的是为了后面使用反向引用，而提供分组。闭标签使用了反向引用，/\1。
另外[\d\D]的意思是，这个字符是数字或者不是数字，因此，也就是匹配任意字符的意思
而当目标字符串是"abbbc"时，就没有所谓的“回溯”。其匹配过程是：
其中子表达式b{1,3}表示“b”字符连续出现1到3次。
图中第5步有红颜色，表示匹配不成功。此时b{1,3}已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式c，去匹配字符“c”。当然，此时整个表达式匹配成功了。
图中的第6步，就是“回溯”。
你可能对此没有感觉，这里我们再举一个例子。正则是：
目标字符串是"abbbc"，匹配过程是：
其中第7步和第10步是回溯。第7步与第4步一样，此时b{1,3}匹配了两个"b"，而第10步与第3步一样，此时b{1,3}只匹配了一个"b"，这也是b{1,3}的最终匹配结果。
这里再看一个清晰的回溯，正则是：
目标字符串是："acd"ef，匹配过程是：
图中省略了尝试匹配双引号失败的过程。可以看出“.*”是非常影响效率的。
为了减少一些不必要的回溯，可以把正则修改为/"[^"]*"/。
正则表达式匹配字符串的这种方式，有个学名，叫回溯法。
回溯法也称试探法，它的基本思想是： 从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法” 。
本质上就是深度优先搜索算法。其中 退到之前的某一步这一过程，我们称为“回溯” 。从上面的描述过程中，可以看出，路走不通时，就会发生“回溯”。即， 尝试匹配失败时，接下来的一步通常就是回溯
道理，我们是懂了。那么JS中正则表达式会产生回溯的地方都有哪些呢？
3.1 贪婪量词
之前的例子都是贪婪量词相关的。比如b{1,3}，因为其是贪婪的，尝试可能的顺序是从多往少的方向去尝试。首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。如果还不行呢？只能说明匹配失败了。
虽然局部匹配是贪婪的，但也要满足整体能正确匹配。否则，皮之不存，毛将焉附？
此时我们不禁会问，如果当多个贪婪量词挨着存在，并相互有冲突时，此时会是怎样？
答案是，先下手为强！因为深度优先搜索。测试如下：
其中，前面的\d{1,3}匹配的是"123"，后面的\d{1,3}匹配的是"45"。
3.2 惰性量词
惰性量词就是在贪婪量词后面加个问号。表示尽可能少的匹配，比如：
其中\d{1,3}?只匹配到一个字符"1"，而后面的\d{1,3}匹配了"234"。
虽然惰性量词不贪，但也会有回溯的现象。比如正则是：
目标字符串是"12345"，匹配过程是：
知道你不贪、很知足，但是为了整体匹配成，没办法，也只能给你多塞点了。因此最后\d{1,3}?匹配的字符是"12"，是两个数字，而不是一个。
3.3 分支结构
我们知道分支也是惰性的，比如/can|candy/，去匹配字符串"candy"，得到的结果是"can"，因为分支会一个一个尝试，如果前面的满足了，后面就不会再试验了。
分支结构，可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分支。这种尝试也可以看成一种回溯。
比如正则：
目标字符串是"candy"，匹配过程：
上面第5步，虽然没有回到之前的状态，但仍然回到了分支结构，尝试下一种可能。所以，可以认为它是一种回溯的
简单总结就是，正因为有多种可能，所以要一个一个试。直到，要么到某一步时，整体匹配成功了；要么最后都试完后，发现整体匹配不成功。
既然有回溯的过程，那么匹配效率肯定低一些。相对谁呢？相对那些DFA引擎。
而JS的正则引擎是NFA，NFA是“非确定型有限自动机”的简写。
大部分语言中的正则都是NFA，为啥它这么流行呢？
答：你别看我匹配慢，但是我编译快啊，而且我还有趣哦。
而在正则表达式中，操作符都体现在结构中，即由特殊字符和普通字符所代表的一个个特殊整体。
JS正则表达式中，都有哪些结构呢？
其中涉及到的操作符有：
上面操作符的优先级从上至下，由高到低。
这里，我们来分析一个正则：
因为是要匹配整个字符串，我们经常会在正则前后中加上锚字符^和$。
比如要匹配目标字符串"abc"或者"bcd"时，如果一不小心，就会写成/^abc|bcd$/。
而位置字符和字符序列优先级要比竖杠高，故其匹配的结构是：
应该修改成:
2.2 量词连缀问题
假设，要匹配这样的字符串：
此时正则不能想当然地写成/^[abc]{3}+$/，这样会报错，说“+”前面没什么可重复的：
此时要修改成：
2.3 元字符转义问题
所谓元字符，就是正则中有特殊含义的字符。
所有结构里，用到的元字符总结如下：
当匹配上面的字符本身时，可以一律转义：
在string中，也可以把每个字符转义，当然，转义后的结果仍是本身：
现在的问题是，是不是每个字符都需要转义呢？否，看情况。
2.3.1 范围类中的元字符
跟范围类相关的元字符有 []、^、- 。因此在会引起歧义的地方进行转义。例如开头的^必须转义，不然会把整个范围类，看成反义范围类。
2.3.2 匹配“[abc]”和“{3,5}”
我们知道[abc]，是个字符组。如果要匹配字符串"[abc]"时，该怎么办？
可以写成/[abc]/，也可以写成/[abc]/，测试如下:
只需要在第一个方括号转义即可，因为后面的方括号构不成字符组，正则不会引发歧义，自然不需要转义。
同理，要匹配字符串"{3,5}"，只需要把正则写成/{3,5}/即可。
另外，我们知道量词有简写形式{m,}，却没有{,n}的情况。虽然后者不构成量词的形式，但此时并不会报错。当然，匹配的字符串也是"{,n}"，测试如下：
var str = "{,3}";
var reg = /{,3}/g;
console.log( str.match(reg)[0] );
// = "{,3}"
2.3.3 其余情况
比如= ! : - ,等符号，只要不在特殊结构中，也不需要转义。
但是，括号需要前后都转义的，如/(123)/。
至于剩下的^ $ . * + ? | \ /等字符，只要不在字符组内，都需要转义的。
因为竖杠“|”,的优先级最低，所以正则分成了两部分\d{15}和\d{17}[\dxX]。
\d{15}表示15位连续数字。
\d{17}[\dxX]表示17位连续数字，最后一位可以是数字可以大小写字母"x"。
可视化如下：
3.2 IPV4地址
正则表达式是：
这个正则，看起来非常吓人。但是熟悉优先级后，会立马得出如下的结构：
((...)\.){3}(...)
上面的两个(...)是一样的结构。表示匹配的是3位数字。因此整个结构是
3位数.3位数.3位数.3位数
然后再来分析(...)：
(0{0,2}\d|0?\d{2}|1\d{2}|2[0-4]\d|25[0-5])
它是一个多选结构，分成5个部分：
0{0,2}\d ，匹配一位数，包括0补齐的。比如，9、09、009；
0?\d{2} ，匹配两位数，包括0补齐的，也包括一位数；
1\d{2} ，匹配100到199;
2[0-4]\d ，匹配200-249；
25[0-5] ，匹配250-255。
最后来看一下其可视化形式：
掌握正则表达式中的优先级后，再看任何正则应该都有信心分析下去了。
至于例子，不一而足，没有写太多。
这里稍微总结一下，竖杠的优先级最低，即最后运算。
只要知道这一点，就能读懂大部分正则。
另外关于元字符转义问题，当自己不确定与否时，尽管去转义，总之是不会错的。
本文就解决该问题，内容包括：
2.1 是否能使用正则
正则太强大了，以至于我们随便遇到一个操作字符串问题时，都会下意识地去想，用正则该怎么做。但我们始终要提醒自己，正则虽然强大，但不是万能的，很多看似很简单的事情，还是做不到的。
比如匹配这样的字符串：1010010001....
虽然很有规律，但是只靠正则就是无能为力。
2.2 是否有必要使用正则
要认识到正则的局限，不要去研究根本无法完成的任务。同时，也不能走入另一个极端：无所不用正则。能用字符串API解决的简单问题，就不该正则出马。
比如，从日期中提取出年月日，虽然可以使用正则：
其实，可以使用字符串的split方法来做，即可：
比如，判断是否有问号，虽然可以使用：
其实，可以使用字符串的indexOf方法：
比如获取子串，虽然可以使用正则：
其实，可以直接使用字符串的substring或substr方法来做：
var str = "JavaScript";
console.log( str.substring(4) );
// = Script
2.3 是否有必要构建一个复杂的正则
比如密码匹配问题，要求密码长度6-12位，由数字、小写字符和大写字母组成，但必须至少包括2种字符。
在匹配位置那篇文章里，我们写出了正则是：
其实可以使用多个小正则来做：
所谓准确性，就是能匹配预期的目标，并且不匹配非预期的目标。
这里提到了“预期”二字，那么我们就需要知道目标的组成规则。
不然没法界定什么样的目标字符串是符合预期的，什么样的又不是符合预期的。
下面将举例说明，当目标字符串构成比较复杂时，该如何构建正则，并考虑到哪些平衡。
3.1 匹配固定电话
比如要匹配如下格式的固定电话号码：
055188888888 0551-88888888 (0551)88888888
第一步，了解各部分的模式规则。
上面的电话，总体上分为区号和号码两部分（不考虑分机号和+86的情形）。
区号是0开头的3到4位数字，对应的正则是：0\d{2,3}
号码是非0开头的7到8位数字，对应的正则是：[1-9]\d{6,7}
因此，匹配055188888888的正则是：/^0\d{2,3}[1-9]\d{6,7}$/
匹配0551-88888888的正则是：/^0\d{2,3}-[1-9]\d{6,7}$/
匹配(0551)88888888的正则是：/^(0\d{2,3})[1-9]\d{6,7}$/
第二步，明确形式关系。
这三者情形是或的关系，可以构建分支：
提取公共部分：
进一步简写：
上面的正则构建过程略显罗嗦，但是这样做，能保证正则是准确的。
上述三种情形是或的关系，这一点很重要，不然很容易按字符是否出现的情形把正则写成：
/^(?0\d{2,3})?-?[1-9]\d{6,7}$/
虽然也能匹配上述目标字符串，但也会匹配(0551-88888888这样的字符串。当然，这不是我们想要的。
其实这个正则也不是完美的，因为现实中，并不是每个3位数和4位数都是一个真实的区号。
这就
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束
一般表达
可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。
规律
我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j=i）元组（x1，x2，…，xj）一定也满足d中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反d中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反d中仅涉及到x1，x2，…，xi的一个约束，n≥i≥j。因此，对于约束集d具有完备性的问题p，一旦检测断定某个j元组（x1，x2，…，xj）违反d中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题p的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯法C语言举例
八皇后问题是能用回溯法解决的一个经典问题。
八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上的状态 ：
a[] a[i]=0表示第i行上还没有皇后；
b[] b[i]=0表示第i列反斜线/上没有皇后；
c[] c[i]=0表示第i列正斜线\上没有皇后。
棋盘中同一反斜线/上的方格的行号与列号之和相同；同一正斜线\上的方格的行号与列号之差均相同，这就是判断斜线的依据。
初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第m列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。 #includestdio.h
#includestdlib.h
#define Queens 8
int a[Queens+1]; //八皇后问题的皇后所在每一行位置，从1开始算
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1;//初始
a[1]=1;
printf(the possible configuration of 8 queesns are:\n);
while(not_finish) //not_finsh=1:处理未结束
{
while(not_finish iQueens+1) //处理未结束
{
for(flag=1,k=1;flag ki;k++)//判断是否有多个皇后在同一行
if(a[k]==a[i])
flag=0;
for(k=1;flag ki;k++) //判断是否有多个皇后在对角线
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))
flag=0;
if(!flag) //若存在矛盾 重设第i个元素
{
if(a[i]==a[i-1]) //若a[i]的值已经已经一圈追上a[i-1]的值
{
i--; //退回一步 重新试探处理前一个元素
if(i1 a[i]==Queens)
a[i]=1; // 当a[i]为 Queens时 将a[i]的值重置
else
if(i==1 a[i]==Queens)//当第一未位的值达到Queens时结束
not_finish=0;
else
a[i]++;
}
else
if(a[i]==Queens)
a[i]=1;
else
a[i]++;
}
else
if(++i=Queens) //若前一个元素的值为Queens
if(a[i-1]==Queens)
a[i]=1;
else //否则元素为前一个元素的下一个值
a[i]=a[i-1]+1;
}
if (not_finish)
{
++count;
printf((count-1)%3?[%2d]::\n[%2d]:,count);
for(k=1;k=Queens;k++) //输出结果
printf(%d,a[k]);
if(a[Queens-1]Queens)
a[Queens-1]++;
else
a[Queens-1]=1;
i=Queens-1;
}
}
system(pause);
} var
n,k,t,i:longint;
x:array[1..100] of integer;
function pa(k:integer):boolean;
begin
pa:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false;
end;
procedure try(k:integer);
var
i:integer;
begin
if kn then
begin
t:=t+1;
exit;
end;
for i:=1 to n do
begin
x[k]:=i;
if pa(k) then try(k+1);
end;
end;
begin
read(n);
t:=0;
try(1);
write(t);
end. #include
#include
#define m 5
#define n 6
int sf=0;
int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};
void search(int x,int y)
{
if((x==m-1)(y==n-1))
sf=1;
else
{
mase[x][y]=1;
if((sf!=1)(y!=n-1)mase[x][y+1]==0)
search(x,y+1);
if((sf!=1)(x!=m-1)mase[x+1][y]==0)
search(x+1,y);
if((sf!=1)(y!=0)mase[x][y-1]==0)
search(x,y-1);
if((sf!=1)(x!=0)mase[x-1][y]==0)
search(x-1,y);
}
mase[x][y]=0;
if(sf==1)
mase[x][y]=5;//通过路径用数字的表示
}
int main()
{
int i=0,j=0;
//clrscr();
search(0,0);
for(i=0;im;i++) p=/m;i++)
{
for(j=0;jn;j++) p=/n;j++)
printf(%d,mase[i][j]);
printf(\n);
}
system(pause);
return 0;
}
回溯法解决迷宫问题PASCAL语言
program migong;
var
n,k,j,x,y:integer;
a:array[0..10000,0..10000] of integer;
b:array[0..1000000,0..2] of integer;
procedure search(x,y,i:integer);
begin
a[x,y]:=1;
if (x=n) and (y=n) then
begin
for j:=1 to i-1 do
writeln(j,':(',b[j,1],',',b[j,2],')');
writeln(i,':(',x,',',y,')');
halt;
end;
if a[x-1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x-1,y,i+1);end;
if a[x+1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x+1,y,i+1);end;
if a[x,y-1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y-1,i+1);end;
if a[x,y+1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y+1,i+1);end;
a[x,y]:=0;
end;
begin
read(n);
for k:=1 to n do
for j:=1 to n do
read(a[k,j]);
for k:=0 to n+1 do
begin
a[k,0]:=-1;
a[k,n+1]:=-1;
a[n+1,k]:=-1;
a[0,k]:=-1;
end;
x:=1;y:=1;
if a[x+1,y]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x+1,y,1);a[x,y]:=0;end;
if a[x,y+1]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x,y+1,1);a[x,y]:=0;end;
end.
约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统称为剪枝函数（pruning function）。
使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法(backtracking)
使用剪枝函数的广度优先生成状态空间树中结点的求解方法称为分支/枝限界法(branch-and-bound)
回溯法/分支限界法 = 穷举 + 剪枝。
回溯法是一个既带有系统性又带有跳跃性的搜索算法；
这种以深度优先的方式系统地搜索问题的解得算法称为回溯法。其实回溯法就是对 隐式图 的深度优先搜索算法
回溯是穷举方法的一个改进，它在所有可行的选择中，系统地搜索问题的解。它假定解可以由向量形式 (x1,x2,...,xn) 来 表示，其中xi的值表示在第i次选择所作的决策值，并以深度优先的方式遍历向量空间,逐步确定xi 的值，直到解被找到。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束，来确保解的正确性。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。( 找出解空间树中满足约束条件的所有解 )
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。 这种方法适用于解一些组合数较大的问题 。
（1）问题框架
（2） 递归的算法框架
回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：
（3）非递归回溯框架（递归转非递归，这里可以参考树的遍历，或者看上篇博客——递归算法介绍）
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为 ，则回溯法所需的计算空间通常为 。而显式地存储整个解空间则需要 或 内存空间。
回溯法解题的时候常遇到两种类型的解空间树：
用回溯法搜索子集树的算法框架可描述为：
用回溯法搜索排列树的算法框架可描述为：
回溯法也叫试探法，试探的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。
（1）针对所给问题，定义问题的解空间。
（2）确定易于搜索的解空间结构。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。
下面是回溯的3个要素。
（1）解空间：表示要解决问题的范围，不知道范围的搜索是不可能找到结果的。
（2）约束条件：包括隐性的和显性的，题目中的要求以及题目描述隐含的约束条件，是搜索有解的保证。
（3）状态树：是构造深搜过程的依据，整个搜索以此树展开。
下面是影响算法效率的因素：
回溯法搜索解空间时，通常采用两种策略避免无效搜索，提高回溯的搜索效率:
为缩小规模，我们用显示的国际象棋8*8的八皇后来分析。按照国际象棋的规则，皇后的攻击方式是横，竖和斜向。
皇后可以攻击到同一列所有其它棋子，因此可推导出每1列只能存在1个皇后，即每个皇后分别占据一列。棋盘一共8列，刚好放置8个皇后。
为了摆放出满足条件的8个皇后的布局，可以按如下方式逐步操作：
把规模放大到N行N列也一样，下面用回溯法解决N皇后问题：
执行：
