Mahjong: organiza los mosaicos para garantizar al menos un camino hacia la victoria, independientemente del diseño

Question

Independientemente del diseño que se use para los mosaicos, ¿hay alguna buena manera de dividir los mosaicos para que pueda garantizarle al usuario que, al comienzo del juego, existe al menos un camino para completar el rompecabezas y ganando el juego?

Obviamente, dependiendo de los movimientos del usuario, pueden evitar ganar. Solo quiero poder decirle siempre al usuario que el rompecabezas se puede ganar si juega bien.

Si colocas fichas al azar al comienzo del juego, es posible que el usuario pueda hacer algunos movimientos y no pueda hacer más. El conocimiento de que un rompecabezas es al menos solucionable debería hacerlo más divertido de jugar.

Answer 1

Coloque todos los mosaicos en reversa (es decir, diseñe el tablero comenzando en el medio, trabajando)

Para provocar más al jugador, puedes hacerlo de forma visible pero a muy alta velocidad.

Answer 2

Juega el juego al revés.

Coloque aleatoriamente las piezas par por par, en lugares donde pueda deslizarlas en el montón. Necesitará una forma de saber dónde se le permite colocar piezas para terminar con un montón que coincida con algún patrón preestablecido, pero lo necesitaría de todos modos.

Answer 3

Sé que esta es una vieja pregunta, pero me encontré con esto cuando resolví el problema yo mismo. Ninguna de las respuestas aquí es del todo perfecta, y varias de ellas tienen advertencias complicadas o se romperán en diseños patológicos. Aquí está mi solución:

Resuelve el tablero (hacia adelante, no hacia atrás) con fichas sin marcar. Retire dos fichas libres a la vez. Empuje cada par que elimine en un "par coincidente" apilar. A menudo, esto es todo lo que necesitas hacer.

Si se encuentra con un callejón sin salida (numFreeTiles == 1), simplemente reinicie su generador :) He descubierto que generalmente no llego a callejones sin salida, y hasta ahora tengo un recuento máximo de reintentos de 3 para el 10- más o menos diseños que he probado. Una vez que llego a 8 intentos, me doy por vencido y solo asigno al azar el resto de las fichas. Esto me permite usar el mismo generador para configurar el tablero y la función de barajar, incluso si el jugador se equivocó y logró un estado 100% insoluble.

Otra solución cuando llegas a un callejón sin salida es retroceder (retira la pila, reemplazando las fichas en el tablero) hasta que puedas tomar un camino diferente. Tome un camino diferente asegurándose de hacer coincidir los pares que eliminarán el mosaico de bloqueo original.

Desafortunadamente, dependiendo del tablero, esto puede repetirse para siempre. Si termina eliminando un par que se asemeja a un " sin salida " carretera, donde todas las "carreteras" posteriores son un callejón sin salida, y hay múltiples callejones sin salida, su algoritmo nunca se completará. No sé si es posible diseñar una placa donde este sería el caso, pero si es así, todavía hay una solución.

Para resolver ese problema mayor, trate cada posible estado de la placa como un nodo en un DAG, con cada par seleccionado como un borde en ese gráfico. Haga un recorrido aleatorio, hasta que encuentre un nodo de hoja en la profundidad 72. Mantenga un registro de su historial de recorrido para que nunca repita un descenso.

Dado que los callejones sin salida son más raros que las soluciones de primer intento en los diseños que he usado, lo que viene a mi mente de inmediato es una solución híbrida. Primero intente resolverlo con una memoria mínima (almacene los pares seleccionados en su pila). Una vez que haya alcanzado el primer callejón sin salida, degrade a hacer la generación completa de marcado / borde al visitar cada nodo (evaluación diferida cuando sea posible).

Sin embargo, he estudiado muy poco la teoría de gráficos, así que tal vez haya una mejor solución para el problema de búsqueda / recorrido aleatorio DAG :)

Editar: En realidad, podría usar cualquiera de mis soluciones con la generación de la placa a la inversa, hasta el 13 de octubre de 2008. Todavía tienes las mismas advertencias, porque aún puedes terminar con callejones sin salida. Sin embargo, generar un tablero a la inversa tiene reglas más complicadas. Por ejemplo, se garantiza que fallará su configuración si no comienza al menos ALGUNAS de sus filas con la primera pieza en el medio, como en un diseño con 1 fila larga. Elegir un primer movimiento completamente aleatorio (legal) en un generador de resolución hacia adelante es más probable que conduzca a un tablero solucionable.

Answer 4

