VOOZH about

URL: https://dev.to/jaspreet_singh_86ae1740ac/n-queens-backtracking-17m3

⇱ N Queens | Backtracking - DEV Community

Problem Statement

Place N queens on an N x N chessboard such that:

  • No two queens attack each other.
  • Queens cannot share:
    • Row
    • Column
    • Diagonal

Return all possible valid board configurations.

Brute Force Intuition

Try placing queens in every possible cell.

After placing all queens, check whether the board is valid.

Most configurations are invalid, making brute force extremely expensive.

Complexity

  • Time Complexity: O(N^N)
  • Space Complexity: O(N²)

Moving Towards the Optimal Approach

Instead of placing queens randomly:

Place one queen per column.

For each column:

Try every row.

Before placing a queen:

Check if the position is safe.

If safe:

Place Queen
Recurse
Backtrack

Pattern Recognition

Whenever you see:

  • Generate all valid arrangements
  • Constraints while placing elements
  • Chessboard problems

Think:

Backtracking + Constraint Checking

Key Observation

For each column:

Try all rows

If current cell is safe:

Place Queen

Otherwise:

Skip

Optimal Java Solution 

class Solution {

 public List<List<String>> solveNQueens(int n) {

 List<List<String>> ans = new ArrayList<>();

 char[][] board = new char[n][n];

 for (char[] row : board) {
 Arrays.fill(row, '.');
 }

 solve(0, board, ans);

 return ans;
 }

 private void solve(int col,
 char[][] board,
 List<List<String>> ans) {

 if (col == board.length) {

 List<String> temp = new ArrayList<>();

 for (char[] row : board) {
 temp.add(new String(row));
 }

 ans.add(temp);
 return;
 }

 for (int row = 0; row < board.length; row++) {

 if (isSafe(row, col, board)) {

 board[row][col] = 'Q';

 solve(col + 1, board, ans);

 board[row][col] = '.';
 }
 }
 }

 private boolean isSafe(int row,
 int col,
 char[][] board) {

 int r = row;
 int c = col;

 while (c >= 0) {
 if (board[r][c] == 'Q')
 return false;
 c--;
 }

 r = row;
 c = col;

 while (r >= 0 && c >= 0) {
 if (board[r][c] == 'Q')
 return false;
 r--;
 c--;
 }

 r = row;
 c = col;

 while (r < board.length && c >= 0) {
 if (board[r][c] == 'Q')
 return false;
 r++;
 c--;
 }

 return true;
 }
}

Dry Run 

n = 4

Column 0 → Place Queen

Q . . .
. . . .
. . . .
. . . .

Column 1 → Try safe rows

Continue until:

. . Q .
Q . . .
. . . Q
. Q . .

Valid Solution

Complexity Analysis

Metric Complexity
Time Complexity O(N!)
Space Complexity O(N²)

Interview One-Liner

Place one queen column by column, checking whether the current position is safe. Backtrack whenever a conflict occurs.

Memory Trick 

Column Wise Placement

Try Row
↓
Safe?
↓
Place Queen
↓
Recurse
↓
Backtrack