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):

SNIPPET

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 our guided, illustrated walk-through.

How do I use this guide?