# N Queens

Then-queens puzzle is the problem of placingnqueens on ann×nchessboard such that no two queens attack each other.

![](https://leetcode.com/static/images/problemset/8-queens.png)

Given an integern, return all distinct solutions to then-queens puzzle.

Each solution contains a distinct board configuration of then-queens' placement, where`'Q'`and`'.'`both indicate a queen and an empty space respectively.

For example,\
There exist two distinct solutions to the 4-queens puzzle:

```
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
```

**Approach 1: Brute Force**

Check every permutable position on the chess board. This can be done by mapping each position on the board to a unique key that identifies it's `i,j` position - and then checking all $$\_{n(n)}P\_n$$ arrangement's, where n is the number of queens.

```cpp
using c_boards = vector<vector<vector<char>>>;
using c_board = vector<vector<char>>;
using c_row = vector<char>;

struct VectorHash {
    size_t operator()(const c_board& board) const {
        std::hash<char> hasher;
        size_t seed = 0;
        for (c_row row : board) {
            for (char c : row) {
                seed ^= hasher(c) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
            }
        }
        return seed;
    }
};

static class NQueens {
public:


    c_boards solveNQueens(int num_q) {
        unordered_set<c_board, VectorHash> unique_boards;
        c_boards valid_boards;
        unordered_map<int, pair<int, int>> chess_ids = get_chess_ids(num_q);
        c_board blank_chess_board(num_q, vector<char>(num_q, '.'));

        int ignore_next = num_q;
        const int n = num_q * num_q;
        const int k = num_q;
        vector<int> current_queen_keys(n);
        iota(current_queen_keys.begin(), current_queen_keys.end(), 1);
        do
        {
            vector<pair<int, int>> q_locs = map_ids_to_queen_positions(chess_ids, current_queen_keys.begin(), current_queen_keys.begin() + k);
            vector<c_row> next_board = map_queens(blank_chess_board, q_locs);
            if (confirm_stalemate(next_board) && unique_boards.find(next_board) == unique_boards.end()) {
                unique_boards.insert(next_board);
                valid_boards.push_back(next_board);
                print2d(next_board);
            }
            reverse(current_queen_keys.begin() + k, current_queen_keys.end());
        } while (next_permutation(current_queen_keys.begin(), current_queen_keys.end()));

        return valid_boards;
    }

private:

    unordered_map<int, pair<int, int>> get_chess_ids(int num_q) {
        unordered_map<int, pair<int, int>> chess_location_ids;
        const int num_elms = num_q * num_q;
        chess_location_ids.reserve(num_elms);
        int id = 1;

        for (int i = 0; i < num_q; i++) {
            for (int j = 0; j < num_q; j++) {
                chess_location_ids[id++] = { i,j };
            }
        }

        return chess_location_ids;
    }

    bool confirm_grounded_queen(const pair<int, int> q_pos, const c_board &board) {
        int i, j;
        for (i = q_pos.second + 1; i < board.size(); i++)
            if (board[q_pos.first][i] == 'Q') return false; // right

        for (i = q_pos.second - 1; i < board.size(); i--)
            if (board[q_pos.first][i] == 'Q') return false; // left 

        for (i = q_pos.first + 1; i < board.size(); i++)
            if (board[i][q_pos.second] == 'Q') return false; // down

        for (i = q_pos.first - 1; i < board.size(); i--)
            if (board[i][q_pos.second] == 'Q') return false; // up

        for (i = q_pos.first - 1,
             j = q_pos.second + 1;
             i < board.size() && j < board.at(i).size();
             i--, j++)
             if (board[i][j] == 'Q') return false; // diagonal right up

        for (i = q_pos.first + 1,
             j = q_pos.second - 1;
             i < board.size() && j < board.at(i).size();
             i++, j--)
             if (board[i][j] == 'Q') return false; // diagonal left down

        for (i = q_pos.first + 1,
             j = q_pos.second + 1;
             i < board.size() && j < board.at(i).size();
             i++, j++)
             if (board[i][j] == 'Q') return false; // diagonal right down

        for (i = q_pos.first - 1,
             j = q_pos.second - 1;
             i < board.size() && j < board.at(i).size();
             i--, j--)
             if (board[i][j] == 'Q') return false; // diagonal left up
    }

    bool confirm_stalemate(const c_board &board) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.size(); j++) {
                if (board[i][j] == 'Q' && !confirm_grounded_queen({ i,j }, board))
                    return false;
            }
        }
        return true;
    }

    template<typename iter>
    vector<pair<int, int>> map_ids_to_queen_positions(const unordered_map<int, pair<int, int>> &key, iter id_start, iter id_end) {
        vector<pair<int, int>> queen_locs; queen_locs.reserve(distance(id_start, id_end));
        for (auto i = id_start; i != id_end; i++) 
            queen_locs.push_back(key.at(*i));
        return queen_locs;
    }

    c_board map_queens(const c_board &blank_board, const vector<pair<int, int>> &q_pos) {
        c_board board_cp = blank_board;
        for (const pair<int, int> &p : q_pos)
            board_cp[p.first][p.second] = 'Q';
        return board_cp;
    }
};

int main() 
{
    NQueens q;
    for (int i : {1, 2, 3, 4, 5, 6, 7, 8, 9}) {
        cout << i << " x " << i << " BOARD:" << endl;
        q.solveNQueens(i);
    }
}
```

**Example Output**

```
1 x 1 BOARD:

0: Q


2 x 2 BOARD:
3 x 3 BOARD:
4 x 4 BOARD:

0: .  Q  .  .
1: .  .  .  Q
2: Q  .  .  .
3: .  .  Q  .



0: .  .  Q  .
1: Q  .  .  .
2: .  .  .  Q
3: .  Q  .  .


5 x 5 BOARD:

0: Q  .  .  .  .
1: .  .  Q  .  .
2: .  .  .  .  Q
3: .  Q  .  .  .
4: .  .  .  Q  .



0: Q  .  .  .  .
1: .  .  .  Q  .
2: .  Q  .  .  .
3: .  .  .  .  Q
4: .  .  Q  .  .



0: .  Q  .  .  .
1: .  .  .  Q  .
2: Q  .  .  .  .
3: .  .  Q  .  .
4: .  .  .  .  Q

...
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/combinatorics/n-queens.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.