递归回溯实现骑士巡游问题代码崩溃求助

核心崩溃原因：数组越界访问 #

你的safe函数判断顺序错误——先访问了board[i][j]，再检查i和j是否在0-7的合法范围内。当si + movei[i]或sj + movej[i]超出棋盘边界（比如-1或8）时，访问board[i][j]会触发非法内存访问，直接导致程序崩溃。

修复后的safe函数应先判断索引合法性，再检查棋盘值：

_Bool safe(int **board, int i, int j)
{
    // 先确认索引在合法范围，再检查位置是否未被访问
    if (i >= 0 && i < 8 && j >= 0 && j < 8 && board[i][j] == -1)
    {
        return 1;
    }
    return 0;
}

第二个逻辑错误：回溯时未重置count #

当前代码中，当某条路径走不通回溯时，仅将棋盘位置设回-1，但未将全局变量count递减。这会导致count持续递增，后续递归中count == 64的判断逻辑失效，甚至可能出现count超过64后无法终止递归的情况。

修复solve函数的回溯逻辑：

_Bool solve(int **board, int si, int sj)
{
    if (count == 64)
    {
        boardprinter(board);
        return 1;
    }
    int i=0;
    while(i<8)
    {  
        if (safe(board, (si + movei[i]), (sj + movej[i])))
        {
            int ni = si + movei[i];
            int nj = sj + movej[i];
            board[ni][nj] = count++;
            if (solve(board, ni, nj))
            {   
                return 1;
            }
            else
            {   
                board[ni][nj] = -1;
                count--; // 回溯时将count恢复至之前的值
            }
        }
        i++;
    }
    return 0;
}

额外优化建议 #

• 避免使用全局变量count，可将其作为solve函数的指针参数传递，减少全局状态带来的调试复杂度。
• 朴素回溯在部分起始位置会陷入极深递归，可尝试Warnsdorff算法（优先访问后续可选步数最少的位置），大幅提升求解效率。

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