Estructura / algoritmo para resolver juego con cartas superpuestas

Question

Considere un juego de cartas en la línea de la torre solitario, Tripeaks o Fairway Solitaire: la mesa consta de un número de tarjetas que están disponibles de inmediato, cada una de las cuales podría estar cubriendo otras tarjetas por debajo de ella (bloquearlos de ser jugado) . Usted tiene una tarjeta de "fundamento", y se puede eliminar una tarjeta de la mesa si es exactamente un rango por encima o por debajo de su tarjeta de fundación, y en ese momento se convierte en su nueva tarjeta de fundación. Usted tiene un número limitado de tarjetas de reemplazo para sacar de cuando no se puede jugar una carta de la mesa, por lo que generalmente quiere reproducir la secuencia más larga de cartas posible.

En primer lugar, ¿cómo representar a la junta para facilitar la búsqueda de una solución? En segundo lugar, ¿qué algoritmo usaría para encontrar la secuencia más larga jugable?

Ejemplo:

  -4a- -5-
-3-  -2- -4b-

Las cartas sobre las cartas del bloque de fondo en la parte superior de ser eliminado: no se pueden eliminar 4a hasta que ambos 3 y 2 se han ido. Asumiendo que su tarjeta de partida es un as, el juego óptimo aquí sería 2, 3, 4b, 5, 4a. (Se puede jugar 2, 3, 4A lugar, pero eso no es tan bueno.)

supongo que esto debe ser representado como una especie de gráfico dirigido. Se podría tener bordes de 3 y 2 a 4a y 4b de 2 y hasta 5, pero podría también tener bordes entre 3 y 2 y entre 4a y 5, ya que uno se puede jugar detrás de otro? Si es así, sería el hecho de que se pueden reproducir en cualquier orden (3 y luego 2 o 2 y luego 3) forman un ciclo en el gráfico que le impide utilizar los algoritmos eficientes "camino más largo"? (Creo que encontrar el camino más largo en un gráfico es NP-completo si el gráfico contiene ciclos.)

Answer 1

¿Qué pasa si usted representa esto como un gráfico del juego-estado (con posibles próximos estados calculados sobre la marcha) - que no tendrá bucles, lo que significa que es un DFS recto en los estados posibles del juego (que podría ser bastante numerosos todavía) desde el punto de inicio.

Answer 2

El punto es construir un gráfico acíclico dirigido con los nodos menor número posible, cuyos nodos capturaría plenamente el espacio de estado del problema. A continuación, puede ejecutar el algoritmo habitual.

I sugieren una codificación basada en la forma de la estructura de las cartas que quedan en la mesa.

Los primeros datos en el estado podría ser el ID único de la izquierda - carta superior. (Como 4a por ejemplo, es única en el sentido de que sólo hay una tarjeta 4a). El resto de la forma puede ser representado por una de -1,0,1 para cada tarjeta disponible (tarjeta que está listo para ser tomado) que describe si la carta siguiente a la izquierda está en el mismo 'nivel' o es un nivel más profunda o más alto. (Esta es la explotación de la suposición de que una tarjeta se superpone sólo 2 otras tarjetas y que la estructura se parece a la que usted ha dado en el ejemplo).