¿Cómo puedo saber si mi juego de rompecabezas siempre es posible?

68

He creado una especie de juego de rompecabezas en el que el objetivo es eliminar todas las fichas blancas. Puedes probarlo al final de la pregunta.

Cada vez, el tablero se genera aleatoriamente con fichas blancas en lugares aleatorios en una cuadrícula de 5 * 5. Puede hacer clic en cualquier mosaico de esa cuadrícula y alternará su color y todos los mosaicos que lo toquen en sus lados. Mi dilema es el hecho de que no sé si generará un tablero imposible. ¿Cuál es la mejor manera de verificar cosas como esta?

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
fuente
9
Si estás interesado en este tipo de juegos de rompecabezas, echa un vistazo a la colección de rompecabezas portátil de Simon Tatham . Además de este tipo (llamado Flip there), puedes encontrar variantes de muchos rompecabezas japoneses y otros. Todo está bajo licencia BSD y probablemente sea una lectura interesante.
Dubu
10
¿Qué tal la ingeniería inversa? Comience con un tablero en blanco, luego automatice, digamos 20 clics en cuadrados aleatorios. De esa manera, sabrá que debe haber una solución al final.
AJFaraday
3
Quiero seguir jugando, pero debido a tu pregunta, ¡la incertidumbre de si realmente ganaré o no me está comiendo! Juego divertido :)
MrDuk
@MrDuk codepen.io/qwertyquerty/pen/WMGwVW ¡ aquí está el proyecto terminado! Este es fijo y pulido. También hice una aplicación electrónica.
Qwerty
@Qwerty cuando intenté ver su Pen en la vista de página completa, recibí el mensaje "El propietario de este Pen necesita verificar su dirección de correo electrónico para habilitar la Vista de página completa". ¡Verifica tu dirección de correo electrónico en CodePen para que pueda disfrutar tu juego en la ventana completa! :)
stephenwade

Respuestas:

161

Este es el tipo de juego donde el mismo movimiento realizado dos veces invierte el tablero a su estado anterior. Por lo tanto, para garantizar que un tablero sea solucionable, generarlo jugando al revés. Comience con un tablero resuelto (en blanco), luego comience "haciendo clic" mediante programación aleatoriamente, ya sea un cierto número de veces, o hasta que el tablero tenga el número deseado de casillas blancas. Una solución es simplemente realizar los mismos movimientos en el orden inverso. Pueden existir otras soluciones más cortas, pero se garantiza que tendrá al menos una.

Otra solución mucho más compleja es definir un algoritmo de resolución que atraviese todos los estados posibles del juego desde su posición inicial para tratar de encontrar la solución. Esto llevaría mucho más tiempo implementarlo y ejecutarlo, pero permitiría que las placas se generen realmente al azar. No entraré en detalles de esta solución, porque simplemente no es una buena idea.

Ed Marty
fuente
22
@Qwerty: para su problema específico, hacer clic en el mismo cuadrado dos veces se cancela por sí mismo, por lo que nunca hay ninguna razón para hacer clic en ningún cuadrado más de una vez. Es posible que desee elegir un cierto número de cuadrados para hacer clic sin repetir, o considerar una solución que asigne un XX% de posibilidades de clic a cada cuadrado en el tablero. (Ed: ¡Buena respuesta, +1!)
Jeff Bowman
3
He hecho casi el mismo juego antes y terminé usando este enfoque. Incluí una animación al principio que muestra el estado resuelto yendo al estado no resuelto de manera rápida; era bonito.
Jared Goguen
1
@JaredGoguen extraño, agregué eso y volví aquí para ver tu comentario.
Qwerty
44
@JeffBowman De hecho, el conjunto de juegos solucionables se puede tratar como un valor de 25 bits, y cada bit corresponde a un cuadrado que es la cantidad de veces que se ha volteado el mod 2. Para poder generar un número aleatorio en el rango 0. .33,554,432 y luego calcule el valor de cada cuadrado en el tablero a partir de él en poco tiempo.
Monty Harder
77
Por lo que vale, si bien esta es la respuesta correcta a la pregunta matemática de cómo responder a este problema, esta suele ser una práctica dudosa desde el punto de vista del diseño. Este tipo de generación, sin ningún plan en particular, generalmente conduce a rompecabezas que se sienten muy "iguales", sin ningún punto de interés particular o ningún tema unificador. Es posible 'generar de manera procesal' instancias de problemas interesantes para un juego de rompecabezas, pero generalmente requiere una mirada mucho más difícil a cuáles son las características interesantes de sus rompecabezas.
Steven Stadnicki
92

