Estrutura / algoritmo para resolver jogo de cartas sobrepostas

Question

Considere um jogo de cartas ao longo das linhas de Torre Solitaire, Tripeaks, ou Fairway Solitaire: a mesa é composta por um certo número de cartões que estão imediatamente disponíveis, cada um dos quais pode ser relativas a outros cartões debaixo dela (impedindo-os de que está sendo jogado) . Você tem um cartão de "fundação", e você pode remover um cartão da mesa se é exatamente uma posição acima ou abaixo de seu cartão de fundação, altura em que se torna o seu novo cartão de fundação. Você tem um número limitado de cartões de substituição para desenhar a partir de quando você não pode jogar uma carta da mesa, para que você geralmente quer jogar a mais longa sequência de cartas possíveis.

Em primeiro lugar, como você representam a bordo para facilitar a busca de uma solução? Em segundo lugar, o algoritmo que você usaria para encontrar a seqüência jogável mais longo?

Exemplo:

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

Cartões nos cartões bloco inferior em cima de ser removido: você não pode remover 4a até que ambos 3 e 2 são ido. Assumindo que o seu cartão de partida é um ás, o jogo ideal aqui seria 2, 3, 4b, 5, 4a. (Você poderia jogar 2, 3, 4a vez, mas isso não é tão bom.)

Acho que isso deve ser representado como um tipo de grafo dirigido. Você teria bordas de 3 e 2 a 4a e de 2 e 4-B a 5, mas você também tem bordas entre 3 e 2 e entre a 4a e 5, já que um é jogável após o outro? Se assim for, seria o fato de que eles podem ser jogados em qualquer ordem (3, em seguida, 2, ou 2, em seguida, 3) formam um ciclo no grafo que impede que você use os eficientes algoritmos "caminho mais longo"? (Eu acredito que encontrar o caminho mais longo em um grafo é NP-completo se o gráfico contém ciclos.)

Answer 1

E se você representa isso como um gráfico do jogo-estados (com potenciais estados próximos computados on the fly) - que não terá loops, ou seja, é um DFS retas sobre os estados potenciais do jogo (que poderia ser bastante numerosos ainda) a partir do ponto de início.

Answer 2

O objetivo é construir um gráfico acíclico dirigido com o menor número de nós de possíveis, cujos nós iria capturar totalmente o espaço de estados do problema. Em seguida, você pode executar o seu algoritmo de costume.

I sugerem uma codificação com base na forma da estrutura das restantes cartas na mesa.

Os primeiros dados no estado poderia ser a identificação única da mais à esquerda - Cartão superior. (Como 4a por exemplo, ele é único no sentido de que há apenas um cartão 4a). O resto da forma pode ser representado por um dos -1,0,1 para cada cartão disponível (cartão que está pronto para ser tomado) descrevendo se o cartão seguinte à esquerda está no mesmo 'nível' ou é um nível mais profunda ou mais elevada. (Isto é explorar a hipótese de que um cartão sobrepõe apenas 2 outros cartões e que os olhares estrutura como a que você tem dado no exemplo).