Як я можу знати, що моя гра-головоломка завжди можлива?

Я зробив своєрідну гра-головоломку, де метою є позбутися всіх білих плиток. Ви можете спробувати його в кінці питання.

Кожен раз, дошка випадково генерується з білими плитками у випадкових місцях на 5 * 5 сітки. Ви можете натиснути будь-яку плитку на цій сітці, і вона буде перемикатися колір його і всі плитки, торкаючись його з боків. Моя дилема полягає в тому, що я не знаю, чи стане вона неможливим. Який найкращий спосіб перевірити такі речі?

<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false"> <div class="snippet-code">

function newgame() {
 moves = 0;
    document.getElementById("moves").innerHTML = "Moves: "+moves;

  for (var i = 0; i < 25; i++) {
   if (Math.random() >= 0.5) {
$(document.getElementsByClassName('block')[i]).toggleClass("b1 b2")
   }
}
}
newgame();
function toggle(a,b) {  
  moves += 1;
  document.getElementById("moves").innerHTML = "Moves: "+moves;
$(document.getElementsByClassName('block')[a+(b*5)]).toggleClass("b1 b2");

if (a<4) {$(document.getElementsByClassName('block')[(a+1)+(b*5)]).toggleClass("b1 b2")}
  
  
if (a>0) {$(document.getElementsByClassName('block')[(a-1)+(b*5)]).toggleClass("b1 b2")}
  
  
if (b<4) {$(document.getElementsByClassName('block')[a+((b+1)*5)]).toggleClass("b1 b2")}
  
if (b>0) {$(document.getElementsByClassName('block')[a+((b-1)*5)]).toggleClass("b1 b2")}
}
body {
  background-color: #000000;
}

.game {
  float: left;
  background-color: #000000;
  width: 300px;
  height: 300px;
  overflow: hidden;
  overflow-x: hidden;
  user-select: none;
  display: inline-block;
}

.container {
  border-color: #ffffff;
  border-width: 5px;
  border-style: solid;
  border-radius: 5px;
  width: 600px;
  height: 300px;
  text-align: center;
}

.side {
  float: left;
  background-color: #000000;
  width: 300px;
  height: 300px;
  overflow: hidden;
  overflow-x: hidden;
  user-select: none;
  display: inline-block;
}

.block {
  transition: background-color 0.2s;
  float: left;
}

.b1:hover {
  background-color: #444444;
  cursor: pointer;
}

.b2:hover {
  background-color: #bbbbbb;
  cursor: pointer;
}

.row {
  width: 300px;
  overflow: auto;
  overflow-x: hidden;
}

.b1 {
  display: inline-block;
  height: 50px;
  width: 50px;
  background-color: #000000;
  border-color: #000000;
  border-width: 5px;
  border-style: solid;
}




.b2 {
  display: inline-block;
  height: 50px;
  width: 50px;
  background-color: #ffffff;
  border-color: #000000;
  border-width: 5px;
  border-style: solid;
}



.title {
  width: 200px;
  height: 50px;
  color: #ffffff;
  font-size: 55px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
}

.button {
  cursor: pointer;
  width: 200px;
  height: 50px;
  background-color: #000000;
  border-color: #ffffff;
  border-style: solid;
  border-width: 5px;
  color: #ffffff;
  font-size: 25px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
  border-radius: 5px;
  transition: background-color 0.3s, color 0.3s;
}

.button:hover {
  background-color: #ffffff;
  color: #000000;
}

.sidetable {
  padding: 30px 0px;
  height: 200px;
}


