基于回溯法的Peg Solitaire跳棋C语言求解程序异常排查

核心问题分析 #

程序无法终止且输出大量无效内容，根源在于以下几个关键错误：

1. move_is_valid函数的未定义行为与逻辑缺陷 #

• 函数未处理无合法移动的情况，无返回值会导致调用时得到随机值，触发错误移动。
• 判断中间棋子时用mtrx[i-1][j] !=0，但棋盘无效位置为-1，会把无效位置误判为可跳过的棋子，导致非法移动。
• 函数仅返回第一个检测到的合法方向，漏检其他可能的移动路径，导致部分解被遗漏。

2. 递归过程中不必要的棋盘打印 #

play函数每次进入递归都调用show，导致输出所有中间尝试的棋盘状态，而非仅正确的解路径。

3. 历史记录初始化与回溯逻辑问题 #

• 初始历史未保存初始棋盘状态，第一次撤销移动时会出错。
• move_pin直接修改原棋盘并添加历史，递归失败撤销后，后续循环可能重复处理同一错误状态。

4. 递归终止条件不完整 #

当没有任何合法移动但未达到目标状态时，程序未直接返回，会导致无意义的循环。

修正步骤与代码实现 #

1. 修复move_is_valid函数 #

• 明确判断中间棋子为1（有效棋子），而非!=0。
• 改为检测指定方向是否合法，确保每个方向都能被验证。
• 补充无合法方向时的返回值0。

2. 调整show的调用时机 #

仅在找到正确解时，回溯打印整个历史路径，而非每次递归都打印。

3. 初始化历史记录 #

在main函数中，将初始棋盘状态存入history[0]。

4. 完善递归逻辑 #

• 在play函数中，先遍历所有位置和方向尝试移动，避免漏检。
• 使用临时副本保存棋盘状态，回溯时直接恢复，避免历史记录混乱。

完整修正代码 #

#include <stdio.h>
#include <unistd.h>

#define MAX_LENGTH (1000)

int history[MAX_LENGTH][7][7];
int history_length = 0;

int verify(int mtrx[7][7]);
int move_is_valid(int mtrx[7][7], int i, int j, int direction);
int move_pin(int mtrx[7][7], int i, int j, int direction);
void add_to_history(int mtrx[7][7]);
void show(int mtrx[7][7]);
void print_solution();
int play(int mtrx[7][7]);

int main()
{
    int mtrx[7][7] = {
        { -1, -1, 1, 1, 1, -1, -1 },
        { -1, -1, 1, 1, 1, -1, -1 },
        { 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1 },
        { -1, -1, 1, 1, 1, -1, -1 },
        { -1, -1, 1, 1, 1, -1, -1 }
    };

    // 初始化历史记录，保存初始状态
    add_to_history(mtrx);
    show(mtrx);
    
    if (play(mtrx)) {
        printf("Jogo Concluido!!!\n");
        print_solution();
    } else {
        printf("Erro!!!\n");
    }

    return 0;
}

int verify(int mtrx[7][7])
{
    int total_pins = 0;
    for (int i = 0; i < 7; i++)
    {
        for (int j = 0; j < 7; j++)
        {
            if (mtrx[i][j] == 1)
            {
                total_pins++;
            }
        }
    }
    return (total_pins == 1 && mtrx[3][3] == 1) ? 1 : 0;
}

// 修改为检测指定方向是否合法
int move_is_valid(int mtrx[7][7], int i, int j, int direction) {
    if (i < 0 || i >=7 || j <0 || j >=7 || mtrx[i][j] != 1) {
        return 0; // 当前位置无棋子或无效
    }

    switch(direction) {
        case 1: // 向上
            return (i > 1 && mtrx[i-1][j] == 1 && mtrx[i-2][j] == 0) ? 1 : 0;
        case 2: // 向下
            return (i < 5 && mtrx[i+1][j] == 1 && mtrx[i+2][j] == 0) ? 1 : 0;
        case 3: // 向左
            return (j > 1 && mtrx[i][j-1] == 1 && mtrx[i][j-2] == 0) ? 1 : 0;
        case 4: // 向右
            return (j < 5 && mtrx[i][j+1] == 1 && mtrx[i][j+2] == 0) ? 1 : 0;
        default:
            return 0;
    }
}

int move_pin(int mtrx[7][7], int i, int j, int direction) {
    switch(direction) {
        case 1:
            mtrx[i][j] = 0;
            mtrx[i-1][j] = 0;
            mtrx[i-2][j] = 1;
            break;
        case 2:
            mtrx[i][j] = 0;
            mtrx[i+1][j] = 0;
            mtrx[i+2][j] = 1;
            break;
        case 3:
            mtrx[i][j] = 0;
            mtrx[i][j-1] = 0;
            mtrx[i][j-2] = 1;
            break;
        case 4:
            mtrx[i][j] = 0;
            mtrx[i][j+1] = 0;
            mtrx[i][j+2] = 1;
            break;
        default:
            return 0;
    }
    add_to_history(mtrx);
    return 1;
}

void add_to_history(int mtrx[7][7]) {
    if (history_length < MAX_LENGTH) {
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                history[history_length][i][j] = mtrx[i][j];
            }
        }
        history_length++;
    }
}

void show(int mtrx[7][7])
{
    for (int i = 0; i < 7; i++)
    {
        for (int j = 0; j < 7; j++)
        {
            if (mtrx[i][j] == -1)
                printf("#");
            else if (mtrx[i][j] == 0)
                printf(" ");
            else
                printf("o");
        }
        printf("\n");
    }
    printf("\n");
}

// 打印完整的解路径
void print_solution() {
    printf("Solucao completa:\n");
    for (int k = 0; k < history_length; k++) {
        show(history[k]);
        sleep(1);
    }
}

int play(int mtrx[7][7]) {
    if (verify(mtrx)) {
        return 1;
    }

    // 遍历所有位置和所有方向
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            for (int dir = 1; dir <=4; dir++) {
                if (move_is_valid(mtrx, i, j, dir)) {
                    // 保存当前状态的副本用于回溯
                    int temp[7][7];
                    for (int x=0; x<7; x++) {
                        for (int y=0; y<7; y++) {
                            temp[x][y] = mtrx[x][y];
                        }
                    }
                    move_pin(mtrx, i, j, dir);
                    if (play(mtrx) == 1) {
                        return 1;
                    }
                    // 回溯，恢复原状态
                    for (int x=0; x<7; x++) {
                        for (int y=0; y<7; y++) {
                            mtrx[x][y] = temp[x][y];
                        }
                    }
                    history_length--; // 移除错误的历史记录
                }
            }
        }
    }

    return 0;
}

修正说明 #

1. move_is_valid重构：改为检测指定方向是否合法，确保每个方向都能被正确验证，避免漏检路径。
2. 历史记录管理：初始化时保存初始棋盘，回溯时直接恢复临时副本，避免历史记录混乱。
3. 解路径打印：新增print_solution函数，仅在找到正确解时打印完整的移动路径，而非所有中间尝试。
4. 递归逻辑优化：遍历所有位置和方向，确保所有可能的移动都被尝试，同时通过临时副本回溯，避免棋盘状态污染。

内容的提问来源于stack exchange，提问作者Vitor Alves Pereira