Comment savoir si mon jeu de réflexion est toujours possible?

68

J'ai créé une sorte de jeu de puzzle dans lequel l'objectif est de se débarrasser de toutes les tuiles blanches. Vous pouvez l'essayer à la fin de la question.

À chaque fois, le tableau est généré de manière aléatoire avec des carreaux blancs à des emplacements aléatoires sur une grille 5 * 5. Vous pouvez cliquer sur n’importe quelle tuile de cette grille et celle-ci changera de couleur et toutes les tuiles le toucheront sur les côtés. Mon dilemme est le fait que je ne sais pas si cela va générer un conseil impossible. Quel est le meilleur moyen de vérifier de telles choses?

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
la source
9
Si vous êtes intéressé par ce type de jeux de réflexion, jetez un œil à la collection de casse-tête portables de Simon Tatham . En dehors de ce type (appelé Flip là-bas), vous pouvez trouver des variantes de nombreux puzzles japonais et autres. Tout est sous licence BSD et probablement une lecture intéressante.
Dubu
10
Qu'en est-il de l'ingénierie inverse? Commencez avec un tableau vide, puis automatisez, disons 20 clics sur des carrés aléatoires. De cette façon, vous savez qu'il doit y avoir une solution à la fin.
AJFaraday
3
Je veux continuer à jouer, mais à cause de votre question, l’incertitude de savoir si je gagnerai ou non me rongera! Jeu amusant :)
MrDuk
@MrDuk codepen.io/qwertyquerty/pen/WMGwVW voici le projet terminé! Celui-ci est corrigé et poli. J'ai aussi fait une application électronique.
Qwerty
@ Qwerty, lorsque j'ai essayé de visualiser votre stylo en mode pleine page, le message "Le propriétaire de ce stylo doit vérifier son adresse électronique pour activer l'affichage de la page complète". Veuillez vérifier votre adresse e-mail sur CodePen pour que je puisse profiter de votre jeu dans la pleine fenêtre! :)
stephenwade

Réponses:

161

C'est le type de jeu où le même coup effectué deux fois fait revenir le tableau à son état précédent. Donc, pour que le tableau soit résoluble, générez-le en jouant à l'envers. Commencez par un tableau résolu (vierge), puis démarrez par programme en "cliquant" de manière aléatoire, soit un certain nombre de fois, soit jusqu'à ce que le tableau dispose du nombre souhaité de carrés blancs. Une solution consiste alors simplement à effectuer les mêmes mouvements dans l’ordre inverse. D'autres solutions plus courtes peuvent exister, mais vous êtes assuré d'en avoir au moins une.

Une autre solution, beaucoup plus complexe, consiste à définir un algorithme de résolution qui passe par tous les états de jeu possibles à partir de votre position de départ pour essayer de trouver la solution. Cela prendrait beaucoup plus de temps à mettre en œuvre et à exécuter, mais permettrait aux cartes d'être réellement générées de manière aléatoire. Je n'entrerai pas dans les détails de cette solution, car ce n'est tout simplement pas une bonne idée.

Ed Marty
la source
22
@ Qwerty: pour votre problème spécifique, cliquer deux fois sur la même case s'annule, il n'y a donc aucune raison de cliquer plus d'une fois sur une case. Vous pouvez choisir un certain nombre de carrés à cliquer sans répéter, ou envisager une solution qui attribue une chance de clic de XX% à chaque carré du tableau. (Ed: Belle réponse, +1!)
Jeff Bowman
3
J'ai fait presque exactement le même jeu auparavant et j'ai fini par utiliser cette approche. J'ai inclus une animation au début montrant rapidement l'état résolu et l'état non résolu; c'était joli.
Jared Goguen
1
@ JaredGoguen impair, j'ai ajouté cela et je suis revenu ici pour voir votre commentaire.
Qwerty
4
@JeffBowman En effet, l'ensemble des jeux pouvant être résolus peut être traité comme une valeur de 25 bits, chaque bit correspondant à un carré correspondant au nombre de fois où il a été retourné mod 2. On peut donc générer un nombre aléatoire compris dans l'intervalle 0. .33,554,432 et ensuite calculer la valeur de chaque carré sur le tableau à partir de celui-ci dans un ordre court.
Monty Harder
7
Pour ce que cela vaut, bien que ce soit la bonne réponse à la question mathématique de savoir comment répondre à ce problème, il s’agit généralement d’une pratique douteuse du point de vue de la conception. Ce type de génération, sans aucun plan particulier, conduit généralement à des énigmes très «identiques», sans points d’intérêt particuliers ni thèmes fédérateurs. Il est possible de «générer de manière procédurale» des instances de problèmes intéressantes pour un jeu de puzzle, mais cela nécessite généralement un examen beaucoup plus difficile des fonctionnalités intéressantes de vos puzzles.
Steven Stadnicki
92

