非递归栈+回溯实现N皇后剩余皇后求解的无限循环问题求助

问题描述 #

需要实现N皇后问题的剩余皇后补全功能，要求必须使用栈+回溯，禁止递归。现有代码在测试4皇后（初始皇后{0,0}）时能正确输出无解，但测试5皇后时陷入无限循环。补充测试用例：

• 初始皇后{0,1}, {1,4}（原测试用例写的{1,5}为笔误，5皇后列索引范围是0-4，对应输出格式为1 2 2 5 3 3 4 1 5 4）应输出指定解
• 初始皇后{0,0}, {1,4}应输出无解

现有代码 #

核心实现代码 #

#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 emptyQueen;
}

// 检查(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;
        }
    }
    return true;
}

void solveQueens(int max_queens, Queen* initQs, int numInitQ) {
    Queen queens[MAX_N];
    Stack stack;
    initStack(&stack);

    // 初始化初始皇后
    for (int i = 0; i < numInitQ; i++) {
        queens[i] = initQs[i];
    }

    int numQueens = numInitQ;
    int row = numInitQ; // 从下一行开始尝试

    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) {   // 回溯，弹出皇后
            queens[numQueens - 1] = pop(&stack); // 错误：回溯无需覆盖数组元素
            numQueens--;
            row = queens[numQueens - 1].row + 1; // 错误：应在同一行尝试下一列而非跳行
            if(numQueens <= numInitQ){
                printf("no solution\n");
                return;
            }
        } else {
            push(&stack, queens[numQueens - 1]);
            row++;
        }
    }

    // 输出解
    for (int i = 0; i < numQueens; i++) {
        printf("%d %d\n", queens[i].row+1, queens[i].col+1);
    }
}

测试用例代码 #

int main() {
    Queen initialQueens[] = { {0, 0} }; // 示例初始皇后
    int numInitialQueens = 1;
    int maxQueens = 4; // 修改为对应棋盘大小
    solveQueens(maxQueens, initialQueens, numInitialQueens);
    return 0;
}

问题根源分析 #

1. Pop函数逻辑错误：原函数先递减top再返回元素，导致返回的是新栈顶元素而非被弹出的目标元素，回溯状态完全混乱。
2. 回溯行列处理错误：当前行找不到合法列时，应回到上一个皇后的行，从该皇后的下一列开始尝试，而非跳到下一行，这是无限循环的核心原因。
3. 初始皇后未入栈：初始皇后仅存入数组但未压入栈，导致回溯到初始状态时无法正确获取上一步信息，触发错误的无解判断。
4. 回溯数组操作冗余：回溯时无需用弹出的皇后覆盖数组元素，只需减少numQueens即可，后续新元素会自动覆盖旧位置。

修复后的完整代码 #

#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) {
        Queen popped = stack->items[stack->top]; // 先保存被弹出的元素
        stack->top--;
        return popped;
    }
    Queen emptyQueen = { -1, -1 };
    return emptyQueen;
}

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;
        }
    }
    return true;
}

void solveQueens(int max_queens, Queen* initQs, int numInitQ) {
    Queen queens[MAX_N];
    Stack stack;
    initStack(&stack);

    // 初始化：初始皇后存入数组并压入栈
    for (int i = 0; i < numInitQ; i++) {
        queens[i] = initQs[i];
        push(&stack, queens[i]);
    }

    int numQueens = numInitQ;
    int currentRow = numInitQ; // 当前尝试的行
    int startCol = 0; // 当前行的起始尝试列

    while (numQueens < max_queens) {
        bool found = false;
        // 从startCol开始尝试当前行的列
        for (int col = startCol; col < max_queens; col++) {
            if (isValid(queens, numQueens, currentRow, col)) {
                queens[numQueens] = (Queen){ currentRow, col };
                push(&stack, queens[numQueens]);
                numQueens++;
                found = true;
                currentRow++;
                startCol = 0; // 下一行从第0列开始
                break;
            }
        }

        if (!found) {
            // 回溯：弹出最后一个皇后
            if (numQueens <= numInitQ) {
                printf("no solution\n");
                return;
            }
            Queen popped = pop(&stack);
            numQueens--;
            currentRow = popped.row; // 回到弹出皇后所在的行
            startCol = popped.col + 1; // 从该皇后的下一列开始尝试
        }
    }

    // 输出解
    for (int i = 0; i < numQueens; i++) {
        printf("%d %d\n", queens[i].row + 1, queens[i].col + 1);
    }
}

// 测试用例
int main() {
    // 测试用例1：5皇后，初始{0,1}, {1,4}
    Queen initialQueens1[] = { {0, 1}, {1, 4} };
    int numInitial1 = 2;
    int maxQueens1 = 5;
    printf("Test Case 1:\n");
    solveQueens(maxQueens1, initialQueens1, numInitial1);

    // 测试用例2：5皇后，初始{0,0}, {1,4}
    Queen initialQueens2[] = { {0, 0}, {1, 4} };
    int numInitial2 = 2;
    int maxQueens2 = 5;
    printf("\nTest Case 2:\n");
    solveQueens(maxQueens2, initialQueens2, numInitial2);

    // 测试用例3：4皇后，初始{0,0}
    Queen initialQueens3[] = { {0, 0} };
    int numInitial3 = 1;
    int maxQueens3 = 4;
    printf("\nTest Case 3:\n");
    solveQueens(maxQueens3, initialQueens3, numInitial3);

    return 0;
}

关键修改点说明 #

1. 修复Pop函数：先保存栈顶元素再递减top，确保返回的是被弹出的皇后。
2. 新增startCol变量：记录当前行的起始尝试列，回溯时从弹出皇后的下一列开始，避免重复尝试无效列。
3. 初始皇后入栈：初始化时将所有初始皇后压入栈，保证回溯逻辑的连贯性。
4. 修正回溯逻辑：回溯时回到弹出皇后的行，从下一列开始尝试，避免跳行导致的无限循环。
5. 优化循环逻辑：将行和起始列分开管理，避免原代码中row变量的混乱赋值。

测试验证 #

• 测试用例1：输出正确解1 2、2 5、3 3、4 1、5 4。
• 测试用例2：输出no solution。
• 测试用例3：输出no solution。
• 5皇后初始{0,0}：不再无限循环，能正确找到解或判断无解。

内容的提问来源于stack exchange，提问作者The-coder-E