N-Queens

LeetCode 51 | Difficulty: Hard

Hard

Problem Description

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.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

- `1 <= n <= 9`

Topics: Array, Backtracking

---

Approach

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

---

Solutions

Solution 1: C# (Best: 348 ms)

Metric	Value
Runtime	348 ms
Memory	N/A
Date	2018-02-27

Solution

public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
       List<IList<string>> res = new List<IList<string>>();
    var nQueens = new List<char[]>();
    for (int i = 0; i < n; i++)
    {
        char[] row = new char[n];
        for (int j = 0; j < n; j++)
        {
            row[j] = '.';
        }
        nQueens.Add(row);
    }
    SolveNQueensUtil(ref res,  nQueens, 0, n);

    return res;
}

public void SolveNQueensUtil(ref List<IList<string>> res, List<char[]> nQueens, int row, int n)
{
    if(row == n)
    {
        res.Add(nQueens.Select(c => new string(c)).ToList());
    }
    
    for (int col = 0; col != n; col++)
    {
        if(isvalid(nQueens, row, col, n))
        {
            nQueens[row][col] = 'Q';
            SolveNQueensUtil(ref res, nQueens, row+1, n);
            nQueens[row][col] = '.';
        }
    }
}

bool isvalid(List<char[]> nQueens, int row, int col, int n)
{
    for (int i = 0; i != row; i++)
    {
        if(nQueens[i][col]=='Q')
        return false;
    }
    for (int i = row-1,j=col-1; i>=0 && j>=0; i--,j--)
    {
        if (nQueens[i][j] == 'Q')
            return false;
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
    {
        if (nQueens[i][j] == 'Q')
            return false;
    }
    
    return true;
}
}

---

Complexity Analysis

Approach	Time	Space
Backtracking	$O(n! or 2^n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Identify pruning conditions early to avoid exploring invalid branches.