Flexor teacher about using backtracking to solve the N queens problem on video address: www.bilibili.com/video/BV1Ls… , Qu teacher’s explanation of logical, easy to understand, here no longer gild the lily, mainly focused on the implementation of the code, is also to throw a brick to attract jade.

/** * n queen problem, find and return a feasible solution *@param {number} n number of queens to be placed
 * @returns * /
function queenPlacer(n) {
    const root = new _Node(null, n);
    return solve(root, n);

    function solve(node) {
        if(! node)return;
        // If the path is full, a feasible solution is found
        if (node.path.length >= n)
            return node.path;
        // This marks whether to continue looking for the next node in the child node that has no conflicts
        let continuable = true,
            path = node.path,
            pathLen = path.length,
            children = node.children,
            // Represents the index value of the current row
            curIndex = pathLen;
        // Find the next child node that does not conflict with the path
        // That is, any Pi on the path has a child! = Pi,
        // And not on the diagonal, i.e. the current path value plus or minus the index difference is not equal to the value of the child node
        while (children.length > 0) {
            for (let j = 0; j < pathLen; j++) {
                let diff = curIndex - j;
                // If the value of the current child node conflicts with that of a node on the path, the child is checked
                if (path[j] == children[0] || path[j] - diff == children[0] || path[j] + diff == children[0]) {
                    continuable = false;
                    break; }}// The child has no conflict, end traversal
            if (continuable)
                break;
            // This child has a conflict, remove it from the queue and continue traversing the rest of the children
            else {
                children.shift();
                continuable = true; }}// There is also a child, which means there is no conflict in the head of the child, and the node is searched recursively
        if (children.length > 0) {
            const child = new _Node(node, n);
            return solve(child);
        } 
        // If there are no children, go back to the parent node
        else {
            returnsolve(node.parent); }}function _Node(parent, n) {
        this.parent = parent || null;
        // List a value from the parent node queue as the node for this traversal
        // When backtracking, since this node is already out of the queue, we can continue to traverse other unvisited nodes from the queue head
        this.value = this.parent ? parent.children.shift() : 0;
        // Each node in the n-queen problem is the root of an n-fork complete tree
        this.children = new Array(n).fill(0).map((_, idx) = > idx + 1);
        // The path inherits from the parent node and adds the value of this node to it
        this.path = this.parent ? [...parent.path, this.value] : []; }}Copy the code

Test code:

let result = queenPlacer(8);
    console.log(result.toString());
    for (let i = 0; i < 8; i++) {
        let info = ' ';
        for (let j = 0; j < 8; j++) {
            if (result[i] - 1 == j) {
                info += '| +';
            } else {
                info += '|';
            }
        }
        info += '|';
        console.log(info);
    }
Copy the code

Terminal display result:

1,5,8,6,3,7,2,4 + | | | | | | | | | | | | | | + | | | | | | | | | | | | + | | | | | | | + | | | | | | + | | | | | | | | | | | | |+| | | |+| | | | | | | | | | |+| | | | |Copy the code