Structure/algorithm for solving game with overlapping cards

Question

Consider a card game along the lines of Tower Solitaire, Tripeaks, or Fairway Solitaire: the table consists of some number of cards which are immediately available, each of which might be covering other cards underneath it (blocking them from being played). You have one "foundation" card, and you can remove a card from the table if it's exactly one rank above or below your foundation card, at which point it becomes your new foundation card. You have a limited number of replacement cards to draw from when you can't play a card from the table, so you generally want to play the longest sequence of cards possible.

First, how would you represent the board to facilitate finding a solution? Second, what algorithm would you use to find the longest playable sequence?

Example:

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

Cards on the bottom block cards on top from being removed: you can't remove 4a until both 3 and 2 are gone. Assuming your starting card is an ace, the optimal play here would be 2, 3, 4b, 5, 4a. (You could play 2, 3, 4a instead, but that's not as good.)

I suppose this should be represented as some kind of directed graph. You'd have edges from 3 and 2 to 4a and from 2 and 4b to 5, but would you also have edges between 3 and 2 and between 4a and 5, since one is playable after the other? If so, would the fact that they can be played in either order (3 then 2, or 2 then 3) form a cycle in the graph that prevents you from using the efficient "longest path" algorithms? (I believe finding the longest path in a graph is NP-complete if the graph contains cycles.)

Answer 1

What if you represent this as a graph of game-states (with potential next states computed on the fly) - that will not have loops, meaning it's a straight DFS on the potential states of the game (which could be quite numerous still) from the start point.

Answer 2

The point is to construct a directed acyclic graph with the fewest nodes possible, whose nodes would fully capture the state space of the problem. Then you can run your usual algorithm.

I suggest an encoding based on the shape of the structure of the remaining cards at the table.

The first data in the state could be the unique ID of the leftmost - topmost card. (like 4a for example, it is unique in a sense that there is only one card 4a). The rest of the shape can be represented by one of -1,0,1 for each available card (card that is ready to be taken) describing if the next card to the left is on the same 'level' or it is one level deeper or higher. (This is exploiting the assumption that a card overlaps only 2 other cards and that the structure looks like the one you have given in the example).