Backtracking

Backtracking is a technique that explores multiple paths to find the solution. It builds the solution step by step by increasing values with time and removes the choices that don’t contribute to the problem’s solution based on some constraints.

N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

A queen can move horizontally, vertically, diagonally on a chessboard. One queen can be attacked by another queen if both share the same row, column, or diagonal.

Constraints: 1 ≤ n ≤ 9

As stated in the problem statement, we have an n \times nn×n chessboard to place the queens such that no two queens attack each other. Let’s understand the implications of these two conditions:

1. Once we place the first queen anywhere in the first row, no other queen may be placed in that row. Therefore, the search for a safe position for the next queen starts from the next row.
2. As there are nn rows in the given board, and each row may safely hold just one queen, in any valid solution, all nn rows would be used, each holding exactly one queen. This gives us both a condition to check the validity of a solution, as well as a way to check whether a solution is complete.

There are two conditions that cause us to backtrack, but for two different purposes:

1. When we find that we cannot place the current queen in a particular row, we have to backtrack and alter the position of the queen whose position was decided before the current one. Next, we move forward again to find a safe position for the current queen.
2. Once we find a valid solution, we still have to identify all the other valid solutions. So, we backtrack by removing the last queen placed on the board and resuming our search for solutions from that point. In order to be sure to find all possible solutions, we’ll need to backtrack, row by row, all the way back to the first queen placed on the board, changing its position and then looking for alternative solutions.

Step-by-step solution construction

1. Place a queen in the first column of the first row.
2. Now place a queen in the first such column of the second row where placement is permissible. This means that the current queen is not attacked by any queen already on the board.
3. If no such column is found, we’ll backtrack to the previous row and try to place the queen in the next column of that row.
4. We continue this until we reach the last row of the board.
5. When we are able to successfully place the nth queen in the nth row, we’ll have found one valid solution.
6. After we find a solution, we backtrack to the previous row to find the next solution. Next, we try to find another column in the previous row where placement is permissible.

We’ll start by declaring a results array that will store all possible solutions for n queens.

We’ll call a recursive function called helper() to place the queens on the chessboard. We’ll start by placing the queen in the first column of the first row. For every placement, we’ll check if a move is valid. If yes, we’ll add it to our solution.

If we successfully reach the last row of the chessboard, we’ll save that solution in the results array and backtrack to find the alternatives.

const solveNQueens = function (n) {
    let mat = new Array(n).fill('.').map(() => new Array(n).fill('.'));
    let results = [];

    helper(0, mat);
    return results;

    function helper(row, mat) {
        if (row === n) {
            results.push([...mat].map(e => e.join("")));
            return;
        }
        for (let j = 0; j < n; j++) {
            if (check(row, j, mat, n)) {
                mat[row][j] = 'Q';
                helper(row + 1, mat);
                mat[row][j] = '.';
            }
        }
    }
}

We’ll also implement a check() function that checks whether the desired move can place a queen at a safe position. A move is valid if the queen is not vulnerable to attack from other queens on the board.

    function check(i, j, mat, n) {
        // check left and top diagonal
        let x = i - 1;
        let y = j - 1;

        while (x >= 0 && y >= 0) {
            if (mat[x][y] === 'Q') return false;
            x--;
            y--;
        }
        // check right and top diagonal
        x = i - 1;
        y = j + 1;
        while (x >= 0 && y >= 0 && y < n) {
            if (mat[x][y] === 'Q') return false;
            x--;
            y++;
        }
        x = i - 1;
        y = j;
        // check exact top
        while (x >= 0) {
            if (mat[x][y] === 'Q') return false;
            x--;
        }
        return true;
    }

To recap, the solution to this problem can be divided into the following parts:

1. Place a queen in the first column of the first row.
2. Place a queen wherever permissible in the next row.
3. Backtrack if no safe configuration exists.
4. Once a solution is found, backtrack to find other possible configurations.