Как я могу узнать, всегда ли моя игра-головоломка возможна?

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

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

 function newgame () {
 ходы = 0;
    document.getElementById ("move"). innerHTML = "Перемещение:" + перемещение;

  для (var i = 0; i <25; i ++) {
   if (Math.random ()> = 0,5) {
$ (document.getElementsByClassName ('block') [i]). toggleClass ("b1 b2")
   }
}
}
новая игра();
функция toggle (a, b) {
  ходы + = 1;
  document.getElementById ("move"). innerHTML = "Перемещение:" + перемещение;
$ (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 {
  плыть налево;
  background-color: # 000000;
  ширина: 300 пикселей;
  высота: 300 пикселей;
  переполнение: скрыто;
  переполнение-x: скрыто;
  user-select: none;
  display: inline-block;
}

.container {
  border-color: #ffffff;
  border-width: 5px;
  border-style: solid;
  border-radius: 5px;
  ширина: 600 пикселей;
  высота: 300 пикселей;
  text-align: center;
}

.боковая сторона {
  плыть налево;
  background-color: # 000000;
  ширина: 300 пикселей;
  высота: 300 пикселей;
  переполнение: скрыто;
  переполнение-x: скрыто;
  user-select: none;
  display: inline-block;
}

.block {
  переход: фоновый цвет 0,2 с;
  плыть налево;
}

.b1: hover {
  background-color: # 444444;
  курсор: указатель;
}

.b2: hover {
  background-color: #bbbbbb;
  курсор: указатель;
}

.ряд {
  ширина: 300 пикселей;
  переполнение: авто;
  переполнение-x: скрыто;
}

.b1 {
  display: inline-block;
  высота: 50 пикселей;
  ширина: 50 пикселей;
  background-color: # 000000;
  border-color: # 000000;
  border-width: 5px;
  border-style: solid;
}




.Би 2 {
  display: inline-block;
  высота: 50 пикселей;
  ширина: 50 пикселей;
  background-color: #ffffff;
  border-color: # 000000;
  border-width: 5px;
  border-style: solid;
}



.заглавие {
  ширина: 200 пикселей;
  высота: 50 пикселей;
  цвет: #ffffff;
  font-size: 55px;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  вертикально-выровненный: средний;
}

.button {
  курсор: указатель;
  ширина: 200 пикселей;
  высота: 50 пикселей;
  background-color: # 000000;
  border-color: #ffffff;
  border-style: solid;
  border-width: 5px;
  цвет: #ffffff;
  размер шрифта: 25 пикселей;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  вертикально-выровненный: средний;
  border-radius: 5px;
  переход: фоновый цвет 0,3 с, цвет 0,3 с;
}

.button: hover {
  background-color: #ffffff;
  цвет: # 000000;
}

.столик {
  padding: 30px 0px;
  высота: 200 пикселей;
}


#moves {
  ширина: 200 пикселей;
  высота: 50 пикселей;
  цвет: #aaaaaa;
  размер шрифта: 30 пикселей;
  font-weight: bold;
  font-family: Arial;
  display: table-cell;
  вертикально-выровненный: средний;
}
 <script src = "https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min .js "> & Lt; & /сценарий; GT
& Lt; & центр GT;
  <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);" класс = "блок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 = " 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">
      <center class = "sidetable">
        <div class = "title"> Tiles </div>
        & Lt; & шир GT;
        <div class = "button" onclick = "newgame ()"> Новая игра </div>
        & Lt; & шир GT; & Lt; & шир GT;
        <div id = "move"> Перемещение: 0 </div>
      & Lt; /центр >
    & Lt; /дел >
    
  & Lt; /дел >
    & Lt; /центр >
68 голосов | спросил Qwerty 7 FebruaryEurope/MoscowbWed, 07 Feb 2018 23:18:16 +0300000000pmWed, 07 Feb 2018 23:18:16 +030018 2018, 23:18:16

6 ответов


161

Это тип игры, в котором одно и то же действие выполняется дважды, перевернувшись на предыдущее состояние. Поэтому, чтобы обеспечить разрешимость платы, сгенерируйте ее, играя в обратном порядке. Начните с разрешенной (пустой) доски, затем начните программно «нажимать» произвольно либо определенное количество раз, либо до тех пор, пока на доске не будет желаемого количества белых квадратов. Одно из решений заключается в том, чтобы просто выполнить те же шаги в обратном порядке. Другие более короткие решения могут существовать, но вы гарантированно имеете хотя бы один.

Другим, гораздо более сложным решением является определение алгоритма решения, который проходит через все возможные игровые состояния из вашей начальной позиции, чтобы попытаться найти решение. Это займет намного больше времени, чтобы реализовать и запустить, но позволит создавать платы по-разному. Я не буду вдаваться в подробности этого решения, потому что это не совсем хорошая идея.

