Пятнашки в общем виде решить - не девяток яиц купить...
Для классических "пятнашек" с конца 19 века известно, что половина начальных расстановок сводится к нерешаемой конфигурации
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14
и существует математический критерий определения сходимости начальной конфигурации, который можно считать и по "Вики" и в нескольких других вариациях, в частности, проверяя чётность количества случаев, для которых ni > nj, i,j = 1, 2, ..., 15, где ni, nj - очередная пара чисел в игровом поле при построчном чтении матрицы расположения "костяшек".
Как обстоит дело с обобщением головоломки на поле размерностью n×n или n×m?
После ряда бредовых рассуждений мне казалось, что такие "пятнашки" разрешимы, если значение A + B + N чётно, где A - количество инверсий (пар плиток, для которых плитка с большим номером идёт перед плиткой с меньшим), В - номер строки, в которой находится пустое поле (начиная с единицы), N - размерность поля. Но жизнь эту формулу не подтвердила даже для размерности 3×3, всё равно получаются
1 2 3 4 5 6 8 7
или
1 2 3 4 6 5 7 8
которые решить нельзя.
Разумеется, допустимую расстановку всегда можно сгенерировать "обратным алгоритмом", то есть, делая случайные допустимые ходы из начальной позиции, но хотелось принципиально этого не делать. Так что вот несовершенные пятнашки 3 на 3, точней "Девяток", целевой считается только расстановка
1 2 3 4 5 6 7 8
, скрипт в работе и полный исходник файла .html приведены ниже.
Критерий допустимости позиции в методе random_block оставлен один из "сумасшедших", каким-либо чётким математическим выкладкам он не соответствует.
Для управления есть 2 кнопки слева от игрового поля, ход делается кликом по полю, с которого нужно передвинуть фигурку. Яйцо - это совершенство восьмёрки, в рамках дальнейшего развития импортозамещённой метрологии.
А вы смогли вывести точную формулу для определения разрешимости начальной расстановки в обобщённых "пятнашках"?
Время
Старт
Заново
<!DOCTYPE html>
<html lang="ru">
<head>
<meta charset="UTF-8">
<title>Девяток</title>
<style>
#container{
position:relative;
width: 600px;
height: 460px;
margin: 0 auto;
margin-top: 100px;
border-radius: 2px;
}
#game{
position: absolute;
width: 450px;
height: 450px;
border-radius:5px;
display: inline-block;
background-color: #3f3f3f;
box-shadow: 5px 5px 40px #3f3f3f;
}
#game div{
position: absolute;
width: 148px;
height: 148px;
border: 2px solid #244;
border-radius: 10px;
background-color: #689;
color: #fff;
text-align: center;
font-family: monospace;
font-size: 9em;
line-height: 150px;
cursor: pointer;
transition: 0.3s;
}
#game div:hover{
color: #9cd;
}
#control{
width: 150px;
height: 450px;
display: inline-block;
float: left;
}
#control h3{
height: 30px;
font-size:1.5em;
font-family: monospace;
margin-top: 16px;
}
#start9, #reset9 {
display: inline-block;
width: 100px;
height: 28px;
background-color: #689;
border-radius: 10px;
box-shadow: 2px 2px 5px #689;
color: white;
text-align: center;
padding-top: 5px;
cursor: pointer;
}
#timeText, #timer9, #info9 {
display: inline-block;
width: 100px;
height: 28px;
background-color: #fff;
text-align: center;
}
#block1 { left: 0px; }
#block2 { left: 150px; }
#block3 { left: 300px; }
#block4 { top: 150px; }
#block5 { top: 150px; left: 150px; }
#block6 { top: 150px; left: 300px; }
#block7 { top: 300px; }
#block8 { left: 150px; top: 300px; }
</style>
<script>
let time = 0;
let set_timer;
let pause_flag = true;
let block = new Array(10);
for (let i = 1; i < 9; i++) block[i] = i;
block[9] = 0;
let block_direction = [ //на какие блоки можно перемещать
[0],
[2,4], [1,3,5], [2,6],
[1,5,7], [2,4,6,8], [3,5,9],
[4,8], [5,7,9], [6,8]
];
let block_position = [ //позиции блоков (x,y)
[0],
[0,0], [150,0], [300,0],
[0,150], [150,150], [300,150],
[0,300], [150,300], [300,300]
];
function move9 (id) { //основная функция
if (!pause_flag) {
document.getElementById("info9").innerHTML = "";
let i = 1;
for (; i < 10; i++) { //найти блок на доске
if (block[i] == id) break;
}
let target_dir = move_dir(i);
if (target_dir != 0) {
block[i] = 0;
block[target_dir] = id;
//новое положение блока:
document.getElementById("block"+id).style.left = block_position[target_dir][0]+"px";
document.getElementById("block"+id).style.top = block_position[target_dir][1]+"px";
}
}
else {
document.getElementById("info9").innerHTML = "Нажмите \"Старт\"";
return;
}
//проверка на окончание:
let finish_flag = true;
for (let k=1; k<9; k++){
if (block[k] != k){
finish_flag = false;
break;
}
}
if (finish_flag == true){
document.getElementById("info9").innerHTML = "Вы выиграли";
document.getElementById("start9").innerHTML = "...";
clearInterval (set_timer);
}
function move_dir(curr_loc){
let j = 0;
let canMove = false;
for (; j<block_direction[curr_loc].length; j++) {
//занят ли блок в нужном направлении
if (block[block_direction[curr_loc][j]] == 0) {
canMove = true;
break;
}
}
if (canMove == true) return block_direction[curr_loc][j];
else return 0;
}
} //move9
function start9() { //кнопка "Старт"
if (document.getElementById("start9").innerHTML == "...") {
document.getElementById("info9").innerHTML = "Нажмите \"Заново\"";
return;
}
document.getElementById("info9").innerHTML = "";
if (pause_flag) { //Если в игре
document.getElementById("start9").innerHTML = "Пауза";
pause_flag = false;
set_timer = setInterval(function() { //Повторяем это раз в секунду
time++;
let min = parseInt(time/60);
let sec = time%60;
document.getElementById("timer9").innerHTML =
String(min).padStart(2, '0') + ":" + String(sec).padStart(2, '0');
},1000);
}
else { //Если на паузе
document.getElementById("start9").innerHTML = "Старт";
pause_flag = true;
clearInterval (set_timer);
}
}
function reset9() { //кнопка "Заново"
time = 0;
document.getElementById("timer9").innerHTML = "";
document.getElementById("info9").innerHTML = "";
random_block();
document.getElementById("start9").innerHTML = "Старт";
pause_flag = true;
clearInterval (set_timer);
start9();
function random_block() { //Генерация игры
let shuffle_array = new Array(10);
let solvable = false;
let inversion = 0;
while (!solvable) {
shuffle_array = shuffle(block);
inversion = 0;
for (let i = 1; i <shuffle_array.length; i++){
for(let j = 2; j < shuffle_array.length; j++){
if (shuffle_array[i] != 0 && shuffle_array[j] != 0) {
if (shuffle_array[i] > shuffle_array[j]) {
//console.log('i=' + shuffle_array[i] + ' j=' +shuffle_array[j]);
inversion++;
}
}
}
}
if (inversion%2 == 0) solvable = true;
}
//console.log('inversion=' + inversion);
//console.log(shuffle_array);
for (let i=9; i > 0; i--){
if (block[i] != 0) {
document.getElementById("block"+shuffle_array[i]).style.left=block_position[i][0]+"px";
document.getElementById("block"+shuffle_array[i]).style.top=block_position[i][1]+"px";
}
}
}
function shuffle (array) { //Собственное перемешивание массива
for (let i = 9; i > 0; i--) {
let j = Math.floor(Math.random() * (i - 1) + 1);
let temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
} //reset9
</script>
</head>
<body>
<div id="container">
<div id="control">
<p>
<h3 id="timeText">Время</h3>
<h3 id="timer9"></h3>
</p>
<p>
<h3 id="start9" onclick="start9()">Старт</h3>
<h3 id="reset9" onclick="reset9()">Заново</h3>
<h3 id="info9"></h3>
</p>
</div>
<div id="game">
<!-- отрисовка доски начальная -->
<div id="block1" onclick="move9(1)">1</div>
<div id="block2" onclick="move9(2)">2</div>
<div id="block3" onclick="move9(3)">3</div>
<div id="block4" onclick="move9(4)">4</div>
<div id="block5" onclick="move9(5)">5</div>
<div id="block6" onclick="move9(6)">6</div>
<div id="block7" onclick="move9(7)">7</div>
<div id="block8" onclick="move9(8)">🥚</div>
</div>
</div>
<script>
window.addEventListener ('load', function (e) {
reset9();
}, false);
</script>
<noscript>
<p>Включите Javascript в браузере для работы приложения.</p>
</noscript>
</body>
</html>
P.S. Вроде бы, естественный вариант функции, показанный ниже, тоже к успеху не приводит:
function random_block() { //Генерация игры
let shuffle_array = new Array(10);
let solvable = false;
let inversion = 0;
while (!solvable) {
shuffle_array = shuffle(block);
inversion = 0;
for (let i=1; i<10; i++) {
if (shuffle_array[i] == 0) inversion += 1 + Math.floor((i-1) / 3);
else {
for (let j=i+1; j<10; j++)
if (shuffle_array[j] < shuffle_array[i]) inversion++;
}
}
if (inversion%2 == 0) solvable = true;
}
console.log('inversion=' + inversion);
console.log(shuffle_array);
for (let i=9; i > 0; i--){
if (block[i] != 0) {
document.getElementById("block"+shuffle_array[i]).style.left=block_position[i][0]+"px";
document.getElementById("block"+shuffle_array[i]).style.top=block_position[i][1]+"px";
}
}
}
05.06.2023, 14:07 [260 просмотров]