N-Queens

Problem Statement

The n-queens puzzle is a classic combinatorial problem that involves placing n queens on an n x n chessboard so that no two queens threaten each other. A queen in chess can attack any piece in the same row, column, or diagonal. The solution to the puzzle requires that no two queens share the same row, column, or diagonal.

The task is to find all the unique board configurations where the queens are placed such that none of them can attack one another. Each solution should provide a distinct arrangement of the n-queens on the board, with each queen represented by 'Q' and empty spaces represented by '.'.

Examples

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

Approach and Intuition

The n-queens puzzle can be approached using backtracking, a method that builds solutions one piece at a time and abandons a solution ("backtracks") as soon as it determines that the solution is not valid. Below is how one might think about solving the n-queens puzzle:

1. Start with an empty n x n board.
2. Place a queen in the first row and in each column one by one and then proceed to the next row:
   • For each placement of the queen, check if it leads to a valid configuration by ensuring no two queens attack each other.
3. On the current row, if placing a queen on any column violates the attack condition with any already placed queen in previous rows (check rows, columns, and diagonals), skip placing the queen in that column.
4. If a valid position is found, place the queen ('Q'), and move to the next row.
5. If placing the queen in any row/column leads to a contradiction (no valid columns left in the next row), backtrack:
   • Remove the queen from the current row and move the queen position in the previous row.
6. Continue this process until:
   • You have filled all rows successfully, at which point you add the solution to the list of solutions.
   • All possible board configurations have been attempted (all combinations of rows and columns).
7. Return all the distinct board configurations.

Examples and constraints lead us to understand the scale and potential edge cases for the problem:

• For n = 1, the solution is straightforward since only one queen on a 1x1 board doesn't have any possibility of attack.
• For n = 4 as shown in the example, the problem exhibits multiple distinct solutions, illustrating the requirement to explore various configurations. The backtracking approach efficiently navigates these while ensuring all conditions (row, column, diagonal non-attack) are met.

Given the constraints (1 <= n <= 9), the recursive backtracking solution is computationally feasible as it effectively handles smaller boards through systematic exploration of potential placements, ensuring all solutions are found.

Solutions

class Solution {
private:
    int boardSize;
    vector<vector<string>> resultSets;
    
    vector<string> generateBoard(vector<vector<char>> layout) {
        vector<string> chessboard;
        for (int i = 0; i < boardSize; ++i) {
            string row(layout[i].begin(), layout[i].end());
            chessboard.push_back(row);
        }
        return chessboard;
    }
    void placeQueens(int currentRow, unordered_set<int> diag,
                     unordered_set<int> antiDiag, unordered_set<int> columns,
                     vector<vector<char>> boardState) {
        if (currentRow == boardSize) {
            resultSets.push_back(generateBoard(boardState));
            return;
        }
        for (int currentCol = 0; currentCol < boardSize; ++currentCol) {
            int diagKey = currentRow - currentCol;
            int antiDiagKey = currentRow + currentCol;
            if (columns.count(currentCol) || diag.count(diagKey) ||
                antiDiag.count(antiDiagKey)) {
                continue;
            }
            columns.insert(currentCol);
            diag.insert(diagKey);
            antiDiag.insert(antiDiagKey);
            boardState[currentRow][currentCol] = 'Q';
            placeQueens(currentRow + 1, diag, antiDiag, columns, boardState);
            columns.erase(currentCol);
            diag.erase(diagKey);
            antiDiag.erase(antiDiagKey);
            boardState[currentRow][currentCol] = '.';
        }
    }
    
public:
    vector<vector<string>> solveNQueens(int n) {
        boardSize = n;
        vector<vector<char>> initialBoard(boardSize, vector<char>(boardSize, '.'));
        placeQueens(0, unordered_set<int>(), unordered_set<int>(),
                    unordered_set<int>(), initialBoard);
        return resultSets;
    }
};