15拼图游戏可解性判断代码错误排查求助

问题描述 #

开发15拼图游戏时，已在functions.c中实现了基于棋盘逆序数与空白格位置的可解性判断逻辑，但程序仍会生成无解棋盘（已通过在线求解工具验证）。尝试过多种计算方案后，可解棋盘生成概率较高但问题依旧存在，需要找出错误以确保仅生成可解配置，方便测试。

原始代码 #

functions.c #

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

#define ROWS 4
#define COLUMNS 4

// 打印棋盘
void printMatrix(int matrix[ROWS][COLUMNS]) {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLUMNS; j++) {
            if (matrix[i][j] == 16) {
                printf("   ");  // 16代表空白格
            } else {
                printf("%2d ", matrix[i][j]);
            }
        }
        printf("\n\n");
    }
}

// 计算棋盘逆序数
int countInversions(int matrix[ROWS][COLUMNS]) {
    int inversions = 0;
    int elements[ROWS * COLUMNS];

    // 将二维棋盘转为一维数组
    int k = 0;
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLUMNS; j++) {
            elements[k++] = matrix[i][j];
        }
    }

    // 统计逆序数
    for (int i = 0; i < ROWS * COLUMNS - 1; i++) {
        for (int j = i + 1; j < ROWS * COLUMNS; j++) {
            if (elements[j] && elements[i] && elements[i] > elements[j]) {
                inversions++;
            }
        }
    }

    return inversions;
}

// 判断初始配置是否可解
bool itsSolvableConfiguration(int matrix[ROWS][COLUMNS]) {
    int inversions = countInversions(matrix);

    // 查找空白格所在行
    int rowEmptySpace = -1;
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLUMNS; j++) {
            if (matrix[i][j] == 16) {
                rowEmptySpace = i;
                break;
            }
        }
        if (rowEmptySpace != -1) {
            break;
        }
    }

    // 基于空白格位置和逆序数判断可解性
    return (rowEmptySpace % 2 == 0 && inversions % 2 == 0) || (rowEmptySpace % 2 != 0 && inversions % 2 != 0);
}

// 判断输入字符是否有效
bool itsValidChar(char button) {
    return (button == 'Y' || button == 'y' || button == 'S' || button == 's');
}

main.c #

#include "functions.c"

int main(void) {
    int matrix[ROWS][COLUMNS];
    int numbers[16];
    int i, j, k, randomPivot;
    char answer;

    srand(getpid());

    printf("Puzzle 15\n\n");
    printf("CONTROLS:-Enter the number that is adjacent to the empty space to move it to the square.\n-Enter the key (Y) to restart or start the game.\n-Enter the key (S) to exit the game.");

    // 游戏启动控制 - 棋盘更新
    while (1) {
        printf("Load new game (Y to start / S to exit): ");
        scanf(" %c", &answer);
        for (int i = 0; i < 8; i++) {
                printf("\n");
        }

        if (!itsValidChar(answer)) {
            printf("\nInvalid key. Please choose a valid option.\n\n");
            continue;
        }

        if (answer == 'S' || answer == 's') {
            printf("\nThanks for playing!\n");
            break;
        }

        for (i = 0; i < 16; i++) {
            numbers[i] = i + 1;
        }

        // 使用Fisher-Yates算法随机打乱数字
        for (i = 16 - 1; i >= 0; i--) {
            j = rand() % (i + 1);
            randomPivot = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = randomPivot;
        }

        // 填充棋盘
        k = 0;
        for (i = 0; i < ROWS; i++) {
            for (j = 0; j < COLUMNS; j++) {
                matrix[i][j] = numbers[k++];
            }
        }

        // 检查初始配置是否可解
        if (!itsSolvableConfiguration(matrix)) {
            for (int i = 0; i < 15; i++) {
                printf("\n");
            }
            printf("The initial board configuration is not resolvable. Restart the game \nto obtain a valid configuration.");
            for (int i = 0; i < 12; i++) {
                printf("\n");
            }
        continue;
        }

        printf("Game started\n\n");

        for (int i = 0; i < 8; i++) {
                printf("\n");
        }

        // 打印初始棋盘
        printMatrix(matrix);
        break;
    }

    return 0;
}

错误分析与修正 #

1. 逆序数统计错误 #

countInversions函数中，错误地将代表空白格的16纳入了逆序数计算。15拼图的逆序数仅需统计数字1-15之间的逆序对，空白格应被排除。原代码中的elements[j] && elements[i]判断无效，因为16是非零值，会被当作有效元素参与计算，导致逆序数统计结果错误。

修正后的countInversions函数：

int countInversions(int matrix[ROWS][COLUMNS]) {
    int inversions = 0;
    int elements[ROWS * COLUMNS];

    int k = 0;
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLUMNS; j++) {
            elements[k++] = matrix[i][j];
        }
    }

    for (int i = 0; i < ROWS * COLUMNS - 1; i++) {
        for (int j = i + 1; j < ROWS * COLUMNS; j++) {
            // 排除空白格16，仅统计1-15的逆序对
            if (elements[i] != 16 && elements[j] != 16 && elements[i] > elements[j]) {
                inversions++;
            }
        }
    }

    return inversions;
}

2. 可解性规则逻辑颠倒 #

对于4×4的偶数阶棋盘，正确的可解规则为：

• 空白格从底部开始数处于奇数行时，逆序数需为偶数；
• 空白格从底部开始数处于偶数行时，逆序数需为奇数；

等价于使用0-based行号（从顶部开始计数）时，空白格所在行的奇偶性与逆序数的奇偶性不同。原代码的判断条件恰好相反，导致部分可解配置被误判为无解，部分无解配置被误判为可解。

修正后的itsSolvableConfiguration函数：

bool itsSolvableConfiguration(int matrix[ROWS][COLUMNS]) {
    int inversions = countInversions(matrix);

    int rowEmptySpace = -1;
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLUMNS; j++) {
            if (matrix[i][j] == 16) {
                rowEmptySpace = i;
                break;
            }
        }
        if (rowEmptySpace != -1) {
            break;
        }
    }

    // 修正可解条件：空白格0-based行号奇偶性与逆序数奇偶性不同
    return (rowEmptySpace % 2) != (inversions % 2);
}

验证效果 #

修正上述两处错误后，程序将严格按照15拼图的可解规则筛选初始配置，确保生成的棋盘均为可解状态，不会再出现无解配置。

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