Solve a game of Accordion

Question

Accordion is a solitaire card game I recently came across where nearly every layout is solvable, but incredibly hard. You can play it here.

Rules

52 face cards are placed face-up in a random order. Each turn, you replace a card with a later card, where the two cards:

• Share a suit or number and
• Are at a distance of 1 (adjacent) or 3 (two cards in between).

The game is won when there is only 1 card remaining. You can assume that each input is solvable. The replaced card must always precede the replacing card.

Example

As an example, consider the following layout:

2H,2S,1S,2D  (H: Hearts, S: Spades, D: Diamonds)

There are 3 possible moves here:

1. Replace the 2H with the adjacent 2S, so we end up with 2S,1S,2D
2. Replace the 2S with the adjacent 1S, so we end up with 2H,1S,2D
3. Replace the 2H with the 2D (at a distance of 3), so we end up with 2D,2S,1S

Of those 3 moves, only the last one has the possibility of winning (You win by replacing 2D <- 2S, then 2S <- 1S).

Input/Output

Your job is to write an Accordion solver. You are passed a list of cards, and you need to return a list of moves to solve the game.

You are passed a list of cards as a comma-delimited string, where each card is passed as an integer representing their numeric value, then a character representing their suit.

You must return a list of replacements as a comma-delimited string, where each replacement is in the format Card <- Card (following the card format described above). The first card in each pair is the card being replaced.

Test cases:

5H,1C,12S,9C,9H,2C,12C,11H,10C,13S,3D,8H,1H,12H,4S,1D,7H,1S,13D,13C,7D,12D,6H,10H,4H,8S,3H,5D,2D,11C,10S,7S,4C,2H,3C,11S,13H,3S,6C,6S,4D,11D,8D,8C,6D,5C,7C,5S,9D,10D,2S,9S
5H,9C,11H,7S,7D,12D,6H,10S,3H,4D,12C,2S,3C,5C,7H,6S,1H,8S,2H,11S,4C,10D,12H,9H,2D,4H,6C,13H,11C,2C,10H,8C,1S,11D,3S,12S,7C,5D,13S,8D,4S,6D,13C,3D,8H,13D,1D,9D,9S,1C,5S,10C
7H,11C,8C,7S,10D,13H,4S,10C,4D,2C,4H,13D,3C,2H,12C,6C,9H,4C,12H,11H,9S,5H,8S,13S,8H,6D,2S,5D,11D,10S,1H,2D,5C,1C,1S,5S,3H,6S,7C,11S,9C,6H,8D,12S,1D,13C,9D,12D,3D,7D,10H,3S

While this competition is a code-golf, I am particularly interested in time-efficient solutions, and am likely to reward ingenious solutions with bounties. That said, solutions that take astronomical amounts of time are still acceptable (I'd recommend testing with a smaller deck, such as a 16-card, 4 suit deck).

Answer 1

Python 3, 274 272 271 bytes

2 bytes saved thanks to @orlp.

def g(p):
 q=lambda a:[[i,a]for i in range(len(p)-a)if p[i][:-1]==p[i+a][:-1]or p[i][-1]in p[i+a]]
 for n in q(1)+q(3):
  s=sum(n);c=p[:s]+p[s+1:];c[n[0]]=p[s]
  if g(c):return p[n[0]]+' <- '+p[s]+','+g(c)
 return' 'if len(p)<2else[]
print(g(input().split(','))[:-2]or'')

This is extremely slow. However, you can try it with a memoize. This has a few extra list-tuple conversions, but is otherwise equivalent.

import functools
@functools.lru_cache(maxsize=None)
def g(p):
 q=lambda a:[[i,a]for i in range(len(p)-a)if p[i][:-1]==p[i+a][:-1]or p[i][-1]in p[i+a]]
 for n in q(1)+q(3):
  s=sum(n);c=list(p[:s]+p[s+1:]);c[n[0]]=p[s]
  if g(tuple(c)):return p[n[0]]+' <- '+p[s]+','+g(tuple(c))
 return' 'if len(p)<2else[]
print(g(tuple(input().split(',')))[:-2]or'')

Even this one is astronomically slow with certain inputs.

The code uses strings, not numbers, so it also supports notation like KH instead of 13H.

Example:

$ python accordion.py
5H,9C,11H,7S,7D,12D,6H,10S,3H,4D,12C,2S,3C,5C,7H,6S,1H,8S,2H,11S,4C,10D,12H,9H,2D,4H,6C,13H,11C,2C,10H,8C,1S,11D,3S,12S,7C,5D,13S,8D,4S,6D,13C,3D,8H,13D,1D,9D,9S,1C,5S,10C
7S <- 7D,7D <- 12D,3C <- 5C,12H <- 9H,11C <- 2C,3S <- 12S,13D <- 1D,1D <- 9D,9D <- 9S,2S <- 6S,7H <- 1H,6S <- 8S,1H <- 2H,8S <- 11S,2H <- 9H,10D <- 2D,9H <- 4H,4H <- 4C,5C <- 4C,4D <- 4C,4C <- 12C,10S <- 11S,11H <- 11S,6H <- 3H,12D <- 2D,12C <- 2C,2C <- 6C,6C <- 8C,12S <- 13S,5D <- 6D,6D <- 8D,8D <- 3D,4S <- 9S,13S <- 9S,11D <- 3D,7C <- 1C,1S <- 1C,1C <- 13C,8C <- 13C,13C <- 13H,13H <- 10H,2D <- 3D,3D <- 3H,3H <- 8H,8H <- 10H,11S <- 5S,5H <- 10H,5S <- 9S,10H <- 10C,10C <- 9C,9C <- 9S