关于八皇后问题的 JavaScript 解法，总觉得是需要学习一下算法的，哪天要用到的时候发现真不会就尴尬了
背景
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上
八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为 n×n ，而皇后个数也变成n 。当且仅当n = 1或n ≥ 4时问题有解
盲目的枚举算法
通过N重循环，枚举满足约束条件的解（八重循环代码好多，这里进行四重循环），找到四个皇后的所有可能位置，然后再整个棋盘里判断这四个皇后是否会直接吃掉彼此，程序思想比较简单
function check1(arr, n) { for(var i = 0; i < n; i++) { for(var j = i + 1; j < n; j++) { if((arr[i] == arr[j]) || Math.abs(arr[i] - arr[j]) == j - i) { return false; } } } return true; } function queen1() { var arr = []; for(arr[0] = 1; arr[0] <= 4; arr[0]++) { for(arr[1] = 1; arr[1] <= 4; arr[1]++) { for(arr[2] = 1; arr[2] <= 4; arr[2]++) { for(arr[3] = 1; arr[3] <= 4; arr[3]++) { if(!check1(arr, 4)) { continue; } else { console.log(arr); } } } } } } queen1(); //[ 2, 4, 1, 3 ] //[ 3, 1, 4, 2 ]
关于结果，在 4*4 的棋盘里，四个皇后都不可能是在一排， arr[0] 到 arr[3] 分别对应四个皇后，数组的下标与下标对应的值即皇后在棋盘中的位置
回溯法
『走不通，就回头』，在适当节点判断是否符合，不符合就不再进行这条支路上的探索
function check2(arr, n) { for(var i = 0; i <= n - 1; i++) { if((Math.abs(arr[i] - arr[n]) == n - i) || (arr[i] == arr[n])) { return false; } } return true; } function queen2() { var arr = []; for(arr[0] = 1; arr[0] <= 4; arr[0]++) { for(arr[1] = 1; arr[1] <= 4; arr[1]++) { if(!check2(arr, 1)) continue; //摆两个皇后产生冲突的情况 for(arr[2] = 1; arr[2] <= 4; arr[2]++) { if(!check2(arr, 2)) continue; //摆三个皇后产生冲突的情况 for(arr[3] = 1; arr[3] <= 4; arr[3]++) { if(!check2(arr, 3)) { continue; } else { console.log(arr); } } } } } } queen2(); //[ 2, 4, 1, 3 ] //[ 3, 1, 4, 2 ]
非递归回溯法
算法框架：
while(k > 0 『有路可走』 and 『未达到目标』) { // k > 0 有路可走 if(k > n) { // 搜索到叶子节点 // 搜索到一个解，输出 } else { //a[k]第一个可能的值 while(『a[k]在不满足约束条件且在搜索空间内』) { // a[k]下一个可能的值 } if(『a[k]在搜索空间内』) { // 标示占用的资源 // k = k + 1; } else { // 清理所占的状态空间 // k = k - 1; } } }
具体代码如下，最外层while下面包含两部分，一部分是对当前皇后可能值的遍历，另一部分是决定是进入下一层还是回溯上一层
function backdate(n) { var arr = []; var k = 1; // 第n的皇后 arr[0] = 1; while(k > 0) { arr[k-1] = arr[k-1] + 1; while((arr[k-1] <= n) && (!check2(arr, k-1))) { arr[k-1] = arr[k-1] + 1; } // 这个皇后满足了约束条件，进行下一步判断 if(arr[k-1] <= n) { if(k == n) { // 第n个皇后 console.log(arr); } else { k = k + 1; // 下一个皇后 arr[k-1] = 0; } } else { k = k - 1; // 回溯，上一个皇后 } } } backdate(4); //[ 2, 4, 1, 3 ] //[ 3, 1, 4, 2 ]
递归回溯法
递归调用大大减少了代码量，也增加了程序的可读性
var arr = [], n = 4; function backtrack(k) { if(k > n) { console.log(arr); } else { for(var i = 1;i <= n; i++) { arr[k-1] = i; if(check2(arr, k-1)) { backtrack(k + 1); } } } } backtrack(1); //[ 2, 4, 1, 3 ] //[ 3, 1, 4, 2 ]
华而不实的amb
什么是 amb ？给它一个数据列表，它能返回满足约束条件的成功情况的一种方式，没有成功情况就会失败，当然，它可以返回所有的成功情况。笔者写了上面那么多的重点，就是为了在这里推荐这个amb算法，它适合处理简单的回溯场景，很有趣，让我们来看看它是怎么工作的
首先来处理一个小问题，寻找相邻字符串：拿到几组字符串数组，每个数组拿出一个字符串，前一个字符串的末位字符与后一个字符串的首位字符相同，满足条件则输出这组新取出来的字符串
ambRun(function(amb, fail) { // 约束条件方法 function linked(s1, s2) { return s1.slice(-1) == s2.slice(0, 1); } // 注入数据列表 var w1 = amb(["the", "that", "a"]); var w2 = amb(["frog", "elephant", "thing"]); var w3 = amb(["walked", "treaded", "grows"]); var w4 = amb(["slowly", "quickly"]); // 执行程序 if (!(linked(w1, w2) && linked(w2, w3) && linked(w3, w4))) fail(); console.log([w1, w2, w3, w4].join(' ')); // "that thing grows slowly" });
看起来超级简洁有没有！不过使用的前提是，你不在乎性能，它真的是很浪费时间！
下面是它的 javascript 实现，有兴趣可以研究研究它是怎么把回溯抽出来的