主页 / 问题 / 1354443
Accepted
Kto To
Asked:2022-04-27 07:18:45 +0000 UTC2022-04-27 07:18:45 +0000 UTC

在游戏 15 中检查解决方案

  • 772

帮我想一个公式/算法来检查解决方案的存在игре в 15，但以一般的方式。也就是说，我将有一个大小为 3x3、5x5 等的字段的公式。以下是Wikipedia为 4x4 写的内容：

让带有数字的正方形位于数字小于的正方形i之前（如果您从左到右和从上到下计数）。我们将考虑，即如果在第 - 个数字的关节之后没有小于 的数字，则。我们还引入了一个数字——空单元格的行号（从 1 开始计数）。如果总和 是奇数，那么这个谜题就没有解决方案。kin[i] = kiik=0e公式

对于 4x4，对于游戏的可解性，总和必须是偶数，然后（以下我的猜测）对于字段 3x3、5x5 等，对于可解性，总和必须是奇数。好吧，在我的决定中0-我认为是一个空牢房。

// Проверяет игру на наличие решения.
function checkArrayForGame(arrayOrig) {
    let size = Math.sqrt(arrayOrig.length);
    let indZero = arrayOrig.indexOf(0);
    if (size !== parseInt(size) || indZero === -1) {
        console.log('Не верный формат аргументов');
        return false;
    }
    let N = parseInt(indZero / size) + 1; // на какой строке пустая клетка начиная с 1

    let array = arrayOrig.slice(); // make copy array;

    array.splice(indZero, 1); // удалил нолик из массива.
    for(let i = 0; i < array.length - 1; ++i) {
        for (let j = i + 1; j < array.length; ++j) {
            N += array[i] > array[j];
        }
    }
    // console.log(size, N)
    return ((size % 2) && (N % 2))
            || (!(size % 2) && !(N % 2));
}

let testDataTrue = [
        [1, 2, 3, 4, 5, 6, 7, 8, 0],
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
    ];
let testDataFalse = [
        [1, 2, 3, 4, 5, 6, 8, 7, 0],
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 0],
        [1, 7, 4, 6, 3, 0, 8, 2, 5] // для этого примера не работает =(
    ];
console.log('Must be True');
for (let i = 0; i < testDataTrue.length; ++i) {
    console.log('*', checkArrayForGame(testDataTrue[i]));
}
console.log('Must be False');
for (let i = 0; i < testDataFalse.length; ++i) {
    console.log('*', checkArrayForGame(testDataFalse[i]));
}

感谢@Harry 的回答。我试图根据你的公式来实现哈利公式：。结果是这段代码：

// Проверяет игру на наличие решения.
function checkArrayForGame(arrayOrig) {
    let size = Math.sqrt(arrayOrig.length);
    let indZero = arrayOrig.indexOf(0);
    if (size !== parseInt(size) || indZero === -1) {
        console.log('Не верный формат аргументов');
        return false;
    }
    let e = parseInt(indZero / size); // на какой строке пустая клетка начиная с 0

    let rightPart = (size - 1) * (e - 1) + 1;

    let array = arrayOrig.slice(); // make copy array;
    array.splice(indZero, 1); // удалил нолик из массива.

    let summ = 0;

    for (let i = 0; i < array.length - 1; ++i) {
        for (let j = i; j < array.length; ++j) {
            summ += array[i] > array[j];
        }
    }
    let result = summ + rightPart;
    // console.log(size, e, rightPart, summ, result);
    //return ((size % 2) && (result % 2))
    //        || (!(size % 2) && !(result % 2));
    return result % 2;
}
let testDataTrue = [
        [1, 2, 3, 4, 5, 6, 7, 8, 0],
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
    ];
let testDataFalse = [
        [1, 2, 3, 4, 5, 6, 8, 7, 0],
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 0],
        [1, 7, 4, 6, 3, 0, 8, 2, 5] // для этого примера не работает =(
    ];
console.log('Must be True');
for (let i = 0; i < testDataTrue.length; ++i) {
    console.log('*', checkArrayForGame(testDataTrue[i]));
}
console.log('Must be False');
for (let i = 0; i < testDataFalse.length; ++i) {
    console.log('*', checkArrayForGame(testDataFalse[i]));
}

javascript

1 个回答

  1. Best Answer

    如实验所示，这种方法不适用于奇数板。

    标准必须有所不同。

    实验本身可以在这里查看，或者自己编译（写在“膝盖上”，快速而低效，只是为了检查......）。

    但！我有一个基于我对数论的无知的一些考虑的假设:)。我既无法证明也无法反驳……但实验似乎正在进行中……应该取而代之e的不是假人的行号，而是假人的行号，从0开始，乘以（ N-1)

    那些。这是金额

    在此处输入图像描述

    为了可解决性，必须与N本身的值具有相同的奇偶性，即棋盘的大小。但是怀疑折磨着我，甚至不是很模糊的怀疑，假设是错误的......

    如果有人反驳或证明 - 我将非常感激......

    更新

    对于提议的

    1 7 4 6 3 0 8 2 5

    “虚拟”在哪里0，我们有：

    1 - 0, 2 - 0, 3 - 1, 4 - 2, 5 - 0, 6 - 3, 7 - 5, 8 - 2的反转，总数为13。空在第2行，表示13 + 2 *1+1 = 16 是偶数。N 等于 3 并且是奇数。总之，没有解决办法。

    一般来说，我开了一个半小时左右的计算实验。如果是真的，当我们更换最后两个芯片时，我们得到了一个无法解决的组合，那么在这半个小时里我没有发现一个故障。当然，计算实验不是严格的数学证明，而是严肃地声称它是……

    实验代码可以在这里找到。

    • 3

相关问题