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.)