#moves {
  width: 200px;
  height: 50px;
  color: #aaaaaa;
  font-size: 30px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  vertical-align: middle;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div class="container"> <div class="game"><div class="row"><div onclick="toggle(0,0);" class="block b1"></div><div onclick="toggle(1,0);" class="block b1"></div><div onclick="toggle(2,0);" class="block b1"></div><div onclick="toggle(3,0);" class="block b1"></div><div onclick="toggle(4,0);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,1);" class="block b1"></div><div onclick="toggle(1,1);" class="block b1"></div><div onclick="toggle(2,1);" class="block b1"></div><div onclick="toggle(3,1);" class="block b1"></div><div onclick="toggle(4,1);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,2);" class="block b1"></div><div onclick="toggle(1,2);" class="block b1"></div><div onclick="toggle(2,2);" class="block b1"></div><div onclick="toggle(3,2);" class="block b1"></div><div onclick="toggle(4,2);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,3);" class="block b1"></div><div onclick="toggle(1,3);" class="block b1"></div><div onclick="toggle(2,3);" class="block b1"></div><div onclick="toggle(3,3);" class="block b1"></div><div onclick="toggle(4,3);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,4);" class="block b1"></div><div onclick="toggle(1,4);" class="block b1"></div><div onclick="toggle(2,4);" class="block b1"></div><div onclick="toggle(3,4);" class="block b1"></div><div onclick="toggle(4,4);" class="block b1"></div></div></div> <div class="side">
<div class="title">Tiles</div>
<div class="button" onclick="newgame()">New Game</div>

<div id="moves">Moves: 0</div>
</div> </div>
 
</div> </div>

68
Ви повинні дійсно змінити прийняту відповідь. Роберт дає вам математичний спосіб генерування випадкової сітки І негайно перевіряє її можливість.
додано Автор Johannes Setiabudi, джерело
Якщо ви зацікавлені в подібних головоломках, зверніться до . Крім цього типу (так званий Flip там), ви можете знайти варіанти багатьох японських та інших головоломок. Все знаходиться під ліцензією BSD і, мабуть, цікаво читати.
додано Автор S.C. Madsen, джерело
Я хочу продовжувати грати, але у зв'язку з вашим питанням, невпевненість в тому, чи дійсно я переможу, це їсть у мене! Забавна гра :)
додано Автор Alen Kwane, джерело
@stephenwade зроблено
додано Автор Claas Rover, джерело
Як щодо зворотного проектування? Почніть з порожньої дошки, потім автоматизуйте, скажімо, 20 кліків на випадкових квадратах. Таким чином, ви знаєте, що має бути рішення в кінці.
додано Автор Denny, джерело
@Qwerty, коли я спробував переглянути ваш Pen на повному перегляді сторінки, я отримав повідомлення "Власник цього пера має перевірити свою адресу електронної пошти, щоб увімкнути повний перегляд сторінки". Будь ласка, перевірте свою адресу електронної пошти на CodePen, щоб я міг насолоджуватися вашою грою у повному вікні! :)
додано Автор Joseph, джерело

6 Відповіді

Це тип гри, де один і той же хід, що виконується двічі, перевертає плату до попереднього стану. Таким чином, щоб гарантувати, що плата вирішується, генеруйте її, граючи в зворотному напрямку. Почніть з вирішеної (пустої) плати, потім запустіть програмним способом "натискання" випадковим чином або певну кількість разів, або поки плата не матиме потрібної кількості білих квадратів. Одне з рішень полягає в тому, щоб просто виконувати ті ж рухи в зворотному порядку. Можливо, існують інші більш короткі рішення, але ви гарантовано матимете принаймні одну.

Іншим, набагато складнішим рішенням є визначення алгоритму розв'язання, який проходить через всі можливі стани гри з вашої вихідної позиції, щоб спробувати знайти рішення. Це потребуватиме набагато більше часу для реалізації та запуску, але дозволить дошкам бути дійсно випадковими. Я не буду вдаватися до специфіки цього рішення, тому що це просто не така гарна ідея.

