C语言回溯算法实现矩阵生成问题求助：排查代码错误

我需要实现一个回溯算法来生成所有满足以下条件的n×n矩阵（n定义为10）：

1. 矩阵初始化为0，每行、每列恰好包含两个1；
2. 1之间不能有相邻元素（包括对角线相邻）。

以下是我的C语言代码：

#include <stdio.h>

#define n 10
int s[n][n];


int sol_p(int l, int c)
{
    int nrl=0, nrc=0;
    for(int i=0; i<c && nrl<2; i++)
        if(s[l][i] == 1)
            nrl ++;
    for(int i=0; i<l && nrl<2; i++)
        if(s[i][c] == 1)
            nrc ++;
    if(nrl>=2 || nrc>=2)
        return 0;
    if(l>0 && l<n-1 && c>0 && c<n-1)
    {
        if(s[l+1][c]==1 || s[l-1][c]==1 || s[l][c+1]==1 || s[l][c-1]==1 || s[l+1][c+1]==1 || s[l-1][c-1]==1
                || s[l-1][c+1]==1 || s[l+1][c-1]==1 )
            return 0;
    }
    return 1;
}

void bkt(int c)
{
    for(int i=0; i<n; i++)
    {
        if(sol_p(i,c)==1)
        {
            s[i][c]=1;
            if(c == n-1)
            {

                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                        printf("%d ", s[i][j]);
                    printf("\n");
                }
                printf("\n");
            }
            else
                bkt(c+1);


        }


    }
}
int main()
{
    bkt(0);
    return 0;
}

我认为自己的回溯函数bkt存在错误，请求帮忙排查问题所在。

核心问题分析 #

你的代码存在多处逻辑漏洞，导致无法生成符合要求的矩阵，具体问题如下：

1. 回溯无状态回退
   当前代码设置s[i][c] = 1后，没有在递归返回时将该位置重置为0。这会导致后续递归路径中，之前放置的1永久保留在矩阵中，直接破坏行/列的计数规则，也会干扰相邻元素的判断逻辑。

2. 列的计数逻辑缺失
   题目要求每列必须恰好有2个1，但你的bkt函数只是逐个尝试在当前列的行中放1，没有控制每列的1的总数。这会导致某列出现1个、3个甚至更多1的情况，完全不符合约束条件。

3. 相邻元素判断不完整
   sol_p中的相邻判断仅针对非边界位置，边界位置（比如第一行、最后一列）直接跳过了相邻检查，导致边界处的1可以和相邻元素（如同一行的下一个位置）相邻，违反了“1不能相邻”的规则。正确的做法应该是针对每个方向单独判断是否存在，再检查是否有1。

4. 最终验证缺失
   当处理到最后一列时，没有验证每行是否恰好有2个1。即使前面的逻辑没问题，也可能出现某些行只放了1个或0个1的情况，无法保证最终矩阵完全符合要求。

修复建议 #

针对上述问题，给出核心修复点：

1. 添加回溯状态回退
   在递归调用bkt(c+1)后，必须重置当前位置的状态：

   s[i][c] = 1;
   if (c == n-1) {
       // 验证并输出矩阵
   } else {
       bkt(c+1);
   }
   s[i][c] = 0; // 递归返回后恢复状态
   

2. 调整回溯逻辑，确保每列恰好2个1
   因为每列需要固定2个1，所以回溯时应该枚举当前列中两个不同的行i和j（i < j），检查这两个位置都符合约束条件后，再设置为1并递归：

   void bkt(int c) {
       // 枚举当前列的两个不同行
       for (int i = 0; i < n; i++) {
           for (int j = i + 1; j < n; j++) {
               if (sol_p(i, c) && sol_p(j, c)) {
                   // 检查i和j之间是否相邻（包括对角线）
                   if (abs(i - j) <= 1) continue;
                   s[i][c] = 1;
                   s[j][c] = 1;
                   if (c == n-1) {
                       // 验证每行是否恰好2个1，再输出
                       int valid = 1;
                       for (int row = 0; row < n; row++) {
                           int cnt = 0;
                           for (int col = 0; col < n; col++) {
                               if (s[row][col] == 1) cnt++;
                           }
                           if (cnt != 2) {
                               valid = 0;
                               break;
                           }
                       }
                       if (valid) {
                           // 输出矩阵
                           for (int row = 0; row < n; row++) {
                               for (int col = 0; col < n; col++) {
                                   printf("%d ", s[row][col]);
                               }
                               printf("\n");
                           }
                           printf("\n");
                       }
                   } else {
                       bkt(c + 1);
                   }
                   // 回退状态
                   s[i][c] = 0;
                   s[j][c] = 0;
               }
           }
       }
   }
   

3. 完善相邻判断逻辑
   修改sol_p中的相邻判断，去掉边界限制，逐个方向检查：

   int sol_p(int l, int c)
   {
       int nrl = 0;
       // 检查当前行已有的1数量
       for(int i = 0; i < n; i++) {
           if(s[l][i] == 1) nrl++;
       }
       if(nrl >= 2) return 0;
   
       // 检查8个方向是否有1
       if ((l > 0 && s[l-1][c] == 1) ||
           (l < n-1 && s[l+1][c] == 1) ||
           (c > 0 && s[l][c-1] == 1) ||
           (c < n-1 && s[l][c+1] == 1) ||
           (l > 0 && c > 0 && s[l-1][c-1] == 1) ||
           (l > 0 && c < n-1 && s[l-1][c+1] == 1) ||
           (l < n-1 && c > 0 && s[l+1][c-1] == 1) ||
           (l < n-1 && c < n-1 && s[l+1][c+1] == 1)) {
           return 0;
       }
       return 1;
   }
   

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