Stworzyłem rodzaj układanki, w której celem jest pozbycie się wszystkich białych płytek. Możesz spróbować na końcu pytania.

Za każdym razem plansza jest generowana losowo z białymi kafelkami w losowych miejscach na siatce 5 * 5. Możesz kliknąć dowolny kafelek na tej siatce, a on zmieni kolor i wszystkie kafelki dotykające go po bokach. Moim dylematem jest to, że nie wiem, czy wygeneruje niemożliwą płytę. Jaki jest najlepszy sposób na sprawdzenie takich rzeczy?

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>

Jest to rodzaj gry, w której ten sam dwukrotnie wykonany ruch przywraca planszę do poprzedniego stanu. Aby upewnić się, że plansza jest do rozwiązania, wygeneruj ją, grając w odwrotnej kolejności. Zacznij od rozwiązanej (pustej) planszy, a następnie zacznij programowo „losowo” klikać określoną liczbę razy lub do momentu, aż na planszy pojawi się żądana liczba białych kwadratów. Jednym z rozwiązań jest po prostu wykonanie tych samych ruchów w odwrotnej kolejności. Mogą istnieć inne krótsze rozwiązania, ale na pewno masz co najmniej jedno.

Innym, o wiele bardziej złożonym rozwiązaniem, jest zdefiniowanie algorytmu rozwiązywania, który przechodzi wszystkie możliwe stany gry od twojej pozycji początkowej, aby spróbować znaleźć rozwiązanie. Wdrożenie i uruchomienie zajęłoby znacznie więcej czasu, ale pozwoliłoby na generowanie losowych tablic. Nie będę wdawał się w szczegóły tego rozwiązania, ponieważ nie jest to tak dobry pomysł.

Chociaż powyższe odpowiedzi są sprytne (i prawdopodobnie jak i tak bym to zrobił), ta konkretna gra jest bardzo dobrze znana. Nazywa się Lights Out i został matematycznie rozwiązany. Istnieje rozwiązanie wtedy i tylko wtedy, gdy dwie sumy różnych elementów (podane na stronie wikipedii) dodają do zera mod 2 (tj. Liczby parzystej). Ogólnie mała algebra liniowa powinna dawać podobne warunki rozwiązania dla gier na dowolnej planszy.

Podczas generowania układanki odwróć się.

Zamiast losowo wybierając płytki i zamieniając je z białego na czarny, zacząć od czystej karty, a następnie wybrać płytki ale zamiast toczenia , że płytki na czarno, zrób to tak, jakby użytkownik wybrał go, w wyniku odbijania wszystkich innych płytek dookoła tego.

W ten sposób masz zagwarantowane co najmniej jedno rozwiązanie: użytkownik będzie musiał cofnąć to, co zrobiłeś gracz „AI”, aby stworzyć poziom.

Ed i Alexandre mają do tego prawo.

Ale jeśli nie chcesz wiedzieć, czy każde rozwiązanie jest możliwe, istnieją sposoby.

Istnieje ograniczona liczba możliwych zagadek

Dwukrotne kliknięcie tego samego kwadratu daje ten sam wynik, co wcale go nie klikanie, bez względu na to, ile kliknięć zostało między nimi zrobionych. Oznacza to, że każde rozwiązanie można opisać, przypisując każdemu kwadratowi wartość binarną „kliknięto” lub „nie kliknięto”. Podobnie, każdą łamigłówkę można opisać, nadając każdemu kwadratowi wartość binarną „przełączane” lub „nie przełączane”. Oznacza to, że istnieje 2 ^ 25 możliwych łamigłówek i 2 ^ 25 możliwych rozwiązań. Jeśli możesz udowodnić, że każde rozwiązanie rozwiązuje unikalną łamigłówkę, musi istnieć rozwiązanie każdej układanki. Podobnie, jeśli znajdziesz dwa rozwiązania, które rozwiązują tę samą łamigłówkę, nie może być rozwiązania dla każdej układanki.

Również 2 ^ 25 wynosi 33,554 432. To całkiem sporo, ale nie jest to liczba niemożliwa do zarządzania. Dobry algorytm i przyzwoity komputer mogą prawdopodobnie zaszkodzić tej sile w ciągu kilku godzin, zwłaszcza jeśli weźmie się pod uwagę, że połowa zagadek to odwrotność drugiej połowy.

Uogólniona odpowiedź:

1. Utwórz macierz wielkości (# ruchów) x (# świateł).
2. Umieść 1 w komórce, jeśli wykonanie ruchu odpowiadającego temu wierszowi przełącza światło odpowiadające tej kolumnie, w przeciwnym razie 0.
3. Wykonaj eliminację Gaussa-Jordana (moduł 2) na matrycy.
4. Jeśli wynikowa macierz ma jeden 1 w każdej kolumnie, a każdy wiersz ma co najwyżej jeden 1, to każda siatka jest do rozwiązania.

Inni wspominali już o sposobach sprawdzenia, czy losowo wygenerowana łamigłówka jest do rozwiązania. pytanie, które powinieneś również zadać, to czy faktycznie chcesz losowo generowanych łamigłówek.

Wszystkie losowo generowane łamigłówki mają tę samą wadę: ich trudność jest prawie nieprzewidywalna. Możliwe układanki mogą się wahać od już rozwiązanych, przez trywialne (rozwiązanie jest oczywiste) do trudnych (rozwiązanie nie jest oczywiste) do niemożliwych (układanki w ogóle nie można rozwiązać). Ponieważ trudność jest nieprzewidywalna, zapewnia niezadowalające wrażenia dla gracza, szczególnie jeśli wykonują wiele łamigłówek z rzędu. Jest mało prawdopodobne, aby uzyskały gładką krzywą trudności, co może powodować, że będą się nudzić lub frustrować w zależności od tego, jakie łamigłówki dostaną.

Kolejnym problemem generowania losowego jest to, że czas inicjalizacji układanki jest nieprzewidywalny. Ogólnie rzecz biorąc, od razu otrzymasz (prawie) układankę do rozwiązania, ale przy odrobinie szczęścia losowo wygenerowane puzzle mogą skończyć się pasmem nierozwiązywalnych zagadek.

Jednym ze sposobów rozwiązania obu tych problemów jest posiadanie predefiniowanych wektorów każdej dostępnej układanki, ułożonych w grupy trudności, a następnie wybranie losowej układanki z zagadek rozwiązanych na podstawie poziomu trudności. W ten sposób będziesz mieć pewność, że każdą zagadkę da się rozwiązać, że trudność jest przewidywalna i że generacja zostanie wykonana w stałym czasie.