161
додано
Для чого це варто, хоча це правильна відповідь на математичне питання про те, як відповісти на цю проблему, це, як правило, сумнівна практика з точки зору дизайну. Таке покоління, без будь-якого конкретного плану, зазвичай призводить до головоломок, які відчувають себе дуже «точно», без особливих інтересів або будь-яких об'єднуючих тем. Можна «процедурно генерувати» цікаві випадкові проблеми для головоломки, але зазвичай це вимагає набагато складнішого погляду на те, які цікаві особливості ваших головоломок.
додано Автор Steven Stadnicki, джерело
@Qwerty: для вашої конкретної проблеми, клацання по одному квадрату двічі скасовується, тому ніколи не буває жодної причини натискати будь-який квадрат більше одного разу. Ви можете вибрати певну кількість квадратів, щоб натиснути без повторення, або розглянути рішення, яке присвоює кожному квадрату дошки XX% шанс клацання. (Ед: Приємна відповідь, +1!)
додано Автор Tiago Fernandez, джерело
@Monty Абсолютно вірно - це прекрасне представлення, але деякі з цих станів призводять до еквівалентних світлових станів, оскільки існують 2 ^ 25 легких станів, і не всі вони є розв'язними. Те ж саме стосується і перелічених мною рішень. Хитрість у створенні випадкового числа полягає в тому, що хороша головоломка шукає певне число вогнів або встановлює біти, які важко налаштувати на чисте випадкове число.
додано Автор Tiago Fernandez, джерело
@JeffBowman Дійсно, набір розв'язуваних ігор може розглядатися як 25-бітове значення, причому кожен біт, що відповідає квадрату, є числом разів перевернутого мода 2. Таким чином, можна створити випадкове число в діапазоні 0. .33,554,432, а потім розрахувати вартість кожного квадрата на дошці з короткого порядку.
додано Автор ytpillai, джерело
@JeffBowman Я думаю, це залежить від вашого визначення "хороша головоломка". Добре спочатку розрізати це число "1" біт з 25 спочатку генерованих. Отже, якщо ви хочете, ви можете підрахувати їх, і якщо їх менше 13, XOR значення з 0x1FFFFF, інвертуючи всі ваші біти. Або просто зрозумійте, що шанси на випадкову генерацію тривіальної головоломки настільки низькі, що, якщо це трапиться, гравець легко вийде на цей раз, але наступний раз, ймовірно, буде незрозумілим.
додано Автор ytpillai, джерело
Це саме те, що я зробив, коли я розробив свої рівні для мого варіанту цього дизайну, який я назвав "Congruity". Я не відчував, що міг би витрачати час, щоб зробити математичний варіант, як я представив купу інших механіків, які змішують це так, що я зробив, це створити редактор, який почався в "розв'язаній" версії, і я міг натиснути на це виглядало добре і змішано, і натиснути кнопку "експортувати" рівень.
додано Автор user49905, джерело
Я зробив майже таку ж гру раніше і закінчив, використовуючи цей підхід. На початку я включив анімацію, що показує швидке вирішення стану, що йде в нерозв'язане стан; це було досить.
додано Автор user86873, джерело
"Ще одне, набагато складніше рішення, [...] дозволить дошкам бути дійсно випадковими." Немає нічого "неправдивого" щодо методу вашого першого абзацу.
додано Автор Will, джерело
Я припускаю, що я дійсно мав на увазі, що в тому, що алгоритм генерації плати не потрібно змінюватися від його дещо більш випадкової реалізації вибору квадратів, щоб включити довільно.
додано Автор Valentin Tihomirov, джерело
@JaredGoguen дивно, я додав, що і повернувся сюди, щоб побачити ваш коментар.
додано Автор Claas Rover, джерело

Хоча вищенаведені відповіді розумні (і, ймовірно, як я б це зробив все одно), ця конкретна гра дуже добре відома. Вона називається Lights Out і математично вирішена. Є рішення тоді і тільки тоді, коли дві суми різних елементів (наведені на сторінці Вікіпедії) додають до нуля mod 2 (тобто парне число). Взагалі невелика лінійна алгебра повинна дати аналогічні умови для ігор на будь-якій дошці.

