Woher weiß ich, ob mein Puzzlespiel immer möglich ist?

68

Ich habe eine Art Puzzlespiel gemacht, bei dem es darum geht, alle weißen Kacheln loszuwerden. Sie können es am Ende der Frage versuchen.

Jedes Mal wird die Tafel zufällig mit weißen Kacheln an zufälligen Stellen in einem 5 * 5-Raster erzeugt. Sie können auf eine beliebige Kachel in diesem Raster klicken. Die Farbe und alle Kacheln, die diese an den Seiten berühren, werden umgeschaltet. Mein Dilemma ist die Tatsache, dass ich nicht weiß, ob daraus ein unmögliches Board wird. Was ist der beste Weg, um solche Dinge zu überprüfen?

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
quelle
9
Wenn Sie sich für diese Art von Puzzlespielen interessieren, schauen Sie sich die Portable Puzzle Collection von Simon Tatham an . Abgesehen von diesem Typ (dort Flip genannt) gibt es Varianten vieler japanischer und anderer Rätsel. Alles ist unter BSD-Lizenz und wahrscheinlich eine interessante Lektüre.
Dubu
10
Wie wäre es mit Reverse-Engineering? Beginnen Sie mit einem leeren Brett und automatisieren Sie dann, sagen wir 20 Klicks auf zufällige Quadrate. Auf diese Weise wissen Sie, dass es am Ende eine Lösung geben muss.
AJFaraday
3
Ich möchte weiterspielen, aber aufgrund Ihrer Frage frisst mich die Ungewissheit, ob ich tatsächlich gewinnen werde oder nicht! Fun-Spiel :)
MrDuk
@MrDuk codepen.io/qwertyquerty/pen/WMGwVW hier ist das fertige Projekt! Dieser ist repariert und aufpoliert. Ich habe auch eine Elektronen-App gemacht.
Qwerty
@Qwerty Als ich versuchte, Ihren Stift in der Ganzseitenansicht anzuzeigen, erhielt ich die Meldung "Der Besitzer dieses Stifts muss seine E-Mail-Adresse bestätigen, um die Ganzseitenansicht zu aktivieren." Bitte überprüfe deine E-Mail-Adresse auf CodePen, damit ich dein Spiel im vollen Fenster genießen kann! :)
stephenwade

Antworten:

161

Dies ist die Art von Spiel, bei der der gleiche Zug zweimal ausgeführt wird, um den vorherigen Zustand des Spielbretts wiederherzustellen. Um sicherzustellen, dass ein Brett lösbar ist, generieren Sie es, indem Sie in umgekehrter Reihenfolge spielen. Beginnen Sie mit einer gelösten (leeren) Tafel und klicken Sie dann programmgesteuert nach dem Zufallsprinzip entweder eine bestimmte Anzahl von Malen oder bis die Tafel die gewünschte Anzahl von weißen Quadraten aufweist. Eine Lösung besteht dann darin, die gleichen Züge einfach in umgekehrter Reihenfolge auszuführen. Es gibt möglicherweise andere kürzere Lösungen, aber Sie haben garantiert mindestens eine.

Eine andere, viel komplexere Lösung besteht darin, einen Lösungsalgorithmus zu definieren, der alle möglichen Spielzustände von Ihrer Startposition aus durchläuft, um die Lösung zu finden. Dies würde viel länger dauern, um implementiert und ausgeführt zu werden, würde jedoch ermöglichen, dass die Boards wirklich zufällig generiert werden. Ich werde nicht auf die Details dieser Lösung eingehen, weil es einfach keine so gute Idee ist.

Ed Marty
quelle
22
@Qwerty: Wenn Sie für ein bestimmtes Problem zweimal auf dasselbe Quadrat klicken, wird es automatisch gelöscht. Es gibt also keinen Grund, mehr als einmal auf ein Quadrat zu klicken. Möglicherweise möchten Sie eine bestimmte Anzahl von Feldern auswählen, auf die Sie klicken möchten, ohne sie zu wiederholen, oder eine Lösung in Betracht ziehen, bei der jedem Feld auf dem Brett eine Wahrscheinlichkeit von XX% für das Klicken zugewiesen wird. (Ed: Nette Antwort, +1!)
Jeff Bowman
3
Ich habe fast das gleiche Spiel gemacht und am Ende diesen Ansatz gewählt. Zu Beginn habe ich eine Animation eingefügt, die zeigt, wie der gelöste Zustand schnell in den ungelösten Zustand übergeht. es war schön.
Jared Goguen
1
@JaredGoguen ungerade, ich fügte hinzu und kam hierher zurück, um Ihren Kommentar zu sehen.
Qwerty
4
@ JeffBowman In der Tat kann die Menge der lösbaren Spiele als 25-Bit-Wert behandelt werden, wobei jedes Bit einem Quadrat entspricht, das die Anzahl der Spiegelungen von Mod 2 darstellt. Man kann also eine Zufallszahl im Bereich 0 generieren. .33,554,432 und berechnen Sie dann den Wert jedes Quadrats auf der Tafel in kurzer Zeit.
Monty Harder
7
Für das, was es wert ist, ist dies zwar die richtige Antwort auf die mathematische Frage, wie dieses Problem zu beantworten ist, dies ist jedoch vom Standpunkt des Designs aus in der Regel eine zweifelhafte Praxis. Diese Art von Generation, ohne einen bestimmten Plan, führt im Allgemeinen zu Rätseln, die sich sehr "gleichartig" anfühlen, ohne bestimmte Punkte von Interesse oder einheitliche Themen. Es ist möglich, interessante Probleminstanzen für ein Puzzlespiel prozedural zu generieren, aber es erfordert normalerweise einen viel genaueren Blick auf die interessanten Eigenschaften Ihrer Puzzlespiele.
Steven Stadnicki
92

