无需递归且用少于n层循环求解n皇后问题可行吗？

嘿，这个问题问得好！其实不用递归也不用8层嵌套循环，咱们完全可以用2-3层循环搞定8皇后问题——核心思路是换个遍历方式，别盯着64个格子挨个试，而是针对每行皇后的列位置组合来遍历，毕竟8皇后的规则本身就要求每行必须且只能放一个皇后对吧？

为什么遍历64个格子行不通？ #

你之前尝试遍历所有格子的思路，会大量重复考虑“同一行放多个皇后”的无效情况，这完全是在做无用功。8皇后的核心约束是每行一个皇后，所以我们只需要遍历“每行皇后的列位置”的所有可能组合，再校验这些组合是否符合列不重复、对角线不冲突的规则即可。

2-3层循环的实现方案 #

我们可以把8行的列位置拆分成几个组，用2-3层循环分别生成每组的列位置组合，再拼接成完整的8行配置进行校验。比如拆成「3行+3行+2行」的结构，用三层循环覆盖所有可能的列组合：

具体C语言实现代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 校验当前皇后列位置组合是否合法
bool is_valid(int queen_col[]) {
    // 用位掩码快速检查列是否重复（效率比数组更高）
    int col_mask = 0;
    for (int i = 0; i < 8; i++) {
        int col = queen_col[i];
        if (col_mask & (1 << col)) {
            return false;
        }
        col_mask |= (1 << col);
    }

    // 检查对角线冲突：任意两行的行差不能等于列差
    for (int i = 0; i < 8; i++) {
        for (int j = i + 1; j < 8; j++) {
            int row_diff = abs(i - j);
            int col_diff = abs(queen_col[i] - queen_col[j]);
            if (row_diff == col_diff) {
                return false;
            }
        }
    }

    return true;
}

// 打印一个合法的8皇后解
void print_solution(int queen_col[]) {
    printf("合法解:\n");
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            printf(queen_col[i] == j ? "Q " : ". ");
        }
        printf("\n");
    }
    printf("\n");
}

int main() {
    int queen_col[8]; // queen_col[i] = 第i行皇后所在的列（0-7）
    int solution_count = 0;

    // 三层循环：分别生成前3行、中间3行、最后2行的列位置组合
    // 前3行：用7进制编码，a的范围是0~7^3-1=342
    for (int a = 0; a < 343; a++) {
        queen_col[0] = a / 49;          // 取7进制最高位
        queen_col[1] = (a / 7) % 7;     // 取7进制中间位
        queen_col[2] = a % 7;           // 取7进制最低位

        // 中间3行：同理处理行3、4、5
        for (int b = 0; b < 343; b++) {
            queen_col[3] = b / 49;
            queen_col[4] = (b / 7) % 7;
            queen_col[5] = b % 7;

            // 最后2行：用7进制编码，c的范围是0~7^2-1=48
            for (int c = 0; c < 49; c++) {
                queen_col[6] = c / 7;
                queen_col[7] = c % 7;

                // 校验并统计合法解
                if (is_valid(queen_col)) {
                    solution_count++;
                    print_solution(queen_col);
                }
            }
        }
    }

    printf("总共找到%d个合法解\n", solution_count);
    return 0;
}

关键细节说明

1. 分层循环的逻辑：把8行拆成三组，用7进制编码每组的列位置（因为列是0-7共8种可能），通过循环变量的进制转换，快速得到每行的列值，避免了8层嵌套。
2. 提前优化（可选）：可以在每层循环内部提前校验当前组的行是否存在冲突，比如生成前3行后先检查这3行的列和对角线是否冲突，不合法就直接跳过后续循环，能大幅减少无效计算。
3. 暴力但高效：虽然本质是暴力枚举，但我们只遍历了所有可能的「每行列位置组合」（共8^8=16777216次循环），比遍历64个格子的无效尝试要高效得多。

内容的提问来源于stack exchange，提问作者bilanush