如何解决C语言递归3x3幻方生成器的数值重复问题

问题说明 #

你提供的递归幻方生成代码会生成包含重复数值的结果，核心原因是填充每个位置时没有检查数字是否已被使用，且循环条件错误（未包含数字9）。以下是修正后的实现方案，确保生成的幻方仅包含1-9的不重复数值。

修正思路 #

1. 追踪已使用数字：添加一个数组记录哪些数字已经被填入幻方，填充前检查数字是否未被使用，避免重复。
2. 回溯恢复标记：递归返回后，取消当前数字的已使用标记，让后续递归可以复用该数字。
3. 修正循环范围：确保遍历1-9的所有数字，原代码循环条件遗漏了数字9。

修正后的完整代码 #

#include <stdio.h>

// used数组用于追踪1-9中哪些数字已被使用（索引对应数字，值为1表示已用，0表示未用）
void magic_square(int *grid, int next_slot, int used[]) 
{
    if (next_slot < 9) 
    {
        // 遍历1-9的所有数字
        for (int i = 1; i <= 9; i++) 
        {
            // 仅使用未被标记的数字
            if (!used[i]) 
            {
                used[i] = 1; // 标记为已使用
                grid[next_slot] = i;
                magic_square(grid, next_slot + 1, used);
                used[i] = 0; // 回溯，取消标记
            }
        }
    } 
    else 
    {
        const int sum = grid[0] + grid[1] + grid[2];
        // 检查所有行、列、对角线的和是否相等
        if (grid[3] + grid[4] + grid[5] != sum) return;
        if (grid[6] + grid[7] + grid[8] != sum) return;
        if (grid[0] + grid[3] + grid[6] != sum) return;
        if (grid[1] + grid[4] + grid[7] != sum) return;
        if (grid[2] + grid[5] + grid[8] != sum) return;
        if (grid[0] + grid[4] + grid[8] != sum) return;
        if (grid[2] + grid[4] + grid[6] != sum) return;
        
        // 打印符合条件的幻方
        printf("%3d %3d %3d\n%3d %3d %3d\n%3d %3d %3d\n\n",
               grid[0], grid[1], grid[2],
               grid[3], grid[4], grid[5],
               grid[6], grid[7], grid[8]);
    }
}

int main(void) 
{
    int grid[9];
    int used[10] = {0}; // 索引0未使用，1-9对应数字1-9的使用状态
    magic_square(grid, 0, used);
    return 0;
}

关键修改点说明 #

• used数组的作用：通过used[i]标记数字i是否已被填入幻方，填充前判断!used[i]确保数字唯一。
• 回溯操作：递归调用完成后将used[i]重置为0，保证后续分支可以继续使用该数字，这是递归回溯算法的核心步骤。
• 循环范围修正：将原代码的i < max_value改为i <= 9，确保覆盖1-9的所有数字。

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