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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5bool isValid(int row, int col, int* queens) {
6 for (int i = 0; i < row; ++i) {
7 int placedQueenCol = queens[i];
8 if (placedQueenCol == col ||
9 placedQueenCol - col == row - i ||
10 placedQueenCol - col == i - row) {
11 return false;
12 }
13 }
14 return true;
15}
16
17void solve(int n, int row, int* queens, char** board, int* resultCount, char**** results) {
18 if (row == n) {
19 *results = realloc(*results, sizeof(char**) * (*resultCount + 1));
20 char** newSolution = (char**)malloc(sizeof(char*) * n);
21 for (int i = 0; i < n; ++i) {
22 newSolution[i] = (char*)malloc(sizeof(char) * (n + 1));
23 for (int j = 0; j < n; ++j) {
24 newSolution[i][j] = board[i][j];
25 }
26 newSolution[i][n] = '\0';
27 }
28 (*results)[*resultCount] = newSolution;
29 (*resultCount)++;
30 return;
31 }
32
33 for (int col = 0; col < n; ++col) {
34 if (isValid(row, col, queens)) {
35 queens[row] = col;
36 board[row][col] = 'Q';
37 solve(n, row + 1, queens, board, resultCount, results);
38 board[row][col] = '.'; // backtrack
39 }
40 }
41}
42
43char*** solveNQueens(int n, int* returnSize) {
44 char*** results = (char***)malloc(sizeof(char**));
45 *returnSize = 0;
46 int* queens = malloc(sizeof(int) * n);
47 char** board = malloc(sizeof(char*) * n);
48 for (int i = 0; i < n; ++i) {
49 board[i] = malloc(sizeof(char) * (n));
50 for (int j = 0; j < n; ++j) {
51 board[i][j] = '.';
52 }
53 }
54 solve(n, 0, queens, board, returnSize, &results);
55 for (int i = 0; i < n; ++i) {
56 free(board[i]);
57 }
58 free(board);
59 free(queens);
60 return results;
61}
62
63int main() {
64 int n = 4;
65 int returnSize;
66 char*** results = solveNQueens(n, &returnSize);
67 for (int i = 0; i < returnSize; ++i) {
68 for (int j = 0; j < n; ++j) {
69 printf("%s\n", results[i][j]);
70 }
71 printf("\n");
72 }
73 return 0;
74}This C solution uses a backtracking approach to place queens row by row, ensuring each placement is valid by checking current column and diagonal conflicts. The recursive function solve advances to next row if a queen is placed, or backtracks if a conflict arises. Valid solutions are stored in a dynamically resized list of boards.
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.
1from typing import List
2
3def solveNQueens(
This Python implementation enhances the typical backtracking with bit positioning. The current column and diagonals are represented with list-formed negative and positive differential tracking to accommodate queen positions and check constraints efficiently.