N Queens

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

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.

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

...