Hitori矩阵回溯算法失效问题排查求助

算力阿峰

2026-6-24

Hitori回溯算法问题排查

我写的Hitori矩阵回溯代码没法正常回溯，给定的5阶矩阵处理后还是有重复数字。Hitori（反向数独）的规则是：

未被消除的单元格，数字在所在行、列中不能重复
所有未被消除的单元格必须连通，不能有孤立单元格
被标记为消除的单元格（marcaj=1）不能相邻

我不追求算法效率，只想搞懂回溯逻辑，但代码肯定哪里错了，求帮忙找问题。

我的代码如下：

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

#define DIM 5

int nr=0, marcaj[DIM][DIM] = {0}, matrice[DIM][DIM] = {
    {5, 1, 2, 3, 2},
    {5, 3, 2, 2, 4},
    {5, 2, 4, 5, 4},
    {3, 4, 5, 1, 2},
    {3, 5, 5, 4, 2},
    };

bool solutionFound = false;

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

void dfs(bool visited[DIM][DIM], int row, int col) {
    int rowOffset[] = {-1, 0, 1, 0};
    int colOffset[] = {0, 1, 0, -1};

    visited[row][col] = true;

    for (int i = 0; i < 4; i++) {
        int newRow = row + rowOffset[i];
        int newCol = col + colOffset[i];

        if (newRow >= 0 && newRow < DIM && newCol >= 0 && newCol < DIM &&
            !visited[newRow][newCol] && marcaj[newRow][newCol] == 0) {
            dfs(visited, newRow, newCol);
        }
    }
}

bool areAllzerosConnected() {
    bool visited[DIM][DIM] = {false};
    bool startFound = false;

    for (int i = 0; i < DIM && !startFound; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 0) {
                dfs(visited, i, j);
                startFound = true;
                break;
            }
        }
    }

    if (!startFound) return true;

    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 0 && !visited[i][j]) {
                return false;
            }
        }
    }

    return true;
}

bool duplicat(int lin, int col) {
    for (int i = 0; i < DIM; i++) {
        if (marcaj[lin][i] == 0 && i != col && matrice[lin][i] == matrice[lin][col]) {
            return true;
        }
        if (marcaj[i][col] == 0 && i != lin && matrice[i][col] == matrice[lin][col]) {
            return true;
        }
    }
    return false;
}

bool areAdjacentMarkedCells() {
    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 1) {
                if ((i > 0 && marcaj[i - 1][j] == 1) ||
                    (i < DIM - 1 && marcaj[i + 1][j] == 1) ||
                    (j > 0 && marcaj[i][j - 1] == 1) ||
                    (j < DIM - 1 && marcaj[i][j + 1] == 1)) {
                    return true;
                }
            }
        }
    }
    return false;
}

void bkt(int lin, int col) {
    if (solutionFound) return;

    if (lin == DIM) {
            printMatrice();
            printf("Numar mutari:%d\n",nr);
            solutionFound = true;
            return;
    }

    if (col == DIM) {
        bkt(lin + 1, 0);
        return;
    }

    if (duplicat(lin, col)) {
        nr++;
        marcaj[lin][col] = 1;
        if (areAllzerosConnected() && !areAdjacentMarkedCells()) {
            bkt(lin, col + 1);
        }

    }
    marcaj[lin][col] = 0;
    bkt(lin, col + 1);
}

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

问题分析

回溯分支不完整：原代码只在当前单元格存在重复时尝试标记为1，否则直接设为0继续。但Hitori中，即使当前单元格暂时没重复，后续单元格的重复可能需要标记当前单元格来解决，必须同时处理标记为1和不标记为0两个分支，且每个分支都要做合法性检查。
状态回溯不彻底：标记单元格为1后，如果递归失败，没有将marcaj[lin][col]改回0，也没有将计数nr减回去，导致后续状态混乱。
校验时机错误：原代码在处理每个单元格时就校验连通性和相邻标记，会过早排除可行解——中间步骤中未标记单元格可能暂时不连通，但后续标记其他单元格后会恢复连通。这些校验应该放在所有单元格处理完成后再做。
duplicat函数逻辑偏差：该函数判断的是当前单元格是否存在重复，但我们需要的是：如果不标记当前单元格，该行和列中是否还有其他未标记的相同数字，以此确保不违反规则1。

修复后的代码

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

#define DIM 5

int nr = 0, marcaj[DIM][DIM] = {0}, matrice[DIM][DIM] = {
    {5, 1, 2, 3, 2},
    {5, 3, 2, 2, 4},
    {5, 2, 4, 5, 4},
    {3, 4, 5, 1, 2},
    {3, 5, 5, 4, 2},
};

bool solutionFound = false;

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