Lo único que he podido encontrar es colocar las fichas en pares iguales como una especie de juego de Mahjong Solitario inverso. Entonces, en cualquier momento durante la colocación de las fichas, el tablero debería verse como si estuviera en el medio de un juego real (es decir, no hay fichas flotando 3 capas por encima de otras fichas).

Si las fichas se colocan en pares iguales en un juego inverso, siempre debe dar como resultado al menos un camino hacia adelante para resolver el juego.

Me encantaría escuchar otras ideas.

Answer 5

Creo que la mejor respuesta ya ha sido impulsada hacia arriba: crear un conjunto resolviéndolo "a la inversa" - es decir, comenzar con un tablero en blanco, luego agregar un par en alguna parte, agregar otro par en una posición que se pueda resolver, y así sucesivamente ...

Si prefiere "Big Bang" enfoque (generando todo el conjunto al azar al principio), eres un desarrollador muy macho o simplemente te sientes masoquista hoy, podrías representar todos los pares que puedes sacar del conjunto dado y cómo dependen de cada uno otro a través de un gráfico dirigido.

A partir de ahí, solo tendría que obtener el cierre transitivo de ese conjunto y determinar si hay al menos una ruta de al menos uno de los pares legales iniciales que conduzca al final deseado (no quedan pares de mosaicos).

La implementación de esta solución se deja como un ejercicio para el lector: D

Answer 6

Estas son las reglas que utilicé en mi implementación.

Al construir el montón, para cada traste en un par por separado, encuentre celdas (lugares), que son:

• tiene todas las celdas en niveles inferiores ya llenas
• el lugar para el segundo traste no se bloquea primero, teniendo en cuenta si el primer traste ya está a bordo
• ambos lugares están "en los bordes" del montón ya construido:
  • CUALQUIERA tiene al menos un vecino en el lado izquierdo o derecho
  • O es el primer traste en una fila (todas las celdas a la derecha y a la izquierda están recursivamente libres)

Estas reglas no garantizan que una compilación siempre tenga éxito: a veces deja que las últimas 2 celdas libres se autobloqueen, y la compilación debe volverse a intentar (o al menos unos pocos trastes) En la práctica, "tortuga" incorporado en no más de 6 reintentos.

La mayoría de los juegos existentes parecen restringir los primeros trastes (" primero en la fila ") en algún punto intermedio. Esto viene con configuraciones más convenientes, cuando no hay trastes en los bordes de filas muy largas, permaneciendo hasta el último jugador se mueve. Sin embargo, "medio" es diferente para diferentes configuraciones.

Buena suerte :)

P.S. Si ha encontrado algo que construye un montón solucionable en un turno, hágamelo saber.

Answer 7

Tienes 144 fichas en el juego, cada una de las 144 fichas tiene una lista de bloqueo. (el mosaico superior de la pila tiene una lista de bloque vacía)

Todos los movimientos válidos requieren que su " current__vertical_Block_list " estar vacío ... esto puede ser una matriz de 144x144, por lo que 20k de memoria más una lista de bloqueo IZQUIERDA y DERECHA, también 20 k cada una.

Genere una tabla de movimiento válida desde (remaning_tiles) AND ((LISTA DE BLOQUEO VERTICAL ACTUAL vacía) y ((LISTA DE BLOQUEO IZQUIERDA ACTUAL vacía) O (LISTA DE BLOQUEO CORRIENTE CORRIENTE DERECHA)))

Elige 2 fichas aleatorias de la tabla de movimiento válida, regístralas Actualice las (tablas actuales Vert, izquierda y derecha), registre los mosaicos eliminados en una pila

Ahora tenemos una lista de movimientos que constituyen un juego válido. Asigne tipos de fichas coincidentes a cada uno de los 72 movimientos.

para juegos desafiantes, rastrea cuando cada ficha esté disponible. buscar conjuntos que tienen son (temprano temprano temprano tarde) y (tarde tarde tarde temprano temprano) ya que está en blanco, encuentra 1 bloques EE 1 LL y 2 LE ... del bloque 2 LE, encuentre un TEMPRANO que bloquea CUALQUIER otro TEMPRANO que ( excepto bloquear a la derecha una pieza del lado izquierdo)
Una vez que tenga un juego válido, juegue con el pedido.

Answer 8

Solitario? Solo una suposición, pero supongo que su computadora necesitaría vencer al juego (o cerca de él) para determinar esto.

Otra opción podría ser tener varios diseños preestablecidos (que permiten ganar, mezclado con su nivel actual.

Hasta cierto punto, puede intentar asegurarse de que uno de los 4 mosaicos no sea más que X capas debajo de otra X.

La mayoría de los juegos que veo tienen el comando shuffle para cuando alguien se atasca.

Probaría una combinación de cosas y vería qué funciona mejor.