Sponsored
Sponsored
This approach involves using backtracking to place queens row by row, exploring valid positions recursively. Each queen placement is validated based on column and diagonal restrictions. If a valid placement is found, the algorithm progresses to the next row, otherwise it backtracks and attempts alternative placements.
Time Complexity: O(N!), because we are trying N possible positions for each row for N queens.
Space Complexity: O(N^2), due to the storage of the board states and recursion stack.
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6void backtrack(vector<vector<string>>& solutions, vector<string>& board, vector<bool>& cols, vector<bool>& d1, vector<bool>& d2, int row, int n) {
7 if (row == n) {
8 solutions.push_back(board);
9 return;
10 }
11
12 for (int col = 0; col < n; col++) {
13 int id1 = col - row + n;
14 int id2 = col + row;
15 if (!cols[col] && !d1[id1] && !d2[id2]) {
16 board[row][col] = 'Q';
17 cols[col] = d1[id1] = d2[id2] = true;
18 backtrack(solutions, board, cols, d1, d2, row + 1, n);
19 board[row][col] = '.';
20 cols[col] = d1[id1] = d2[id2] = false;
21 }
22 }
23}
24
25vector<vector<string>> solveNQueens(int n) {
26 vector<vector<string>> solutions;
27 vector<string> board(n, string(n, '.'));
28 vector<bool> cols(n, false), d1(2 * n, false), d2(2 * n, false);
29 backtrack(solutions, board, cols, d1, d2, 0, n);
30 return solutions;
31}
32
33int main() {
34 int n = 4;
35 vector<vector<string>> solutions = solveNQueens(n);
36 for (auto& solution : solutions) {
37 for (string& row : solution) {
38 cout << row << endl;
39 }
40 cout << endl;
41 }
42 return 0;
43}This C++ solution implements a backtracking approach. The board and auxiliary vectors are used to represent column and diagonal occupancy status. The function backtrack attempts to place queens row by row. If a complete solution is built, it is saved in solutions.
This approach optimizes the placement verification using bit manipulation, reducing the auxiliary space by managing columns and diagonals in integer bitmasks. This permits efficient bitwise operations for placing queens and checking potential attacks.
Time Complexity: O(N!), each row considers N placements, simplified by binary check.
Space Complexity: O(N), due to condensed state tracking via differential lists.
1import java.util.*;
2
3
This solution in Java embodies bit manipulation to track column and diagonal availability via bitmasks, ensuring low overhead while solving N-Queens recursively. Solutions are compiled as lists of strings to represent the board state efficiently.