void dfs(bool visited[DIM][DIM], int row, int col) {
    int rowOffset[] = {-1, 0, 1, 0};
    int colOffset[] = {0, 1, 0, -1};

    visited[row][col] = true;

    for (int i = 0; i < 4; i++) {
        int newRow = row + rowOffset[i];
        int newCol = col + colOffset[i];

        if (newRow >= 0 && newRow < DIM && newCol >= 0 && newCol < DIM &&
            !visited[newRow][newCol] && marcaj[newRow][newCol] == 0) {
            dfs(visited, newRow, newCol);
        }
    }
}

bool areAllzerosConnected() {
    bool visited[DIM][DIM] = {false};
    bool startFound = false;

    for (int i = 0; i < DIM && !startFound; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 0) {
                dfs(visited, i, j);
                startFound = true;
                break;
            }
        }
    }

    if (!startFound) return true;

    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 0 && !visited[i][j]) {
                return false;
            }
        }
    }

    return true;
}

// 检查：如果不标记(lin,col)，该行和列是否有重复的未标记数字
bool hasDuplicateIfNotMarked(int lin, int col) {
    // 检查行
    for (int j = 0; j < DIM; j++) {
        if (j != col && marcaj[lin][j] == 0 && matrice[lin][j] == matrice[lin][col]) {
            return true;
        }
    }
    // 检查列
    for (int i = 0; i < DIM; i++) {
        if (i != lin && marcaj[i][col] == 0 && matrice[i][col] == matrice[lin][col]) {
            return true;
        }
    }
    return false;
}

// 检查当前单元格标记为1后，是否与相邻单元格冲突
bool canMark(int lin, int col) {
    // 上下左右不能有已标记的单元格
    if ((lin > 0 && marcaj[lin-1][col] == 1) ||
        (lin < DIM-1 && marcaj[lin+1][col] == 1) ||
        (col > 0 && marcaj[lin][col-1] == 1) ||
        (col < DIM-1 && marcaj[lin][col+1] == 1)) {
        return false;
    }
    return true;
}

// 最终校验所有规则
bool isValidSolution() {
    // 规则1：所有未标记单元格的行、列无重复
    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 0 && hasDuplicateIfNotMarked(i, j)) {
                return false;
            }
        }
    }
    // 规则2：未标记单元格连通
    if (!areAllzerosConnected()) {
        return false;
    }
    // 规则3：标记单元格不相邻（其实标记时已经检查，这里做最终确认）
    for (int i = 0; i < DIM; i++) {
        for (int j = 0; j < DIM; j++) {
            if (marcaj[i][j] == 1) {
                if ((i > 0 && marcaj[i-1][j] == 1) ||
                    (i < DIM-1 && marcaj[i+1][j] == 1) ||
                    (j > 0 && marcaj[i][j-1] == 1) ||
                    (j < DIM-1 && marcaj[i][j+1] == 1)) {
                    return false;
                }
            }
        }
    }
    return true;
}

void bkt(int lin, int col) {
    if (solutionFound) return;

    // 所有单元格处理完成，校验是否为合法解
    if (lin == DIM) {
        if (isValidSolution()) {
            printMatrice();
            printf("Numar mutari:%d\n", nr);
            solutionFound = true;
        }
        return;
    }

    if (col == DIM) {
        bkt(lin + 1, 0);
        return;
    }

    // 分支1：标记当前单元格为1（消除）
    if (canMark(lin, col)) {
        marcaj[lin][col] = 1;
        nr++;
        bkt(lin, col + 1);
        // 回溯撤销状态
        nr--;
        marcaj[lin][col] = 0;
    }

    // 分支2：不标记当前单元格为0（保留）
    // 只有当不标记时，当前行和列没有重复的未标记数字，才可以走这个分支
    if (!hasDuplicateIfNotMarked(lin, col)) {
        bkt(lin, col + 1);
    }
}

int main() {
    bkt(0, 0);
    if (!solutionFound) {
        printf("Nu exista solutie!\n");
    }
    return 0;
}

关键修改说明

补全回溯分支：同时处理标记和不标记两个分支，每个分支都做合法性检查，递归结束后撤销状态（恢复marcaj和nr）。
调整校验时机：将完整的规则校验移到所有单元格处理完成后（lin == DIM时），避免过早排除可行解。
拆分校验函数：新增canMark函数检查标记是否违反相邻规则，hasDuplicateIfNotMarked检查不标记是否违反重复规则，逻辑更清晰。
完善状态回溯：标记分支递归后，必须将marcaj改回0，nr减1，确保后续递归状态正确。

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

Hitori矩阵回溯算法失效问题排查求助

问题分析 #

修复后的代码 #

关键修改说明 #

问题分析

修复后的代码

关键修改说明