Проверка на наличие решения в игру 15

Question

Помогите сообразить формулу/алгоритм для проверки наличия решения в игре в 15, но в общем виде. То есть мне бы формулу для поля размером 3х3, 5х5 и тд. Вот что пишет википедия для 4х4:

пусть квадратик с числом i расположен до (если считать слева направо и сверху вниз) k квадратиков с числами меньшими i. Будем считать n[i] = k, то есть если после костяшки с i-м числом нет чисел, меньших i, то k=0. Также введем число e — номер ряда пустой клетки (считая с 1). Если сумма является нечётной, то решения головоломки не существует.

Для 4х4 сумма должна быть четной для решаемости игры, то (дальше мое предположение) для полей 3х3, 5х5 и тд сумма должна быть нечетной для решаемости. Ну и в моем решении 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]));
}

Answer 1

Как показал эксперимент, для нечетных досок этот способ не работает.

Критерий должен быть некоторым иным.

Сам эксперимент можно посмотреть здесь, или скомпилировать самому (писано "на коленке", быстро и неэффективно, просто лишь бы проверить...).

Но! У меня есть гипотеза, основанная на некоторых соображениях из моего незнания :) теории чисел. Не могу ее ни доказать, ни опровергнуть... но эксперименты вроде проходит... Что брать вместо e надо не номер строки пустышки, а номер строки пустышки, считая с 0, умноженный на (N-1)

Т.е. вот эта сумма

должна для разрешимости иметь ту же четность, что и само значение N — размер доски. Но терзают меня сомнения, и даже не очень смутные, что гипотеза неверна...

Если кто опровергнет или докажет — буду крайне признателен...

Update

Для предложенного

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 и нечетно. Итого, решения нет.

Вобщем, я гонял вычислительный эксперимент около получаса. Если правда то, что при перемене двух последних фишек мы получаем неразрешимую комбинацию, то за эти полчаса ни одного сбоя я не нашел. Конечно, вычислительный эксперимент — это не строгое математическое доказательство, но серьезная заявка на то, что это так и есть...

С кодом эксперимента можно ознакомиться здесь.

БЛОГ НА HUSL

Проверка на наличие решения в игру 15

Ответы (1 шт):