Regarding the JavaScript solution to the Eight Queens problem, I always feel that I need to learn the algorithm. It will be embarrassing to find out if I use it one day.
background
The Eight Queens question is a question based on chess: how can eight queens be placed on the 8×8 chess board so that no queen can eat the other queens directly? To achieve this, neither queen can be in the same horizontal, vertical or diagonal line
The Eight Queens problem can be generalized to the more general problem of n queen placement: at this time the size of the chessboard becomes n×n, and the number of queens also becomes n. If and only if n = 1 or n ≥ 4 there is a solution to the problem
Blind enumeration algorithm
Through N-fold loops, enumerate solutions that meet the constraints (there are many eight-fold loop codes, four-fold loops are performed here), find all possible positions of the four queens, and then judge in the entire board whether these four queens will eat each other directly. The program idea is relatively simple.
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); } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }Regarding the result, in the 4*4 chessboard, the four queens cannot be in a row. arr[0] to arr[3] correspond to the four queens respectively. The value corresponding to the subscript of the array and the subscript is the position of the queen in the board.
Backtracking method
"If you can't go, just turn around." Determine whether it matches it at the appropriate node. If it doesn't match, you will no longer explore this branch.
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; //State the conflict between two queens for(arr[2] = 1; arr[2] <= 4; arr[2]++) { if(!check2(arr, 2)) continue; //State the conflict between three queens for(arr[3] = 1; arr[3] <= 4; arr[3]++) { if(!check2(arr, 3)) { continue; } else { console.log(arr); } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }Non-recursive backtracking
Algorithm framework:
while(k > 0 『There is a way to go』 and 『Not reached the goal』) { // k > 0 『There is a way to go if(k > n) { // Search for leaf nodes// Search for a solution, output} else { // a[k]The first possible value while("a[k] is in the search space") { // a[k]The next possible value} if("a[k] is in the search space") { // Mark the resource occupied// k = k + 1; } else { // Clean up the occupied state space// k = k - 1; } }}The specific code is as follows. The outermost layer while contains two parts. One is a traversal of the current queen's possible values, and the other is a decision whether to enter the next layer or backtrack the previous layer.
function backdate(n) { var arr = []; var k = 1; // The nth queen 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; } // This queen satisfies the constraints and makes the next judgment if(arr[k-1] <= n) { if(k == n) { // The nth queen console.log(arr); } else { k = k + 1; // The next queen arr[k-1] = 0; } } else { k = k - 1; // Backtrack, last queen} }}backdate(4);//[ 2, 4, 1, 3 ]//[ 3, 1, 4, 2 ]Recursive backtracking method
Recursive calls greatly reduce the amount of code and increase the readability of the program.
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 ]Gorgeous amb
What is amb? Give it a data list, which can return a way to meet the constraints' success situations. Without success, it will fail. Of course, it can return all success situations. The author has written so many points above, just to recommend this amb algorithm here. It is suitable for handling simple backtracking scenarios. It is very interesting. Let's see how it works.
First, let’s deal with a small problem, find adjacent strings: get several sets of string arrays, and each array takes out a string. The last character of the previous string is the same as the first character of the next string. If the conditions are met, the newly retrieved strings will be output.
ambRun(function(amb, fail) { // Constraint method function linked(s1, s2) { return s1.slice(-1) == s2.slice(0, 1); } // Inject data list var w1 = amb(["the", "that", "a"]); var w2 = amb(["frog", "elephant", "thing"]); var w3 = amb(["walked", "treaded", "grows"]); var w4 = amb(["slowly", "quickly"]); // Execute the program if (!(linked(w1, w2) && linked(w2, w3) && linked(w3, w4))) fail(); console.log([w1, w2, w3, w4].join(' ')); // "that thing grows slowly"});It looks super simple or not! However, the premise of using is that you don’t care about performance, it is really a waste of time!
Below is its JavaScript implementation. If you are interested, you can study how it extracts backtracking.
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); } }}And the specific code of the Eight Queens problem implemented using 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 solution to the Eight Queens Problem
This is the JavaScript solution to the Eight Queens problem. The entire program does not use for loops, and is implemented through recursion. It fully utilizes the map, reduce, filter, concat, slice methods of the Array object.
'use strict';var queens = function (boarderSize) { // Use recursion to generate an Array var interval from start to end = function (start, end) { if (start > end) { return []; } return interval(start, end - 1).concat(end); }; // Check whether a combination is valid var isValid = function (queenCol) { // Check whether there is conflict between two positions 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 }; // First slice out the array except the last column, then test whether there is a conflict between the points in each column and the points to be tested, and finally merge the test results. 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; }); }; // Recursively generate combinations that conform to the rules var queenCols = function (size) { if (1 === size) { return interval(1, boarderSize).map(function (i) { return [i]; }); } // First expand the set of all previous columns that conform to the rules, then use reduce dimensionality reduction, and finally use isValid to filter out combinations that conform to the rules 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 function entry return queenCols(boarderSize);};console.log(queens(8));// Output result:// [ [ 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: Extended N Queen Problem
When chess player Max Bezzel asked the eight queens puzzle in 1848, he probably never thought that more than 100 years later, this problem became one of the most important compulsory courses in programming learning. The Eight Queens problem sounds very simple: put the eight queens on the chess board so that the eight queens do not attack each other (the chess board is an 8×8 square array, and the queen can take any multiple steps in any of the eight directions horizontally and vertically). Although there are 92 solutions to this problem, it is not easy to find one solution with bare hands. The following figure is one of the solutions:
There are many variants of the Eight Queens problem, but no matter how hard it is, it will not be more handsome than the following variant: Please design a plan to place a queen in every row and every column of an infinite chessboard, so that all queens do not attack each other. Specifically, suppose the lower left corner of this board is at the origin, with infinite rows from bottom to top and infinite columns from left to right, you need to find out the arrangement of all positive integers a1, a2, a3, … so that when you place the first queen in the first row in column a1, the second queen in column a2, etc., then no two queens will attack each other.
Here is a very simple and clever construction. First, we give an answer to the Five Queens problem. And very importantly, one of the queens occupies the grid in the bottom left corner.
Next, we expand the solution of the Five Queens to the 25 Queens, and based on the layout of the Five Queens itself:
As a result, the five queens in the same group obviously will not attack each other, and the queens in different groups will obviously not attack each other. This is a 25 queen solution that meets the requirements. Note that after the expansion, the previously filled-in section has not changed.
What should I do next? That's right, we copied the 25 Queen's unblocking into five pieces, and arranged it again according to the layout of the five Queens, thus expanding to 125 Queens!
By constantly expanding outwards based on the filled parts like this, you can generate a solution to the infinite queen problem.