Si bien las respuestas anteriores son inteligentes (y probablemente cómo lo haría de todos modos), este juego en particular es muy conocido. Se llama Lights Out y se ha resuelto matemáticamente. Hay una solución si y solo si dos sumas de varios elementos (dados en la página de wikipedia) se suman a cero mod 2 (es decir, un número par). En general, un poco de álgebra lineal debería dar condiciones de solución similares para los juegos en cualquier tablero.

Robert Mastragostino
fuente
2
Es un poco triste descubrir que ya está hecho. Pensé que estaba haciendo algo.
Qwerty
39
@Qwerty hay muy pocas ideas originales, y ciertamente no necesitas tener una para tener éxito (cf Rovio, King).
Deja de dañar a Monica
14
Este juego en particular existe, ¡pero siempre puedes ampliar la idea! Añadir más funciones! Agregue diferentes reglas para lo que sucede cuando hace clic en algún lugar, como colores que se suman según la dirección desde la que se activó / desactivó. Agregue diferentes "herramientas" que tiene que usar. Añadir tableros no rectangulares! Un montón de cosas divertidas para hacer. Solo recuerda que un movimiento siempre debe revertirse.
Ed Marty
77
@OrangeDog: Incluso 'Lights Out' no era original, esa es solo la marca que se hizo popular en los años 90. El artículo de Wikipedia, por ejemplo, enumera esto y esto
BlueRaja - Danny Pflughoeft
1
¿A qué respuestas se refiere como "las respuestas anteriores"? No está completamente claro, ya que en mi pantalla, solo hay una respuesta por encima de la suya. Recuerde que las respuestas cambian el orden según los votos y las opciones del usuario. Siempre debe vincular a respuestas específicas en lugar de referirse a algo "arriba".
David Richerby
13

Dé la vuelta al generar su rompecabezas.

En lugar de seleccionar aleatoriamente los mosaicos y convertirlos de blanco a negro, comience desde una pizarra en blanco, luego seleccione los mosaicos, pero en lugar de convertir ese mosaico en negro, hágalo como si el usuario lo hubiera seleccionado, dando como resultado voltear todos los otros mosaicos alrededor.

De esta manera, se le garantizará tener al menos una solución: el usuario tendrá que deshacer lo que hizo su jugador "AI" para crear el nivel.

Vaillancourt
fuente
7

Ed y Alexandre tienen derecho.

Pero si usted no quiere saber si cada solución es posible, hay maneras.

Hay un número finito de rompecabezas posibles

Hacer clic en el mismo cuadrado dos veces produce el mismo resultado que no hacer clic en él, sin importar cuántos clics se hayan hecho entre ellos. Eso significa que cada solución se puede describir dando a cada cuadrado un valor binario de 'clic' o 'no clic'. Del mismo modo, cada rompecabezas se puede describir dando a cada cuadrado un valor binario de 'activado' o 'no activado'. Eso significa que hay 2 ^ 25 posibles acertijos y 2 ^ 25 posibles soluciones. Si puede probar que cada solución resuelve un rompecabezas único, entonces debe haber una solución para cada rompecabezas. Del mismo modo, si encuentra dos soluciones que resuelven el mismo rompecabezas, entonces no puede haber una solución para cada rompecabezas.

Además, 2 ^ 25 es 33,554,432. Eso es bastante, pero no es un número inmanejable. Un buen algoritmo y una computadora decente probablemente podrían aplicar una fuerza bruta en un par de horas, especialmente cuando consideras que la mitad de los rompecabezas son inversos de la otra mitad.

