3×3网格哈密顿路径计数回溯代码异常：预期输出2实际得1

核心bug分析 #

你的代码存在两个关键问题，导致3×3网格下仅输出1而非预期的2：

1. 移动方向逻辑完全混淆
   你混淆了行（x）和列（y）对应的移动方向：原代码把「左右移动」对应到行号x的变化，「上下移动」对应到列号y的变化，这与实际坐标体系的移动逻辑相反。正确逻辑应为：左右移动改变列号y，上下移动改变行号x。

2. 回溯时未重置终点格子状态
   当checked == num（访问完所有格子）时，函数直接return，没有执行grid[x][y] = false，导致该格子的访问状态未被回溯，后续递归分支无法再次访问该格子，从而漏掉一条有效路径。

修复后的代码 #

#include <iostream>
#include <vector>
using namespace std;

long ans = 0;
const int n = 3;
int num = n * n;
bool grid[n][n];

void search(int x, int y, int checked) {
    grid[x][y] = true;
    cout << "Searching in " << x << " " << y << " in " << checked << "\n";

    if (checked == num) {
        cout << "in IF!\n";
        if (x == n - 1 && y == n - 1){
            ans++;
            cout << "ans++!\n";
        }
        // 修复：重置当前格子状态再返回
        grid[x][y] = false;
        return;
    }   
    else {
        // 左：列号y减小
        if (y > 0 && !grid[x][y - 1]) {
            search(x, y - 1, checked + 1);
        }

        // 右：列号y增大
        if (y < n - 1 && !grid[x][y + 1]) {
            search(x, y + 1, checked + 1);
        }

        // 上：行号x减小
        if (x > 0 && !grid[x - 1][y]) {
            search(x - 1, y, checked + 1);
        }

        // 下：行号x增大
        if (x < n - 1 && !grid[x + 1][y]) {
            search(x + 1, y, checked + 1);
        }
    }
    grid[x][y] = false;
    return;
}

int main() {
    search(0, 0, 1);
    cout << ans;
    return 0;
}

额外优化说明 #

• 去掉了手动的checked++和checked--，直接在递归调用时传递checked + 1，利用参数值传递的特性，避免手动修改变量出错。
• 修正所有移动方向的判断逻辑，确保坐标变化符合实际行/列移动规则。

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