<p>The <strong>n-queens</strong> puzzle is the problem of placing <code>n</code> queens on an <code>n x n</code> chessboard such that no two queens attack each other.</p>

<p>Given an integer <code>n</code>, return <em>all distinct solutions to the <strong>n-queens puzzle</strong></em>. You may return the answer in <strong>any order</strong>.</p>

<p>Each solution contains a distinct board configuration of the n-queens&#39; placement, where <code>&#39;Q&#39;</code> and <code>&#39;.&#39;</code> both indicate a queen and an empty space, respectively.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" style="width: 600px; height: 268px;" />
<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> [[&quot;.Q..&quot;,&quot;...Q&quot;,&quot;Q...&quot;,&quot;..Q.&quot;],[&quot;..Q.&quot;,&quot;Q...&quot;,&quot;...Q&quot;,&quot;.Q..&quot;]]
<strong>Explanation:</strong> There exist two distinct solutions to the 4-queens puzzle as shown above
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> [[&quot;Q&quot;]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 9</code></li>
</ul>

struct boardDesc {
public:
    set<pair<int,int>> queens;
    map<int, set<int>> validSlots;
};

class Solution {
public:
    boardDesc emptyBoard(int n) {
        boardDesc board;

        set<int> emptyRow;
        for (int j = 0; j < n; ++j) {
            emptyRow.insert(j);
        }

        for (int i = 0; i < n; ++i) {
            board.validSlots[i] = emptyRow;
        }
        return board;
    }
    vector<boardDesc> solveNQueens(int n, int queens) {
        if (queens == 0)
            return vector<boardDesc>(1, emptyBoard(n)); // empty board

        auto boardsToCheck = solveNQueens(n, queens - 1);
        cout << boardsToCheck.size() << " solutions for " << queens - 1 << " queens" << endl;
        vector<boardDesc> validBoards;

        for (auto & board : boardsToCheck) {
            for (auto it = board.validSlots.begin(); it != board.validSlots.end(); ++it) {
                int i = it->first;
                auto cols = it->second;
                board.validSlots.erase(it);

                if (board.validSlots.size() < n - queens) continue;

                for (auto it2 = cols.begin(); it2 != cols.end(); ++it2) {
                    int j = *it2;
                    cols.erase(it2);

                    boardDesc boardCopy = board;
                    int diag = 1;
                    for (auto it3 = boardCopy.validSlots.begin(); it3 != boardCopy.validSlots.end(); ++it3) {
                        it3->second.erase(j);
                        if (j + diag < n)
                            it3->second.erase(j + diag);
                        if (j - diag >= 0)
                            it3->second.erase(j - diag);

                        if (it3->second.empty())
                            boardCopy.validSlots.erase(it3);
                        diag++;
                    }

                    if (boardCopy.validSlots.size() < n - queens) continue;

                    boardCopy.queens.insert({i, j});
                    validBoards.push_back(boardCopy);
                }
            }
        }

        return validBoards;
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> boards;
        auto results = solveNQueens(n, n);
        cout << results.size() << " solutions for " << n << " queens" << endl;
        for (auto board : results) {
            vector<string> boardRowStrings;
            for (int i = 0; i < n; ++i) {
                string rowStr;
                for (int j = 0; j < n; ++j) {
                    if (board.queens.find({i, j}) != board.queens.end()) 
                        rowStr += "Q";
                    else
                        rowStr += ".";
                }

                boardRowStrings.push_back(rowStr);
            }
            boards.push_back(boardRowStrings);
        }    
        return boards;
    }
};
44790