Login
Find remaining queens for nqueens problem
As the title says, I have to find the remaining queens for the nqueens problem, but I have not use recursive calls and I have to use stacks and backtracking. Currently I have:
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 11
typedef struct {
int row;
int col;
} Queen;
typedef struct {
int top;
Queen items[MAX_N];
} Stack;
void initStack(Stack* stack) {
stack->top = -1;
}
void push(Stack* stack, Queen queen) {
if (stack->top < MAX_N - 1) {
stack->top++;
stack->items[stack->top] = queen;
}
}
Queen pop(Stack* stack) {
if (stack->top >= 0) {
stack->top--;
return stack->items[stack->top];
}
Queen emptyQueen = { -1, -1 }; // Return an invalid queen
return emptyQueen;
}
// Helper function to check if a queen can be placed at (row, col)
bool isValid(Queen queens[], int numQueens, int row, int col) {
for (int i = 0; i < numQueens; i++) {
if (queens[i].row == row || queens[i].col == col ||
queens[i].row - queens[i].col == row - col ||
queens[i].row + queens[i].col == row + col) {
return false; // Queens attack each other
}
}
return true;
}
void solveQueens(int max_queens, Queen* initQs, int numInitQ) {
Queen queens[MAX_N];
Stack stack;
initStack(&stack);
// Initialize with initial queens
for (int i = 0; i < numInitQ; i++) {
queens[i] = initQs[i];
}
int numQueens = numInitQ;
int row = numInitQ; // Start from the next row
while (numQueens < max_queens) {
bool found = false;
for (int col = 0; col < max_queens; col++) {
if (isValid(queens, numQueens, row, col)) {
queens[numQueens] = (Queen){ row, col };
numQueens++;
found = true;
break;
}
}
if (!found) { //backtrack, pop the queen
queens[numQueens - 1] = pop(&stack);
numQueens--;
row = queens[numQueens - 1].row + 1;
if(numQueens <= numInitQ){ //there are not enough queens in total, therefore no solution
printf("no solution\n");
return;
}
} else {
push(&stack, queens[numQueens - 1]);
row++;
}
}
// Print the solution
for (int i = 0; i < numQueens; i++) {
printf("%d %d\n", queens[i].row, queens[i].col);
}
}
for testing, I have used the main function:
int main() {
Queen initialQueens[] = { {0, 0} }; // Example initial queens
int numInitialQueens = 1;
int maxQueens = 4; // Change this to the board size
solveQueens(maxQueens, initialQueens, numInitialQueens);
return 0;
}
Which expectedly prints No Solution. However, when I try to make the board size 5 (setting maxQueens to 5) the function enters an infinite loop. My theory is that this is probably caused by the function finding a valid queen, but the total number of queens is not enough, which causes it to backtrack repeatedly. Don't take my word for the error, I could be way off but it might be a lead. Anyone got any fixes and suggestions?