Während die obigen Antworten klug sind (und wahrscheinlich, wie ich es sowieso tun würde), ist dieses spezielle Spiel sehr bekannt. Es heißt Lights Out und wurde mathematisch gelöst. Es gibt nur dann eine Lösung, wenn zwei Summen verschiedener Elemente (auf der Wikipedia-Seite angegeben) zu Null Mod 2 (dh einer geraden Zahl) addieren. Im Allgemeinen sollte eine kleine lineare Algebra ähnliche Lösungsbedingungen für Spiele auf jedem Brett ergeben.

Robert Mastragostino
quelle
2
Es ist irgendwie traurig herauszufinden, dass es bereits gemacht wurde. Ich dachte, ich hätte etwas vor.
Qwerty
39
@Qwerty Es gibt nur sehr wenige originelle Ideen, und Sie müssen keine haben, um erfolgreich zu sein (vgl. Rovio, King).
OrangeDog
14
Dieses spezielle Spiel gibt es, aber Sie können die Idee immer erweitern! Weitere Funktionen hinzufügen! Fügen Sie verschiedene Regeln für das Klicken ein, z. B. Farben, die sich basierend auf der Richtung, aus der es aktiviert / deaktiviert wurde, addieren. Fügen Sie verschiedene Tools hinzu, die Sie verwenden müssen. Fügen Sie nicht rechteckige Tafeln hinzu! Es gibt viele lustige Dinge zu tun. Denken Sie daran, dass sich ein Zug immer umkehren muss.
Ed Marty
7
@OrangeDog: Sogar 'Lights Out' war kein Original, das ist nur der Markenname, der in den 90ern populär wurde. Der Wikipedia-Artikel listet dies und das auf
BlueRaja - Danny Pflughoeft
1
Welche Antworten bezeichnen Sie als "die obigen Antworten"? Es ist völlig unklar, da es auf meinem Bildschirm nur eine Antwort über Ihrer gibt. Denken Sie daran, dass die Reihenfolge der Antworten je nach Stimmen und Benutzeroptionen geändert wird. Sie sollten immer auf bestimmte Antworten verweisen, anstatt auf etwas "oben" zu verweisen.
David Richerby
13

Gehen Sie beim Generieren Ihres Puzzles umgekehrt vor.

Anstatt die Kacheln nach dem Zufallsprinzip auszuwählen und von weiß nach schwarz zu drehen, beginnen Sie mit einem leeren Schiefer und wählen Sie dann die Kacheln aus. Anstatt diese Kachel in schwarz zu drehen , stellen Sie sie so ein, als ob der Benutzer sie ausgewählt hätte, wodurch alle anderen Kacheln gespiegelt würden um es herum.

Auf diese Weise haben Sie garantiert mindestens eine Lösung: Der Benutzer muss rückgängig machen, was Ihr "KI" -Spieler getan hat, um das Level zu erstellen.

Alexandre Vaillancourt
quelle
7

Ed und Alexandre haben das Recht dazu.

Wenn Sie jedoch wissen möchten, ob jede Lösung möglich ist, gibt es verschiedene Möglichkeiten.

Es gibt eine endliche Anzahl möglicher Rätsel

Wenn Sie zweimal auf dasselbe Quadrat klicken, wird dasselbe Ergebnis erzielt, als wenn Sie überhaupt nicht darauf klicken, unabhängig davon, wie viele Klicks zwischen ihnen gemacht wurden. Das bedeutet, dass jede Lösung beschrieben werden kann, indem jedem Quadrat ein Binärwert von "angeklickt" oder "nicht angeklickt" zugewiesen wird. In ähnlicher Weise kann jedes Puzzle beschrieben werden, indem jedem Quadrat ein Binärwert von "umgeschaltet" oder "nicht umgeschaltet" zugewiesen wird. Das heißt, es gibt 2 ^ 25 mögliche Rätsel und 2 ^ 25 mögliche Lösungen. Wenn Sie nachweisen können, dass jede Lösung ein einzigartiges Puzzle löst, muss es für jedes Puzzle eine Lösung geben. Wenn Sie zwei Lösungen finden, die dasselbe Rätsel lösen, kann es nicht für jedes Rätsel eine Lösung geben.

Auch 2 ^ 25 ist 33.554.432. Das ist ziemlich viel, aber es ist keine unüberschaubare Zahl. Ein guter Algorithmus und ein anständiger Computer könnten das in ein paar Stunden brutal erzwingen, besonders wenn man bedenkt, dass die Hälfte der Rätsel die Umkehrung der anderen Hälfte ist.

