C语言奇偶性约束矩阵生成程序问题：n>1时无输出

你的C程序在n>1时无法生成符合要求的矩阵，核心问题出在check函数的逻辑错误，以及回溯过程中不必要的无效判断：

问题根源 #

1. 错误检查未填充的邻居：check函数里对row < n-1和col < n-1的邻居进行判断，但这些位置还没被赋值，存储的是随机垃圾值，导致check函数误判所有可能的val，直接跳过，无法找到合法解。
2. 未利用奇偶性的棋盘规律：题目要求相邻元素奇偶性不同，本质是棋盘式分布——每个位置的奇偶性由行号+列号的奇偶性决定：
   • 若row+col为偶数，该位置必须是奇数（或偶数，只要规则统一）；
   • 若row+col为奇数，该位置必须是偶数（或奇数）。
     不需要检查所有邻居，只要遵循这个规则，相邻元素的奇偶性必然不同。

修复后的完整代码 #

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

#define MAX_N 10

int n;
int matrix[MAX_N][MAX_N];
bool used[MAX_N * MAX_N + 1];
int count = 0;

// 检查当前值是否符合位置的奇偶性要求，且未被使用
bool check(int row, int col, int val) {
    // 规则：row+col为偶数 → 填奇数；row+col为奇数 → 填偶数
    int required_is_odd = (row + col) % 2 == 0;
    int val_is_odd = val % 2 == 1;
    return required_is_odd == val_is_odd && !used[val];
}

void print_matrix() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void backtrack(int row, int col) {
    if (row == n) {
        count++;
        print_matrix();
        return;
    }
    if (col == n) {
        backtrack(row + 1, 0);
        return;
    }
    // 直接遍历符合当前位置奇偶性的数值，减少无效循环
    int start = ((row + col) % 2 == 0) ? 1 : 2;
    for (int val = start; val <= n * n; val += 2) {
        if (!used[val]) {
            matrix[row][col] = val;
            used[val] = true;
            backtrack(row, col + 1);
            used[val] = false;
        }
    }
}

int main() {
    printf("Enter the size of the array n (max %d): ", MAX_N);
    scanf("%d", &n);
    if (n <= 0 || n > MAX_N) {
        printf("Invalid array size.\n");
        return 0;
    }
    printf("Matrices meeting the condition:\n");
    backtrack(0, 0);
    printf("Total valid matrices: %d\n", count);
    return 0;
}

关键优化点 #

1. 重构check函数：删除对未填充邻居的无效判断，直接根据位置的row+col奇偶性匹配val的奇偶性，确保相邻元素奇偶性必然不同。
2. 优化回溯循环：根据当前位置的奇偶性要求，只遍历对应奇偶的数值（比如奇数位置只遍历1、3、5...），大幅减少循环次数，提升运行效率。
3. 逻辑简化：去掉不必要的解存在性判断（因为{1,...,n²}中的奇偶数量正好匹配棋盘分布的需求：n为奇数时奇数比偶数多1，n为偶数时数量相等）。

测试示例 #

当n=2时，程序会输出所有合法矩阵，例如：

1 2 
4 3 

1 4 
2 3 

3 2 
4 1 

3 4 
2 1 
...

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