Good morning! Here's our prompt for today.

N-Queen Problem: The Chessboard Conundrum

Imagine stepping into an interview room, and the interviewer asks you to solve the N-Queen problem. It's a modern take on the classic 8-Queen Puzzle, where you place queens on a chessboard in such a way that none can attack another. Here's a complete guide to understanding the problem and constraints.

The Basic Rules of Chessboard and Queens

First, let's get our chess terminology straight. A queen in chess can move horizontally, vertically, and diagonally. Your task is to place n queens on an n x n chessboard in such a way that none of the queens are in a position to attack each other.

Key Assumptions

• Square Board: The chessboard will always be square-shaped.
• Solution Exists: For n > 3, at least one non-attacking arrangement of queens exists.

Constraints to Keep in Mind

Board Size Limitations

• Maximum value of n: The board can have up to 100 rows and columns.
• Minimum value of n: The board must have at least 4 rows and columns.

Performance Expectations

• Time Complexity: Your solution should aim to have a time complexity of O(n^2).
• Space Complexity: Keep the space complexity at O(n).

Example: Solving a 4x4 Board

For a 4x4 chessboard, you could place the queens like so (Q represents a queen, and . represents an empty space):

1. Q . .
2. . . Q
3Q . . .
4. . Q .

Here, no two queens threaten each other. And voila, you've successfully solved the 4-queen problem.

Grasp these guidelines well, and you'll be several moves ahead in your coding interview.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

var assert = require('assert');

​

function solveNQueens(n) {

  // Fill in

}

​

// test cases

​

try {

  res = solveNQueens(4);

  shouldbe = [

    [

      ['.', 'Q', '.', '.'],

      ['.', '.', '.', 'Q'],

      ['Q', '.', '.', '.'],

      ['.', '.', 'Q', '.'],

    ],

    [

      ['.', '.', 'Q', '.'],

      ['Q', '.', '.', '.'],

      ['.', '.', '.', 'Q'],

      ['.', 'Q', '.', '.'],

    ],

  ];

​

  assert.deepEqual(shouldbe, res);

​

  console.log('PASSED: ' + 'With n=4, there should be 2 solution boards.');

} catch (err) {

Here's how we would solve this problem...

How do I use this guide?

Board Validation Function

Before we implement the solver itself, we need to create a function that can be used to see if we can put a queen on a cell in the board. The function will take the board, a row, and a col to place into that cell of the board.

1function validateBoard(board, row, col) {
2}

The function will first check if there is a Queen in the same column in the board. We can check this easily by looping through the rows one at a time. Notice that we do not need to check for queens after the current row because we have not reached that point yet. Here is the python code for this validation:

1// Check if row is valid
2for(let row_it = 0; row_it < row; row_it++){
3    if(board[row_it][col] == 'Q'){
4        return false;
5    }
6}

We do not need to check for Queens in the same column because in the backtracking process, we will put only one Queen at each column.

Following this, we will check if a Queen appears in the first diagonal of the board. To do this, we will need to see how the row_it and the col_it variables in a loop increases or decreases. See the below image to understand it. The first one is for the first diagonal and the second one is for the second diagonal.

xxxxxxxxxx

// Check if block has duplicate

let rowBlock = row - row % 3;

let colBlock = col - col % 3;

for (let rowIt = 0; rowIt < 3; rowIt++) {

    for (let colIt = 0; colIt < 3; colIt++) {

        if (board[rowBlock + rowIt][colBlock + colIt] === val) {

            return false;

        }

    }

}

​

// Check if second diagonal is valid

for (let rowIt = row - 1, colIt = col + 1; rowIt >= 0 && colIt < board.length; rowIt--, colIt++) {

    if (board[rowIt][colIt] === 'Q') {

        return false;

    }

}

Finally if none of these return False, we are sure that a Queen at that row and col position is a valid state. So we will return true.

xxxxxxxxxx

// Everything is valid, so return true

return true;

Base Conditions of Recursing Backtracking

We will start from the first element in the board. We will be putting Queens in places and then move forward. To do this, we will continuously place Queens if possible, and then increment row.

While incrementing row, we will reach at a point where row will be greater than n (out of the board). At that time, we have found a solution. So we will save a copy of the board and continue to backtrack for other solutions.

xxxxxxxxxx

if (row === board.length) {

    // A solution! add a copy of it

    res.push([...board]);

    return res;

}

Recursive Backtracking

For the backtracking, we will take each row and put a Queen in a feasible place (with the help of validate_board) in that row. After placing the Queen, we will recursively continue from the next row in the board.

After finishing that recursive function, we will have all the solved boards, putting a Queen at that row and col. We'll need the next step of putting current Queen in the next feasible place. That is why we will pick up the Queen (put '.' there) and continue the loop.

Finally there will be all the solutions in res. Also, we will again be at the top of the call stack in the recursive function. So we will return our desired res to the caller function.

xxxxxxxxxx

for(let col = 0; col < board.length; col++) {

    if(this.validate_board(board, row, col)) {

        // Put a queen and move forward

        board[row] = board[row].substr(0, col) + "Q" + board[row].substr(col+1);

        this.recursiveSolveNQueens(res, board, row+1);

        // Now backtrack

        board[row] = board[row].substr(0, col) + "." + board[row].substr(col+1);

    }

}

Start of the Backtracking Algorithm

We will start the backtracking process from row=0 and col=0. col=0 part is already taken cared by the backtracking function itself. We just need to create a board so that our recursiveSolveNQueens can start playing with the board.

To create a board, we will first create a string of size n with the python string multiplication operator '.' * n. Then we will again duplicate it n times to get the board.

xxxxxxxxxx

const solveNQueens = (n) => {

    // For n=5, board in Javascript is

    // [".....", => '.'*n

    //  ".....", => '.'*n

    //  ".....", => '.'*n

    //  ".....", => '.'*n

    //  "....."] => '.'*n

    // so, [...Array(n)].map(_ => '.'.repeat(n))

    let board = [...Array(n)].map(_ => '.'.repeat(n));

    // Type will be replaced by actual type later

};

Finally we will start the recursion with the board and an empty res result list. res will be the answer of our problem, so we can directly return it.

This is the most well-known algorithm for solving N-Queen problem. The time complexity is O(n^2) because we are selecting if we can put or not put a Queen at that place. The space is the board size times the result. Note that, even though it seems that the time complexity is huge, it is actually not. The maximum value of n will be only 100.