# 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

...

Last updated