Arkanist Lupus
quelle
4
Mehr als die Hälfte sind "Inverse" - neben horizontalen Reflexionen gibt es vertikale Reflexionen und Rotationen.
Clockwork-Muse
@ Clockwork-Muse, ja, aber es ist schwieriger, eine genaue Zahl zu berechnen, da asymmetrische Designs in 8 Permutationen gedreht und gespiegelt werden können, während symmetrische Designs weniger Permutationen haben. Also habe ich nur die Weiß / Schwarz-Invertierung erwähnt, da jede Lösung genau 1 Inverse hat. (Damit dies umgekehrt funktioniert, muss man allerdings beweisen, dass man das gesamte Board umdrehen kann.)
Arkanist Lupus
Es stellt sich heraus, wie Robert Mastragostino in seiner Antwort erwähnte, dass dies tatsächlich ein bekanntes, gut untersuchtes Problem ist. Jedes lösbare Puzzle hat genau 4 Lösungen, und die Mehrheit der zufälligen Bretter ist nicht lösbar. Das Durchsuchen des gesamten Speicherplatzes mag Spaß machen, aber da es bereits einen Beweis gibt ( math.ksu.edu/math551/math551a.f06/lights_out.pdf ), können Sie auch ein paar Punktprodukte erstellen und in einigen Fällen die gleiche Antwort erhalten Mikrosekunden. :)
GrandOpener
Rechenzeit: Wenn Sie die Anzahl der unterschiedlichen Bretter (unabhängig von der Lösbarkeit) unter Berücksichtigung aller Symmetrien berechnen möchten, ist das Burnside-Lemma der richtige Weg: Es gibt 16 Symmetrien (eine Trivialität, drei Rotationen, vier Reflexionen und dann) jede dieser 8 kombiniert mit einer Inversion von Ein / Aus) und für jede dieser Symmetrien ist eine Anzahl von Platinen völlig unverändert. Wenn Sie den Durchschnitt von völlig unveränderten Brettern pro Symmetrie nehmen, entspricht dies der Anzahl unterschiedlicher Bretter.
Arthur
1
@PeterTaylor Das Codieren des Simulators dauert definitiv viel länger als das Ausführen der Ergebnisse.
corsiKa
4

Verallgemeinerte Antwort:

  1. Erstellen Sie eine Matrix mit der Größe (# Bewegungen) x (# Lichter).
  2. Fügen Sie eine 1 in eine Zelle ein, wenn Sie die dieser Zeile entsprechende Bewegung ausführen, um das dieser Spalte entsprechende Licht umzuschalten, ansonsten 0.
  3. Führen Sie die Gauß-Jordan-Eliminierung (Modulo 2) für die Matrix durch.
  4. Wenn die resultierende Matrix in jeder Spalte eine einzelne 1 und in jeder Zeile höchstens eine einzelne 1 hat, ist jedes Gitter lösbar.
Mark Tilford
quelle
1

Andere haben bereits erwähnt, wie Sie feststellen können, ob Ihr zufällig generiertes Puzzle lösbar ist. Die Frage, die Sie sich auch stellen sollten, ist, ob Sie tatsächlich zufällig generierte Rätsel wollen.

Zufällig generierte Rätsel haben alle den gleichen Kernfehler: Ihre Schwierigkeit ist ziemlich unvorhersehbar. Die möglichen Rätsel, die Sie bekommen können, reichen von bereits gelöst über trivial (Lösung ist offensichtlich) bis schwer (Lösung ist nicht offensichtlich) bis unmöglich (das Rätsel ist überhaupt nicht lösbar). Da die Schwierigkeit nicht vorhersehbar ist, ist die Erfahrung für den Spieler unbefriedigend, insbesondere wenn er mehrere Rätsel hintereinander löst. Es ist sehr unwahrscheinlich, dass sie eine gleichmäßige Schwierigkeitskurve bekommen, was sie je nach den Rätseln, die sie bekommen, gelangweilt oder frustriert machen kann.

Ein weiteres Problem bei der Zufallsgenerierung besteht darin, dass die Zeit, die zum Initialisieren des Puzzles benötigt wird, nicht vorhersehbar ist. Im Allgemeinen erhalten Sie (fast) sofort ein lösbares Rätsel. Mit etwas Pech können Ihre zufällig generierten Rätsel jedoch zu einer Reihe unlösbarer Rätsel führen.

Eine Möglichkeit, beides zu lösen, besteht darin, vordefinierte Vektoren für jedes lösbare Rätsel verfügbar zu haben, die in Schwierigkeitsgruppen eingeteilt sind, und dann ein zufälliges Rätsel aus den lösbaren Rätseln basierend auf der Schwierigkeit auszuwählen. Auf diese Weise können Sie sicher sein, dass jedes Rätsel lösbar ist, dass der Schwierigkeitsgrad vorhersehbar ist und dass die Erstellung in konstanter Zeit erfolgt.

Nzall
quelle