帮我想一个公式/算法来检查解决方案的存在игре в 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]));
}
