如何判断一维数组形式的3x3八数码谜题是否可解？

问题分析 #

你当前的getInversion函数是针对二维数组编写的，逻辑完全不匹配一维数组，且未正确忽略空格（0）来计算逆序数；另外restart函数在生成不可解序列时没有触发重新生成，会导致游戏无法启动。

修正后的代码实现 #

1. 正确计算一维数组的逆序数 #

修改getInversion函数，遍历一维数组的所有元素，统计非0元素的逆序数（即对每个元素，统计它后面比它小的非0元素数量）：

// 计算一维数组的逆序数（忽略空格0）
function getInversion(arr) {
    let inversionCount = 0;
    // 遍历每个元素
    for (let i = 0; i < arr.length; i++) {
        const current = arr[i];
        // 跳过空格（0）
        if (current === 0) continue;
        // 统计当前元素后面比它小的非0元素数量
        for (let j = i + 1; j < arr.length; j++) {
            const next = arr[j];
            if (next !== 0 && next < current) {
                inversionCount++;
            }
        }
    }
    return inversionCount;
}

2. 确认可解性判断逻辑 #

对于3x3的八数码（奇数宽度棋盘），可解性规则为逆序数为偶数，你的isSolvable函数逻辑本身正确，配合修正后的getInversion即可正常工作：

// 判断序列是否可解
function isSolvable(arr) {
    return getInversion(arr) % 2 === 0;
}

3. 修复随机生成逻辑 #

原restart函数在生成不可解序列时没有重新生成，补充递归调用确保最终生成可解序列：

function restart() {
    // 生成随机序列
    const randomOrder = realOrder
        .map(value => ({ value, sort: Math.random() }))
        .sort((a, b) => a.sort - b.sort)
        .map(({ value }) => value);

    // 如果已经是解，重新生成
    if (verifyIfSolved(randomOrder)) {
        alert("Solved");
        restart();
        return;
    }

    // 如果可解则启动游戏，否则重新生成
    if (isSolvable(randomOrder)) {
        play(randomOrder);
    } else {
        restart();
    }
}

关键说明 #

• 逆序数计算必须忽略空格（0），因为空格是移动空位，不属于数字序列的逆序统计范畴
• 3x3棋盘为奇数宽度，无需额外考虑空格的行位置；若为偶数宽度棋盘（如4x4），则需要逆序数加上空格从底部开始数的行号，结果为偶数才判定可解

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