Estructura/algoritmo para resolver juego con cartas superpuestas

Question

Considere un juego de cartas como Tower Solitaire, Tripeaks o Fairway Solitaire: la tabla consiste en un número de cartas que están disponibles de inmediato, cada una de las cuales puede cubrir otras cartas debajo (impidiéndoles jugar). Tienes una carta de "fundación", y puedes quitar una carta de la mesa si es exactamente un rango por encima o por debajo de tu carta de fundación, en ese punto se convierte en tu nueva carta de fundación. Tienes un número limitado de cartas de reemplazo para sacar cuando no puedes jugar una carta de la mesa, por lo que generalmente quieres jugar la mayor cantidad posible de cartas.

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

Ejemplo:

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

Tarjetas en las tarjetas bloque inferior en la parte superior de ser eliminado: no se puede eliminar 4a hasta que ambos 3 y 2 se han ido. Suponiendo que su carta inicial es un as, la jugada óptima aquí sería 2, 3, 4b, 5, 4a. (Podría jugar 2, 3, 4a en su lugar, pero eso no es tan bueno.)

Supongo que esto debería representarse como un tipo de gráfico dirigido. Tendría bordes de 3 y 2 a 4a y de 2 y 4b a 5, pero también tendría bordes entre 3 y 2 y entre 4a y 5, ya que uno se puede reproducir después del otro? De ser así, ¿el hecho de que se puedan reproducir en cualquier orden (3, luego 2 o 2, luego 3) forma un ciclo en el gráfico que le impide utilizar los algoritmos eficientes de "ruta más larga"? (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 de estados de juego (con posibles estados siguientes calculados sobre la marcha) - eso no tiene bucles, lo que significa que es un DFS directo en los estados potenciales del juego (que podría ser bastante numeroso) desde el punto de inicio.

Answer 2

El objetivo es construir un gráfico acíclico dirigido con el menor número posible de nodos, cuyos nodos capturarían completamente el espacio de estado del problema. Entonces puedes ejecutar tu algoritmo habitual.

Sugiero una codificación basada en la forma de la estructura de las cartas restantes en la mesa.

Los primeros datos en el estado podrían ser la identificación única de la tarjeta que se encuentra más a la izquierda. (como 4a, por ejemplo, es único en el sentido de que solo hay una carta 4a). El resto de la forma se puede representar con -1,0,1 por cada tarjeta disponible (tarjeta que está lista para tomarse) que describe si la siguiente carta a la izquierda está en el mismo "nivel" o es un nivel más profundo o más alto. (Esto explota la suposición de que una carta solapa solo 2 otras tarjetas y que la estructura se parece a la que usted ha dado en el ejemplo).