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) {
We'll now take you through what you need to know.
How do I use this guide?