Bien que les réponses ci-dessus soient intelligentes (et probablement comment je le ferais de toute façon), ce jeu est très connu. Cela s'appelle Lights Out et a été résolu mathématiquement. Il existe une solution si et seulement si deux sommes d'éléments différents (indiquées sur la page wikipedia) s'ajoutent à zéro mod 2 (c'est-à-dire un nombre pair). En général, un peu d'algèbre linéaire devrait donner des conditions de solution similaires pour les jeux sur n'importe quel tableau.

Robert Mastragostino
la source
2
C'est un peu triste de découvrir que cela a déjà été fait. Je pensais que j'étais sur quelque chose.
Qwerty
39
@ Qwerty, il y a très peu d'idées originales, et vous n'avez certainement pas besoin d'en avoir une pour réussir (cf Rovio, King).
Cessez de nuire à Monica le
14
Ce jeu existe, mais vous pouvez toujours développer l’idée! Ajouter plus de fonctionnalités! Ajoutez des règles différentes pour ce qui se passe lorsque vous cliquez quelque part, comme les couleurs qui s'additionnent en fonction de la direction dans laquelle il a été activé / désactivé. Ajoutez différents «outils» que vous devez utiliser. Ajoutez des tableaux non rectangulaires! Beaucoup de choses amusantes à faire. Rappelez-vous simplement qu'un mouvement doit toujours s'inverser.
Ed Marty
7
@OrangeDog: Même 'Lights Out' n'était pas original, c'est juste le nom de marque qui est devenu populaire dans les années 90. L'article de Wikipédia, par exemple, énumère ceci et cela
BlueRaja - Danny Pflughoeft le
1
Quelles réponses faites-vous référence comme "les réponses ci-dessus"? C'est complètement obscur, car sur mon écran, il n'y a qu'une réponse au dessus de la vôtre. N'oubliez pas que les réponses changent d'ordre en fonction des votes et des options de l'utilisateur. Vous devriez toujours faire un lien vers des réponses spécifiques au lieu de faire référence à quelque chose "ci-dessus".
David Richerby
13

Faites l'inverse pour générer votre puzzle.

Au lieu de sélectionner au hasard les carreaux et de les passer du blanc au noir, commencez par une ardoise vierge, puis sélectionnez les carreaux, mais au lieu de noircir ce carreau, faites-le comme si l'utilisateur l'avait sélectionné, ce qui ferait basculer tous les autres carreaux. autour de.

De cette façon, vous aurez la garantie d’avoir au moins une solution: l’utilisateur devra annuler ce que votre joueur "IA" a fait pour créer le niveau.

Vaillancourt
la source
7

Ed et Alexandre en ont le droit.

Mais si vous ne voulez savoir si chaque solution est possible, il existe des moyens.

Il y a un nombre fini de puzzles possibles

En cliquant deux fois sur le même carré, on obtient le même résultat que de ne pas cliquer dessus, quel que soit le nombre de clics enregistrés. Cela signifie que chaque solution peut être décrite en attribuant à chaque carré une valeur binaire «cliqué» ou «non cliqué». De même, chaque casse-tête peut être décrit en attribuant à chaque carré une valeur binaire «basculée» ou «non basculée». Cela signifie qu'il y a 2 ^ 25 énigmes possibles et 2 ^ 25 solutions possibles. Si vous pouvez prouver que chaque solution résout un casse-tête unique, il doit exister une solution à chaque casse-tête. De même, si vous trouvez deux solutions qui résolvent le même casse-tête, il ne peut y avoir de solution à chaque casse-tête.