ответил Ed Marty 7 FebruaryEurope/MoscowbWed, 07 Feb 2018 23:32:15 +0300000000pmWed, 07 Feb 2018 23:32:15 +030018 2018, 23:32:15
93

В то время как вышеупомянутые ответы являются умными (и, вероятно, как бы я это сделал), эта конкретная игра очень хорошо известна. Он называется Lights Out и был математически решен. Существует решение тогда и только тогда, когда две суммы различных элементов (заданные на странице wikipedia) добавляют к нулю mod 2 (т. Е. Четное число). В общем, небольшая линейная алгебра должна давать аналогичные условия для игр на любой доске.

ответил Robert Mastragostino 8 FebruaryEurope/MoscowbThu, 08 Feb 2018 06:56:23 +0300000000amThu, 08 Feb 2018 06:56:23 +030018 2018, 06:56:23
13

Идите наоборот, создавая свою головоломку.

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

Таким образом, у вас будет гарантировано как минимум одно решение: пользователь должен будет отменить то, что сделал игрок «AI», чтобы создать уровень.

ответил Alexandre Vaillancourt 7 FebruaryEurope/MoscowbWed, 07 Feb 2018 23:32:07 +0300000000pmWed, 07 Feb 2018 23:32:07 +030018 2018, 23:32:07
7

Эд и Александр имеют право на это.

Но если вы do хотите знать, возможно ли любое решение, существуют способы.

Существует конечное число возможных головоломок

Нажатие на один и тот же квадрат дважды дает тот же результат, что и не щелкая на нем, независимо от того, сколько кликов было сделано между ними. Это означает, что каждое решение может быть описано путем предоставления каждому квадрату двоичного значения «clicked» или «not clicked». Точно так же каждая головоломка может быть описана путем предоставления каждому квадрату двоичного значения 'toggled' или 'not toggled'. Это означает, что есть 2 ^ 25 возможных головоломок и 2 ^ 25 возможных решений. Если вы можете доказать, что каждое решение решает уникальную загадку, тогда должно быть решение каждой головоломки. Аналогично, если вы найдете два решения, которые решают одну и ту же загадку, тогда не может быть решения каждой головоломки.

Кроме того, 2 ^ 25 составляет 33 554 432. Это довольно много, но это не неуправляемый номер. Хороший алгоритм и достойный компьютер могут, вероятно, грубой силой, что через пару часов, особенно если учесть, что половина головоломок - это инверсии другой половины.

ответил Arcanist Lupus 8 FebruaryEurope/MoscowbThu, 08 Feb 2018 06:02:11 +0300000000amThu, 08 Feb 2018 06:02:11 +030018 2018, 06:02:11
4

Обобщенный ответ:

  1. Создайте матрицу размера (# move) x (# lights).
  2. Поместите 1 в ячейку, если перемещение, соответствующее этой строке, переключает свет, соответствующий этому столбцу, 0 в противном случае.
  3. Выполните удаление Гаусса-Джордана (по модулю 2) на матрице.
  4. Если полученная матрица имеет по одному в каждом столбце, и каждая строка имеет не более одного единственного числа, то каждая сетка разрешима.
ответил Mark Tilford 8 FebruaryEurope/MoscowbThu, 08 Feb 2018 17:32:15 +0300000000pmThu, 08 Feb 2018 17:32:15 +030018 2018, 17:32:15
1

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

Случайно созданные головоломки имеют один и тот же основной недостаток: их трудность в значительной степени непредсказуема. Возможные загадки, которые вы можете получить, могут варьироваться от уже решены, до тривиальных (решение очевидно), чтобы трудно (решение не очевидно) до невозможности (головоломка вообще не разрешима). Поскольку трудность непредсказуема, это создает неудовлетворительный опыт для игрока, особенно если они выполняют несколько головоломок подряд. Они вряд ли получат гладкую кривую сложности, которая может сделать их скучными или расстроенными в зависимости от того, какие головоломки они получают.

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

Одним из способов решения этих проблем является наличие заранее определенных векторов каждой разрешимой головоломки, расположенных в группах сложности, а затем выбор случайной головоломки из разрешимых головоломок на основе сложности. Таким образом, вы будете уверены, что каждая головоломка разрешима, что трудность предсказуема и что поколение будет выполняться в постоянное время.

ответил Nzall 13 FebruaryEurope/MoscowbTue, 13 Feb 2018 18:14:36 +0300000000pmTue, 13 Feb 2018 18:14:36 +030018 2018, 18:14:36

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132