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 can attack 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. State Representation: We'll use a vector of integers col where col[i] represents the column index of the queen placed in row i. We'll also use helper functions to check if a placement is valid.
3. Validation: Before placing a queen, we need to check if it's safe to place it in the current row and column. This involves checking the same column, diagonals (positive and negative slopes).
4. Base Case: When we have placed n queens successfully, we have found a solution. We'll store the solution in a string vector and then add it to the result.
5. Exploration: We'll recursively explore all possible column placements for the next row. If a placement is valid, we'll place the queen, recursively explore further, and then backtrack (remove the queen) to explore other possibilities.

Explanation

The backtracking algorithm systematically explores all possible queen placements. The key is the isSafe function, which efficiently checks for conflicts. By using a vector col to store column positions, we avoid redundant checks. The algorithm explores every possible column for each row, and only if the placement is safe does it proceed to the next row. If a solution is found, it's converted to a string representation for the output.

Code

#include <vector>
#include <string>

using namespace std;

bool isSafe(int row, int col, const vector<int>& placement) {
    for (int prevRow = 0; prevRow < row; ++prevRow) {
        // Check same column
        if (placement[prevRow] == col) return false;
        // Check diagonals
        if (abs(placement[prevRow] - col) == row - prevRow) return false;
    }
    return true;
}

void solveNQueensUtil(int row, int n, vector<int>& placement, vector<vector<string>>& result) {
    if (row == n) {
        vector<string> board(n, string(n, '.'));
        for (int i = 0; i < n; ++i) {
            board[i][placement[i]] = 'Q';
        }
        result.push_back(board);
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (isSafe(row, col, placement)) {
            placement[row] = col;
            solveNQueensUtil(row + 1, n, placement, result);
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<int> placement(n);
    solveNQueensUtil(0, n, placement, result);
    return result;
}

Complexity

• Time Complexity: O(N!), where N is the size of the chessboard. In the worst case, we explore all possible permutations of queen placements.
• Space Complexity: O(N^2) to store the result (board configurations) and O(N) for the recursive call stack and the placement vector.