93
додано
@OrangeDog: Навіть "Lights Out" не був оригінальним, це лише бренд, який став популярним у 90-х. Наприклад, у статті у Вікіпедії перелічено це та це
додано Автор DLS3141, джерело
@Qwerty Тут цікавий документ для пошуку розв'язної конфігурації . Крім того, у ньому зазначається, що існує два специфічних векторів стовпців n1 і n2 , так що для заданої конфігурації b , якщо точка ( b, n1) = 0 і точка (b, n2) = 0 , потім b є розв'язуваним. Тут b - поточний стан вашого поля, перетвореного на вектор-стовпець.
додано Автор cosmosparda, джерело
Які відповіді ви посилаєтеся на "вищенаведені відповіді"? Це абсолютно незрозуміло, оскільки на моєму екрані є тільки одна відповідь над вашою. Пам'ятайте, що відповіді змінюють порядок залежно від голосів та параметрів користувача. Ви завжди повинні посилатися на певні відповіді, а не на те, що "вище".
додано Автор Will, джерело
Ця гра існує, але ви завжди можете розширити ідею! Додати додаткові функції! Додайте різні правила для того, що відбувається, коли ви клацнете кудись, наприклад, кольори, які додаються разом, залежно від того, в якому напрямку він був активований/вимкнений. Додайте різні "інструменти", які ви повинні використовувати. Додайте не прямокутні дошки! Багато цікавих речей. Тільки пам'ятайте, що рух завжди повинен бути зворотним.
додано Автор Valentin Tihomirov, джерело
@ Qwerty є дуже мало оригінальних ідей, і ви, звичайно, не повинні мати одного, щоб бути успішним (c.f.
додано Автор nardecky, джерело
@ BlueRaja-DannyPflughoeft Я знаю, у мене був Мерлін :)
додано Автор nardecky, джерело
Дуже сумно дізнатися, що це вже зроблено. Я подумав, що я на щось.
додано Автор Claas Rover, джерело

Перейдіть навпаки, створюючи свою головоломку.

Замість того, щоб випадково вибирати плитки та перетворювати їх з білого на чорний, почніть з чистого аркуша, потім оберіть фрагменти, але замість того, щоб перевести та в чорний колір, зробіть його таким, як якщо б його вибрав користувач. у перегортанні всіх інших плиток навколо нього.

Таким чином, вам гарантовано мати принаймні одне рішення: користувачеві доведеться скасувати те, що ви "AI" гравець зробив для створення рівня.

13
додано

Ед і Олександр мають право на це.

Але якщо ви зробіть хочете знати, якщо кожне рішення є можливим, є способи.

Є кінцеве число можливих головоломок

Натискання на одному і тому ж квадраті двічі призводить до того самого результату, що і не натискання на неї, незалежно від того, скільки кліків було зроблено між ними. Це означає, що кожне рішення можна описати, надавши кожному квадрату двійкове значення "clicked" або "not clicked". Аналогічно, кожну головоломку можна описати, надавши кожному квадрату двійкове значення 'toggled' або 'not toggled'. Це означає, що існує 2 ^ 25 можливих головоломок і 2 25 можливих рішень. Якщо ви можете довести, що кожне рішення вирішує унікальну головоломку, то має бути вирішення кожної головоломки. Аналогічно, якщо ви знайдете два рішення, які вирішують одну і ту ж головоломку, то не може бути вирішення кожної головоломки.

Крім того, 2 ^ 25 становить 33,554,432. Це досить багато, але це не некерований номер. Хороший алгоритм і пристойний комп'ютер могли б, напевно, перебратися на пару годин, особливо якщо врахувати, що половина головоломок - інверси іншої половини.

