N-Queens hard

Problem Statement

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

A queen attacks any piece in the same row, column, or diagonal.

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 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"]]

Steps

1. Backtracking: We'll use a backtracking algorithm to explore all possible placements of queens.
2. Board Representation: We'll represent the chessboard using a list of strings (or a 2D array).
3. IsSafe Function: A crucial function to check if it's safe to place a queen at a given row and column. This involves checking the row, column, and both diagonals.
4. Recursive Function: A recursive function will explore placing queens row by row. If a placement is safe, it recursively calls itself for the next row. If a solution is found (all queens placed), it's added to the result. If no safe placement is found in a row, it backtracks.

Explanation

The backtracking algorithm systematically explores all possible queen placements. The IsSafe function efficiently determines if a placement is valid by checking for conflicts in the row, column, and diagonals. The recursion ensures that all possible combinations are explored. When a complete solution is found, it's added to the result list. If a queen placement leads to a conflict, the algorithm backtracks to try alternative placements.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        IList<IList<string>> result = new List<IList<string>>();
        List<string> board = new List<string>();
        for (int i = 0; i < n; i++) {
            board.Add(new string('.', n));
        }
        SolveNQueensHelper(result, board, 0);
        return result;
    }

    private void SolveNQueensHelper(IList<IList<string>> result, List<string> board, int row) {
        int n = board.Count;
        if (row == n) {
            result.Add(new List<string>(board)); //Add a copy to avoid modification
            return;
        }

        for (int col = 0; col < n; col++) {
            if (IsSafe(board, row, col)) {
                board[row] = board[row].Substring(0, col) + 'Q' + board[row].Substring(col + 1);
                SolveNQueensHelper(result, board, row + 1);
                board[row] = board[row].Substring(0, col) + '.' + board[row].Substring(col + 1); //Backtrack
            }
        }
    }

    private bool IsSafe(List<string> board, int row, int col) {
        int n = board.Count;

        // Check column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }

        // Check diagonals
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
}

Complexity

• Time Complexity: O(N!), where N is the size of the board. In the worst case, we explore all possible permutations of queen placements.
• Space Complexity: O(N^2) to store the board and the recursion stack. The space used by the recursion stack is proportional to N in the average case but can be O(N^2) in the worst case if the algorithm goes very deep.