The setup is this: there are a (predefined) number of queues, with varying numbers of items in them. In one move, you can pick up a queue, and drop the items in the queue, starting from the head (the left side in my depiction), and working your way down, onto the tails of adjacent queues. You must drop each successive item in a queue directly adjacent to the last queue you used (treated cyclically in the total number of queues), and you must continue until all items in the queue you picked up are dropped, at which point you can pick up another queue, with no restriction on which queue you pick up next. (I'm going to call the action of picking up a queue and distributing the items in it a "move".) The goal is to start with a certain configuration, and through a sequence of legal moves, make a certain other configuration. In the game, there are two puzzles of this type. The first puzzle starts with this configuration:
Queue A: D1 B1 A3
Queue B: A1
Queue C: C1 E1
Queue D: A2 B2 E2
Queue E: B3
and the goal configuration is:
Queue A: A1 A2 A3
Queue B: B1 B2 B3
Queue C: C1
Queue D: D1
Queue E: E1 E2
In these depictions, the queues are the lines, and the items in the queues are being called A3, D1, and so on, where the naming system is arbitrary, but designed to make the end configuration recognizable. As an example, I could pick up queue A from the starting configuration. I would then be forced to place D1 at the end of either queue B or queue E (the adjacent queues). If I drop the items into queue B, then A, then E (each time dropping an item adjacent to the last queue I used), I get the configuration [B1, A1 D1, C1 E1, A2 B2 E2, B3 A3].
My goal is to find the fastest solution to this puzzle, if one scores the moves as one point for each pick up and one point for each drop (so that the move given above is 4 points). I should point out that I have a solution:
AEDC; DEDCB; EDEA; AB; ED; DEDE; EAE; AB; DC; CDCBCB; CDE; DCD; EDE; EA; DED; AE; BABABAB
The total score is 57 (the total number of letters in this list).
but I have no idea if it is even close to optimal, and I'd like a solution based on more than trial and error. I tried a brute force breadth-first search, but my computer ran out of memory after 15 points deep (about 5 moves). I haven't tried the second puzzle yet; the initial condition is [C3 B2, B4 B1 C2, C1, A2 B3 D1 A1] with the final state as [A1 A2, B1 B2 B3 B4, C1 C2 C3, D1]. There are only 4 queues in this puzzle, and my best solution so far is
with score 29.
Any observation of invariants or things which could allow me to narrow the search space would be helpful.
EDIT: The number of possible configurations of the first puzzle (with 5 queues and 10 items) is 14!/4! = 3,632,428,800, and of the second puzzle (with 4 queues and 10 items) is 13!/3! = 1,037,836,800. This is not too large to store on disk, so a full graph traversal may be a possibility, although the program will need to take advantage of the symmetries which allowed me to calculate that number (the 14! number of ways of arranging 10 items plus 4 partitions, less the 4! arrangements of the partitions).