7
додано
@PeterTaylor Безумовно, знадобиться набагато довше, щоб кодувати тренажер, ніж він буде виконувати результати.
додано Автор Douglas Anderson, джерело
33,5 мільйона? Замініть "пару годин" на "пару секунд", і це, ймовірно, ще песимістично.
додано Автор Sheldon, джерело
Математичний час: Якщо ви хочете обчислити кількість різних дощок (незалежно від розв'язності), беручи до уваги всі симетрії, то лемма Бернсайда - це шлях: існує 16 симетрій (одна тривіальна, три поворотів, чотирьох відбитків, а потім кожного з цих 8 поєднаних з інверсією вкл/викл), і для кожної з цих симетрій деяка кількість дощок цілком не змінюється. Якщо взяти середнє значення абсолютно незмінених дощок на симетрію, це дорівнює кількості різних плат.
додано Автор boris, джерело
Більше половини є "зворотними" - крім горизонтальних відбитків, у вас є вертикальні відбиття і обертання.
додано Автор Robert S., джерело
Виявляється, як зазначив у своїй відповіді Роберт Мастрагостіно, це насправді добре відома, добре вивчена проблема. Кожна вирішувана головоломка має рівно 4 рішення, і більшість випадкових плат не розв'язуються. Пошук усього цього простору може бути цікавим, але оскільки вже існує доказ ( math.ksu.edu/math551/math551a.f06/lights_out.pdf ) Ви також можете зробити пару точкових продуктів і мати однакову відповідь протягом декількох мікросекунд. :)
додано Автор GrandOpener, джерело
@ Clockwork-Muse, так, але це важче обчислити точне число для, тому що в той час як асиметричні конструкції можуть обертатися і перевертатися в 8 перестановок, симетричні конструкції мають менше перестановок. Так що я тільки згадав білий/чорний інвертування, так як кожне рішення має рівно 1 зворотний. (Незважаючи на те, що для цього обернено, ви повинні довести, що ви можете перевернути всю дошку)
додано Автор user110428, джерело

Узагальнена відповідь:

  1. Створіть матрицю розміру (# ходи) x (# lights).
  2. Помістіть 1 у клітинку, якщо переміщення відповідно до цього рядка перемикає світло, що відповідає цьому стовпцю, 0, інакше.
  3. Виконайте ліквідацію Гаусса-Йордану (по модулю 2) на матриці.
  4. Якщо матриця, яка отримана, має один 1 у кожному стовпці, і кожен рядок має не більше одного, а потім кожну сітку в розв'язних.
4
додано

Інші вже згадували способи знайти, чи можна вирішити випадково згенеровану головоломку. Питання, яке вам слід задати, це те, чи дійсно ви хочете випадково згенеровані головоломки.

Випадково згенеровані головоломки мають один і той самий основний недолік: їхня складність значною мірою непередбачувана. Можливі головоломки, які ви могли б отримати, можуть варіюватися від вже вирішених, до тривіальних (рішення очевидні) до жорстких (рішення не очевидні) до неможливих (загадка не може бути вирішена взагалі). Оскільки складність непередбачувана, вона створює для гравця незадовільний досвід, особливо якщо вони виконують кілька головоломок поспіль. Вони навряд чи отримають рівну криву складності, яка може зробити їх нудними або розчарованими залежно від того, які головоломки вони отримують.

Інша проблема випадкового генерації полягає в тому, що час, необхідний для ініціалізації головоломки, є непередбачуваним. Взагалі кажучи, ви збираєтеся отримати розгадану головоломку (майже) відразу, але з деякою невдачею, ваші випадково згенеровані головоломки можуть закінчитися на смузі нерозв'язних головоломок.

Один із способів вирішити обидва ці питання полягає в тому, що попередньо визначені вектори кожної розв'язуваної головоломки доступні, організовані у групи складності, а потім вибирають випадкову головоломку з розв'язуваних головоломок на основі складності. Таким чином, ви будете впевнені, що кожна головоломка може бути вирішена, що складність передбачувана і що покоління буде здійснюватися в постійний час.

1
додано