NUHMAN.com

Introduction

The N-Queens problem is one of the most classic and fundamental problems in computer science. It tests your ability to implement backtracking algorithms and manage constraints systematically.

LeetCode 51 asks you to return all distinct solutions to the N-Queens puzzle. It’s a recursive problem that requires placing n queens on an n x n chessboard such that no two queens attack each other.

Problem Statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens threaten each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

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

Example:

go

Input: n = 4
Output: [
 [".Q..",
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",
  "Q...",
  "...Q",
  ".Q.."]
]

Explanation: There are 2 distinct solutions to the 4-queens puzzle.

Constraints

• 1 <= n <= 9

Approach: Backtracking with Pruning

We will use backtracking to try placing queens row by row.

Valid Position Rules:

• No other queen should be in the same column
• No other queen should be in the same left diagonal (row - col)
• No other queen should be in the same right diagonal (row + col)

Steps:

1. Start from row 0.
2. Try placing a queen in each column of the current row.
3. If placing a queen is safe:

• Place it
• Move to the next row

1. If all n rows are filled, record the board.
2. Backtrack by removing the queen and trying the next column.

Go Implementation

go

func solveNQueens(n int) [][]string {
    var results [][]string
    board := make([][]byte, n)
    for i := range board {
        board[i] = make([]byte, n)
        for j := range board[i] {
            board[i][j] = '.'
        }
    }

    cols := make(map[int]bool)
    posDiags := make(map[int]bool) // row + col
    negDiags := make(map[int]bool) // row - col

    var backtrack func(row int)
    backtrack = func(row int) {
        if row == n {
            var temp []string
            for _, r := range board {
                temp = append(temp, string(r))
            }
            results = append(results, temp)
            return
        }

        for col := 0; col < n; col++ {
            if cols[col] || posDiags[row+col] || negDiags[row-col] {
                continue
            }

            // Place queen
            board[row][col] = 'Q'
            cols[col], posDiags[row+col], negDiags[row-col] = true, true, true

            backtrack(row + 1)

            // Remove queen (backtrack)
            board[row][col] = '.'
            cols[col], posDiags[row+col], negDiags[row-col] = false, false, false
        }
    }

    backtrack(0)
    return results
}

Example Walkthrough

For n = 4:

• Try placing queen at (0,0), (0,1), (0,2), (0,3)
• Recursively explore valid positions row by row
• Backtrack when no valid column is available in a row
• Once a complete board is filled, record it

Time and Space Complexity

MetricComplexityTime ComplexityO(n!)Space ComplexityO(n²) for board + O(n) for recursion stack

• Time is factorial because of the branching factor reducing at each level.
• Space: board is n x n; the recursion stack can go as deep as n.

Edge Cases

• n = 1: Single queen, return [["Q"]]
• n = 2 or n = 3: No valid configuration, return []

Key Takeaways

• The N-Queens problem demonstrates elegant use of recursive backtracking.
• Efficient constraint pruning (columns and diagonals) makes it fast even for n = 9.
• It's a great example of solving combinatorial problems using depth-first search strategies.