N-Queens

A few days back, I came across the famous problem, N-Queens. Here’s my approach to solving the problem.

Problem Statement

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.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Sample test case, where n=4

Decoding the given problem

We’re given a value n, meaning we need to place n queens on an n x n board.

While doing this, we must ensure that each queen is safe from the others, following the moves a queen can make in a game of chess.

♟️ A Queen can move:

• Horizontally
• Vertically
• Diagonally (both directions)

Keeping these in mind, we can simplify our task. Since a queen can attack any other queen in the same row, we must place only one queen per row. So the challenge becomes placing exactly one queen in each row such that no two queens share the same column or diagonal.

Dry Run with Sample Input (n = 4)

We begin with n = 4. That means we must place 4 queens on a 4 x 4 board.

We start with the first row and try placing Queen Q1 in the first column.
Now we move to the second row and try placing Queen Q2.

• Column 1 is invalid: Q1 is already in column 1.
• Column 2 is diagonally under attack from Q1.
• Column 3 looks good. We place Q2 at row 2, column 3.

Now onto row 3 (Q3):

• Column 1: attacked vertically by Q1.
• Column 2: diagonally attacked by Q2.
• Column 3: attacked vertically by Q2.
• Column 4: also under diagonal threat.

Q3 can’t be placed anywhere safely → we backtrack.

Get Eshita Chokhani’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

We move Q2 to column 4 (instead of 3).

Try placing Q3 again in row 3:

• Column 2 seems safe now. Place Q3 there.

Finally, we attempt to place Q4 in row 4:

• Column 1: attacked vertically.
• Column 2: occupied by Q3.
• Column 3: under diagonal attack.
• Column 4: attacked vertically by Q2.

Again, no safe spot → more backtracking.
We continue this approach, trying new positions for Q1, Q2, etc., exploring all valid configurations.

This process continues until all valid board setups are explored.

Code

n-Queens function

Let’s understand this line by line:

nQueens is our recursive function that takes the current board, current row, total number of rows, and the final answer vector.

If row == n, it means all queens are placed correctly, and we push this configuration to our answer vector. This is our base case.

We then loop through each column in the current row and check if it’s safe to place a queen there using the isSafe function.

If it’s safe, we place the queen, make the recursive call for the next row, and finally backtrack by removing the queen (replacing it with ‘.’).

isSafe function.

isSafe function

Let’s break it down:

• Column Check: We loop through all rows above the current row and check if there’s a queen in the same column. If yes, it’s not safe.
• Top-Left Diagonal Check: We move diagonally up-left from the current cell. If a queen is found, it’s not safe.
• Top-Right Diagonal Check: We move diagonally up-right. Same idea — if we hit a queen, the cell is unsafe.

We don’t need to check the row, because by design, we place only one queen per row. This optimization helps reduce the time complexity.

Conclusion

The N-Queens problem is honestly one of those classic problems that really makes one think. It’s not just about placing queens, it’s about understanding how to navigate through a huge number of possibilities efficiently. The use of recursion and backtracking here isn’t just for the sake of it, but it actually teaches you how to eliminate invalid states early and only go deeper when it’s actually safe. You get to work with constraint checking and see how depth-first search works behind the scenes. All in all, it’s a really fun yet challenging problem that sharpens your logic building.