En outre, 2 ^ 25 est 33,554,432. C'est beaucoup, mais ce n'est pas un nombre ingérable. Un bon algorithme et un ordinateur correct pourraient probablement avoir une force brute d’ici quelques heures, en particulier si l’on considère que la moitié des énigmes sont des inverses de l’autre.

Lupus d'arcaniste
la source
4
Plus de la moitié sont des "inverses" - outre les réflexions horizontales, vous avez des réflexions verticales et des rotations.
Clockwork-Muse
@ Clockwork-Muse, oui, mais il est plus difficile de calculer un nombre exact car, alors que les conceptions asymétriques peuvent être pivotées et inversées selon 8 permutations, les conceptions symétriques ont moins de permutations. J'ai donc seulement mentionné l'inversion blanc / noir, car chaque solution a exactement 1 inverse. (Bien que pour que l'inverse fonctionne, vous devez prouver que vous pouvez retourner le tableau entier)
Arcanist Lupus
Comme le disait Robert Mastragostino dans sa réponse, il s’avère qu’il s’agit en fait d’un problème bien connu et bien étudié. Chaque casse-tête soluble a exactement 4 solutions et la majorité des tableaux aléatoires ne peuvent pas être résolus. Rechercher dans tout cet espace peut sembler amusant, mais comme il existe déjà une preuve ( math.ksu.edu/math551/math551a.f06/lights_out.pdf ), vous pouvez également créer quelques produits scalaires et obtenir la même réponse dans quelques cas. microsecondes. :)
GrandOpener
Temps mathématique: Si vous voulez calculer le nombre de planches distinctes (quelle que soit la solvabilité), en tenant compte de toutes les symétries, le lemme de Burnside est la solution: il y a 16 symétries (une triviale, trois rotations, quatre réflexions, puis chacune de ces 8 combinées avec l'inversion d'activation / désactivation), et pour chacune de ces symétries, un certain nombre de cartes sont totalement inchangées. Si vous prenez la moyenne de conseils entièrement inchangés par symétrie, cela équivaut au nombre de conseils distincts.
Arthur
1
@ PeterTaylor Il faudra beaucoup plus de temps pour coder le simulateur que pour exécuter les résultats.
CorsiKa
4

Réponse généralisée:

  1. Créez une matrice de taille (# déplacements) x (# lumières).
  2. Mettez un 1 dans une cellule si le déplacement correspondant à cette ligne bascule la lumière correspondant à cette colonne, sinon, 0.
  3. Effectuer l'élimination de Gauss-Jordan (modulo 2) sur la matrice.
  4. Si la matrice qui en résulte a un seul 1 dans chaque colonne et que chaque ligne en a au plus un, chaque grille est résolvable.
Mark Tilford
la source
1

D'autres ont déjà mentionné des moyens de déterminer si votre puzzle généré de manière aléatoire peut être résolu. La question que vous devriez également vous poser cependant est de savoir si vous voulez réellement des énigmes générés aléatoirement.

Les puzzles générés aléatoirement ont tous le même défaut fondamental: leur difficulté est quasiment imprévisible. Les énigmes possibles peuvent aller de déjà résolues à triviales (la solution est évidente) à difficiles (la solution n'est pas évidente) à impossibles (le casse-tête ne peut pas être résolu du tout). Parce que la difficulté est imprévisible, cela rend le joueur peu satisfaisant, surtout s'il fait plusieurs énigmes à la suite. Il est très peu probable qu'ils obtiennent une courbe de difficulté fluide, ce qui peut les ennuyer ou les frustrer selon les énigmes qu'ils rencontrent.

Un autre problème de la génération aléatoire est que le temps nécessaire à l'initialisation du puzzle est imprévisible. En règle générale, vous obtiendrez (presque) immédiatement une énigme que vous pourrez résoudre, mais avec un peu de malchance, vos énigmes générées aléatoirement risquent de se retrouver sur une série de énigmes insolubles.

Une façon de résoudre ces deux problèmes consiste à disposer de vecteurs prédéfinis de chaque puzzle résoluble disponibles, classés en groupes de difficulté, puis de sélectionner un puzzle aléatoire parmi les puzzles résolvables en fonction de la difficulté. De cette façon, vous serez certain que chaque casse-tête est résoluble, que la difficulté est prévisible et que la génération se fera dans un temps constant.

Nzall
la source