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

68

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

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

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>
<center>
  <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">
      <center class="sidetable">
        <div class="title">Tiles</div>
        <br>
        <div class="button" onclick="newgame()">New Game</div>
        <br><br>
        <div id="moves">Moves: 0</div>
      </center>
    </div>
    
  </div>
    </center>

Qwerty
источник
9
Если вы заинтересованы в подобных играх-головоломках, взгляните на Портативную коллекцию головоломок Саймона Тэтхэма . Помимо этого типа (называется Flip there), вы можете найти варианты многих японских и других головоломок. Все находится под лицензией BSD и, вероятно, интересно читать.
Дабу
10
Как насчет реверс-инжиниринга? Начните с пустой доски, затем автоматизируйте, скажем, 20 кликов по случайным клеткам. Таким образом, вы знаете, что в конце должно быть решение.
AJFaraday
3
Я хочу продолжать играть, но из-за твоего вопроса неуверенность в том, действительно ли я выиграю, съедает меня!
Веселая
@MrDuk codepen.io/qwertyquerty/pen/WMGwVW вот готовый проект! Этот исправлен и отполирован. Я также сделал электронное приложение.
Qwerty
@Qwerty, когда я пытался просмотреть ваше перо в режиме полного просмотра страницы, я получил сообщение «Владелец этого пера должен подтвердить свой адрес электронной почты, чтобы включить полный просмотр страницы». Пожалуйста, подтвердите ваш адрес электронной почты на CodePen, чтобы я мог наслаждаться вашей игрой в полном окне! :)
Стивенвейд,

Ответы:

161

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

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

Эд Марти
источник
22
@Qwerty: для вашей конкретной задачи, дважды щелкнув один и тот же квадрат, вы отменяете себя, поэтому нет никакой причины щелкать по любому квадрату более одного раза. Возможно, вы захотите выбрать определенное количество квадратов для щелчка, не повторяя, или рассмотрите решение, которое назначает XX% вероятности клика для каждого квадрата на доске. (Ред .: Хороший ответ, +1!)
Джефф Боуман
3
Я сделал почти такую ​​же игру раньше и в итоге использовал этот подход. В начале я включил анимацию, показывающую, что решенное состояние быстро переходит в нерешенное состояние; это было красиво
Джаред Гогуэн
1
@JaredGoguen странно, я добавил это и вернулся сюда, чтобы увидеть ваш комментарий.
Qwerty
4
@JeffBowman Действительно, набор разрешимых игр может рассматриваться как 25-битное значение, каждый бит соответствует квадрату, который является числом раз, когда он был перевернут мод 2. Таким образом, можно генерировать случайное число в диапазоне 0. .33,554,432, а затем рассчитать значение каждого квадрата на доске из него в короткие сроки.
Монти Хардер
7
Что бы это ни стоило, хотя это правильный ответ на математический вопрос о том, как решить эту проблему, это обычно сомнительная практика с точки зрения дизайна. Такое поколение без какого-либо особого плана, как правило, приводит к головоломкам, которые кажутся очень «одинаковыми», без каких-либо особых точек интереса или каких-либо объединяющих тем. Можно «процедурно генерировать» интересные проблемные экземпляры для головоломки, но обычно требуется гораздо более внимательный взгляд на интересные особенности ваших головоломок.
Стивен Стадницки,
92

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

Роберт Мастрагостино
источник
2
Грустно узнавать, что это уже сделано. Я думал, что я был к чему-то.
Qwerty
39
@Qwerty есть очень мало оригинальных идей, и вам, безусловно, не нужно иметь одну, чтобы быть успешной (ср. Ровио, Кинг).
Стоп Harm Моника
14
Эта конкретная игра существует, но вы всегда можете расширить идею! Добавьте больше возможностей! Добавьте различные правила для того, что происходит, когда вы щелкаете где-то, например, цвета, которые складываются вместе в зависимости от того, в каком направлении он был активирован / деактивирован. Добавьте различные «инструменты», которые вы должны использовать. Добавьте непрямоугольные доски! Много забавных вещей, чтобы сделать. Просто помните, что движение всегда должно меняться само собой.
Эд Марти
7
@OrangeDog: Даже «Lights Out» не был оригинальным, это просто название бренда, которое стало популярным в 90-х годах. Например, в статье в Википедии перечислено это и это
BlueRaja - Дэнни Пфлугхофт,
1
Какие ответы вы называете «вышеуказанными ответами»? Это совершенно неясно, так как на моем экране есть только один ответ над вашим. Помните, что ответы меняются в зависимости от голосов и пользовательских настроек. Вы всегда должны ссылаться на конкретные ответы, а не на что-то «выше».
Дэвид Ричерби
13

При создании вашей головоломки идите наоборот.

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

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

Vaillancourt
источник
7

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

Но если вы действительно хотите знать , если каждое решение возможно, есть способы.

Есть конечное число возможных головоломок

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

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

Чародейская волчанка
источник
4
Более половины являются «инверсиями» - помимо горизонтальных отражений у вас есть вертикальные отражения и повороты.
Заводная муза
@ Clockwork-Muse, да, но точнее рассчитать их сложнее, потому что хотя асимметричные конструкции можно вращать и переворачивать в 8 перестановках, симметричные конструкции имеют меньше перестановок. Поэтому я упомянул только инверсию белого / черного, поскольку каждое решение имеет ровно 1 инверсию. (Хотя для того, чтобы это не сработало, вам нужно доказать, что вы можете перевернуть всю доску)
Чародейка Lupus
Оказывается, как отметил в своем ответе Роберт Мастрагостино, это на самом деле хорошо известная, хорошо изученная проблема. Каждая разрешимая головоломка имеет ровно 4 решения, и большинство случайных досок не разрешимы. Поиск во всем этом пространстве может быть увлекательным, но поскольку уже существует доказательство ( math.ksu.edu/math551/math551a.f06/lights_out.pdf ), вы также можете сделать несколько точечных продуктов и получить один и тот же ответ в нескольких микросекунд. :)
GrandOpener
Математическое время: если вы хотите вычислить количество различных плат (независимо от разрешимости), принимая во внимание все симметрии, то лемма Бернсайда - это то, что нужно: 16 симметрий (одна тривиальная, три поворота, четыре отражения, а затем каждая из этих 8 сочетается с инверсией включения / выключения), и для каждой из этих симметрий некоторое количество плат совершенно не изменяется. Если вы возьмете среднее количество полностью неизмененных досок на симметрию, это будет равно количеству разных досок.
Артур
1
@PeterTaylor Определенно, для кодирования симулятора потребуется гораздо больше времени, чем для запуска результатов.
CorsiKa
4

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

  1. Создайте матрицу размера (# ходов) х (# свет).
  2. Поместите 1 в ячейку, если перемещение, соответствующее этой строке, переключает свет, соответствующий этому столбцу, в противном случае - 0.
  3. Выполните исключение Гаусса-Джордана (по модулю 2) на матрице.
  4. Если полученная матрица имеет один 1 в каждом столбце, а каждая строка имеет не более одного 1, то каждая решетка решаема.
Марк Тилфорд
источник
1

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

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

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

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

Nzall
источник