function ambRun(func) { var choices = []; var index; function amb(values) { if (values.length == 0) { fail(); } if (index == choices.length) { choices.push({i: 0, count: values.length}); } var choice = choices[index++]; return values[choice.i]; } function fail() { throw fail; } while (true) { try { index = 0; return func(amb, fail); } catch (e) { if (e != fail) { throw e; } var choice; while ((choice = choices.pop()) && ++choice.i == choice.count) {} if (choice == undefined) { return undefined; } choices.push(choice); } } }
以及使用 amb 实现的八皇后问题的具体代码
ambRun(function(amb, fail){ var N = 4; var arr = []; var turn = []; for(var n = 0; n < N; n++) { turn[turn.length] = n + 1; } while(n--) { arr[arr.length] = amb(turn); } for (var i = 0; i < N; ++i) { for (var j = i + 1; j < N; ++j) { var a = arr[i], b = arr[j]; if (a == b || Math.abs(a - b) == j - i) fail(); } } console.log(arr); fail(); });
八皇后问题的JavaScript解法
这是八皇后问题的JavaScript解法，整个程序都没用for循环，都是靠递归来实现的，充分运用了Array对象的map, reduce, filter, concat, slice方法
'use strict'; var queens = function (boarderSize) { // 用递归生成一个start到end的Array var interval = function (start, end) { if (start > end) { return []; } return interval(start, end - 1).concat(end); }; // 检查一个组合是否有效 var isValid = function (queenCol) { // 检查两个位置是否有冲突 var isSafe = function (pointA, pointB) { var slope = (pointA.row - pointB.row) / (pointA.col - pointB.col); if ((0 === slope) || (1 === slope) || (-1 === slope)) { return false; } return true; }; var len = queenCol.length; var pointToCompare = { row: queenCol[len - 1], col: len }; // 先slice出除了最后一列的数组，然后依次测试每列的点和待测点是否有冲突，最后合并测试结果 return queenCol .slice(0, len - 1) .map(function (row, index) { return isSafe({row: row, col: index + 1}, pointToCompare); }) .reduce(function (a, b) { return a && b; }); }; // 递归地去一列一列生成符合规则的组合 var queenCols = function (size) { if (1 === size) { return interval(1, boarderSize).map(function (i) { return [i]; }); } // 先把之前所有符合规则的列组成的集合再扩展一列，然后用reduce降维，最后用isValid过滤掉不符合规则的组合 return queenCols(size - 1) .map(function (queenCol) { return interval(1, boarderSize).map(function (row) { return queenCol.concat(row); }); }) .reduce(function (a, b) { return a.concat(b); }) .filter(isValid); }; // queens函数入口 return queenCols(boarderSize); }; console.log(queens(8)); // 输出结果: // [ [ 1, 5, 8, 6, 3, 7, 2, 4 ], // [ 1, 6, 8, 3, 7, 4, 2, 5 ], // ... // [ 8, 3, 1, 6, 2, 5, 7, 4 ], // [ 8, 4, 1, 3, 6, 2, 7, 5 ] ]
PS：延伸的N皇后问题
当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题（eight queens puzzle）时，他恐怕怎么也想不到，100 多年以后，这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单：把八个皇后放在国际象棋棋盘上，使得这八个皇后互相之间不攻击（国际象棋棋盘是一个 8×8 的方阵，皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步）。虽然这个问题一共有 92 个解，但要想徒手找出一个解来也并不容易。下图就是其中一个解：
八皇后问题有很多变种，不过再怎么也不会比下面这个变种版本更帅：请你设计一种方案，在一个无穷大的棋盘的每一行每一列里都放置一个皇后，使得所有皇后互相之间都不攻击。具体地说，假设这个棋盘的左下角在原点处，从下到上有无穷多行，从左到右有无穷多列，你需要找出一个全体正整数的排列方式 a1, a2, a3, … ，使得当你把第一个皇后放在第一行的第 a1 列，把第二个皇后放在第二行的第 a2 列，等等，那么任意两个皇后之间都不会互相攻击。
下面给出一个非常简单巧妙的构造。首先，我们给出五皇后问题的一个解。并且非常重要的是，其中一个皇后占据了最左下角的那个格子。
接下来，我们把五皇后的解扩展到 25 皇后，而依据则是五皇后本身的布局：