Lupus arcanista
fuente
44
Más de la mitad son "inversas": además de los reflejos horizontales, tiene reflejos y rotaciones verticales.
Clockwork-Muse
@ Clockwork-Muse, sí, pero es más difícil calcular un número exacto porque, si bien los diseños asimétricos se pueden rotar y voltear en 8 permutaciones, los diseños simétricos tienen menos permutaciones. Así que solo mencioné la inversión blanco / negro, ya que cada solución tiene exactamente 1 inversa. (Aunque para que ese inverso funcione, tienes que demostrar que puedes voltear todo el tablero)
Arcanist Lupus
Resulta que, como Robert Mastragostino mencionó en su respuesta, este es realmente un problema bien conocido y bien estudiado. Cada rompecabezas solucionable tiene exactamente 4 soluciones, y la mayoría de los tableros aleatorios no tienen solución. Buscar todo ese espacio puede ser divertido, pero dado que ya existe una prueba ( math.ksu.edu/math551/math551a.f06/lights_out.pdf ) también podría hacer un par de productos de puntos y tener la misma respuesta en unos pocos microsegundos :)
GrandOpener
Tiempo matemático: si desea calcular el número de tableros distintos (independientemente de la capacidad de solución), teniendo en cuenta todas las simetrías, entonces el lema de Burnside es el camino a seguir: hay 16 simetrías (una trivial, tres rotaciones, cuatro reflexiones y luego cada uno de esos 8 combinados con inversión de encendido / apagado), y para cada una de esas simetrías, cierto número de tableros no cambia por completo. Si toma el promedio de tablas sin cambios por simetría, es igual a la cantidad de tablas distintas.
Arthur
1
@PeterTaylor Definitivamente llevará más tiempo codificar el simulador que ejecutar los resultados.
corsiKa
4

Respuesta generalizada:

  1. Cree una matriz de tamaño (# movimientos) x (# luces).
  2. Ponga un 1 en una celda si el movimiento correspondiente a esa fila alterna esa luz correspondiente a esa columna, 0 de lo contrario.
  3. Realice la eliminación de Gauss-Jordan (módulo 2) en la matriz.
  4. Si la matriz que resulta tiene un solo 1 en cada columna, y cada fila tiene como máximo un solo 1, entonces cada cuadrícula se puede resolver.
Mark Tilford
fuente
1

Otros ya han mencionado formas de determinar si su rompecabezas generado aleatoriamente tiene solución. Sin embargo, la pregunta que también debes hacerte es si realmente quieres rompecabezas generados al azar.

Todos los rompecabezas generados aleatoriamente tienen el mismo defecto central: su dificultad es prácticamente impredecible. Los posibles acertijos que puede obtener pueden variar desde ya resueltos, a triviales (la solución es obvia) a difíciles (la solución no es obvia) a imposibles (el rompecabezas no se puede resolver en absoluto). Debido a que la dificultad es impredecible, se convierte en una experiencia insatisfactoria para el jugador, especialmente si hacen múltiples rompecabezas seguidos. Es muy poco probable que obtengan una curva de dificultad suave, lo que puede aburrirlos o frustrarlos dependiendo de los acertijos que obtengan.

Otro problema de la generación aleatoria es que el tiempo que tarda el rompecabezas en inicializarse es impredecible. En términos generales, obtendrá un rompecabezas solucionable (casi) de inmediato, pero con algo de mala suerte, sus rompecabezas generados al azar podrían terminar en una racha de rompecabezas sin solución.

Una forma de resolver ambos es tener vectores predefinidos de cada rompecabezas solucionable disponible, organizados en grupos de dificultad, y luego seleccionar un rompecabezas aleatorio de los acertijos solucionables en función de la dificultad. De esta manera, estará seguro de que cada rompecabezas es solucionable, que la dificultad es predecible y que la generación se realizará en tiempo constante.

Nzall
fuente