问题：C 语言回溯的 Peg Solitaire 解决方案

Question

我正在研究一种回溯解决方案来解决纸牌游戏。我的问题是它不断打印可能的解决方案并且永远不会停止。递归的基本情况是当中心只有一个引脚时程序必须停止；虽然没有，但它必须保持只打印正确的解决方案或正确的引脚移动。

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

#define MAX_LENGTH (1000)

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

int verify(int mtrx[7][7]);
int move_is_valid(int mtrx[7][7], int i, int j);
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]);
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 }
    };

    show(mtrx);
    
    if (play(mtrx))
        printf("Jogo Concluido!!!");
    else
        printf("Erro!!!");

    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)
{
    if (i < 0 || i >= 7 || j < 0 || j >= 7 || mtrx[i][j] == 0 || mtrx[i][j] == -1) {
        return 0; // invalid move
    }
    if (i > 1 && mtrx[i - 1][j] != 0 && mtrx[i - 2][j] == 0) {
        return 1; // valid upward move 
    }
    if (i < 7 - 2 && mtrx[i + 1][j] != 0 && mtrx[i + 2][j] == 0) {
        return 2; // valid downward move
    }
    if (j > 1 && mtrx[i][j - 1] != 0 && mtrx[i][j - 2] == 0) {
        return 3; // valid move to the left
    }
    if (j < 7 - 2 && mtrx[i][j + 1] != 0 && mtrx[i][j + 2] == 0) {
        return 4; // valid move to the right
    }
}

int move_pin(int mtrx[7][7], int i, int j, int direction) {
    
    if (direction == 1) {
        mtrx[i][j] = 0;
        mtrx[i - 1][j] = 0;
        mtrx[i - 2][j] = 1;
        add_to_history(mtrx);
        return 1;

    } else if (direction == 2) {
        mtrx[i][j] = 0;
        mtrx[i + 1][j] = 0;
        mtrx[i + 2][j] = 1;
        add_to_history(mtrx);
        return 1;

    } else if (direction == 3) {
        mtrx[i][j] = 0;
        mtrx[i][j - 1] = 0;
        mtrx[i][j - 2] = 1;
        add_to_history(mtrx);
        return 1;

    } else if (direction == 4) {
        mtrx[i][j] = 0;
        mtrx[i][j + 1] = 0;
        mtrx[i][j + 2] = 1;
        add_to_history(mtrx);
        return 1;
    }

    return 0;

}

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

int undo_move(int mtrx[7][7]) {
    if (history_length > 1) {
        history_length--;
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                mtrx[i][j] = history[history_length][i][j];
            }
        }
    }
    return 0;
}

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");
}

int play(int mtrx[7][7]) {

    //printf("history_length: %d\n", history_length);
    
    if (verify(mtrx)) {
        return 1;
    } else {
        show(mtrx);
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                int direction = move_is_valid(mtrx, i, j);
                if (direction != 0) {
                    move_pin(mtrx, i, j, direction);
                    sleep(1);
                    if (play(mtrx) == 1) {
                        return 1;
                    } else undo_move(mtrx);
                }
            }
        }
    }
    return 0;
}

Answer 1

缺少退货

节省时间，启用所有编译器警告。当所有

move_pin()

都不为真时，您期望从

if()

返回什么值？

修复

move_pin()

、删除

sleep()

、添加一些性能改进（例如将

if (mtrx[3][3] != 1) return false;

添加到

verify()

的开头）导致

Erro!!!

。 所以代码可能仍然存在其他逻辑错误。