Mathematically interesting puzzle from Myst Revelation

[di gama]

If any of you have played Myst IV: Revelation before, you'll know this puzzle as the Dream Puzzle from the end of the game. If not, no worries - I'm going to strip all the plot stuff out of the posed problem anyway.

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:

Spoiler:

The moves here are given as (pickup queue letter) (drop queue letters...).
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

Spoiler:

BABC; ADAD; AB; DABADCB; ADA; DAD; ADA; DAD
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).

[Proginoskes]

The thing's probably PSPACE-complete.

[burgie12]

*puzzle description*

I have to say, I never played Myst: Revelation, but this puzzle was quite intriguing. In fact, it got me to register for this site. I'd been reading through the logic puzzle forum during my lunch breaks for a couple weeks, but nothing had been sufficiently interesting for me to register until this one. So, awesome-sauce.

Anyways,

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

I got a couple of 55-point solutions. One was what I came up with before I read your solution (and is pretty similar to the one that you use for the second puzzle):

Spoiler:

ABCD; ED; BAE; CDED; DEDEDCBC; CDC; DCDC; DE; EDEAEA; BC; CBCDC; CBC; CD; DCBC; CDC

while the other takes yours and modifies it slightly:

Spoiler:

AEDC; DEDCB; EDEA; AB; ED; DEDE; EAE; AB; DC; CDEAEA; ABA; AB; EDEA; AE; DCD; BABABAB

(I hope I used your notation correctly.)

And, I'll just say that you kicked my butt on the second one. I tried to get too fancy and ended up with a 58-point solution. I was thoroughly impressed with the simplicity of your solution when I glanced at it.

I'd also be interested in coding out a brute force (or non-, either or) solver or helping to collaborate. My coding skills aren't quite up to snuff, but I'll give it a gander and try to contribute, anyways.

[lightvector]

Just for fun, I coded up a solver too. The solver I wrote uses iterative-deepening a-star search. If you're looking for exact optimal solutions by brute-force-like methods, then a-star and its variants tend to be the generic algorithms you can throw at a problem like this that won't (hopefully) do too terribly.

Particularly for exponentially branching puzzles, the general approach of depth-first + iterative deepening can be effective, because the overhead of repeatedly searching is only a small constant factor when the space is exponential anyways, and you avoid huge memory usage. You also avoid the overhead of copying the puzzle state, as instead you can simply make moves and undo them incrementally.

The a-star heuristic I coded up might be inadmissable if there's a bug, but assuming it's good, the following solution should be optimal:

Spoiler:

ABAEBAEABADCBCEDCDCDEAEADCDCCBC (31 steps)

For the second puzzle, the following solution should be optimal:

Spoiler:

ADAABBABCBDABADCABADADDADA (26 steps)

[di gama]

Just for fun, I coded up a solver too. The solver I wrote uses iterative-deepening a-star search.

Wow, that's fantastic. I've never heard of that algorithm before. What language did you use? Do you have any code samples? I'd love to see how you made finding the optimal solution a tractable puzzle. What heuristics did you use? I thought about it for a while, but it seems to me that in a puzzle like this it's hard to tell whether you are close to the solution, except when you are within 2 moves or so.

TBH, I'm not really interested in the true globally-optimal solution, but one only one which is close to optimal, and computer-certified as such (as in a solution which is solved by a heuristic algorithm without needing to be partially solved by hand), and your solutions do nicely for this purpose. The reason I became interested in this in the first place was that I'm actually doing a speed run of Myst IV: Revelation, and I wanted the fastest possible way of solving this puzzle. I should also fess up and mention that those solutions are not mine. I got them from a walkthrough site, because the puzzle soundly walloped me all the times I've tried to play the game for real (although in the game there is the added layer of difficulty in just figuring out what the end configuration should be). I'm not very good at solving these kinds of puzzles, but I'm rather better at coding puzzle-solving programs, so I'll apply my talents where they are most effective.

[lightvector]

If you haven't seen the algorithm - here's the idea.

"Iterative deepening": Let's use depth-first search instead of breadth first search to avoid the memory blowup. We'll force the depth-first search to stop and backtrack at a fixed depth limit, and then iteratively re-search with incrementing depth, so that when it finds a solution, we know it's the shortest possible. If the branching factor is B on average and the solution is at depth D, then normally we expect a running time of B^D, but due to the repeated searching we actually run in 1 + B + B^2 + B^3 + ... + B^D. But since this is a geometric series, and B isn't tiny (here, maybe 3-4 on average), the largest term by far dominates the rest. So by iterative researching and using depth-first, we avoid memory usage while hardly increasing the search time at all.

"A-star": Imagine we have some function H that allows us to roughly estimate how many steps it would take to solve the puzzle from any position p. If our depth limit is D, and we are S steps deep in the search, and S+H(p) > D, then it's very likely that we won't find the solution anywhere within the depth limit, so we return right then and there, without wasting time on a search doomed to fail. Indeed, if H is strictly a lower bound and never overestimates, then this is provably safe.

For this problem, an immediate obvious lower bound is the number of wrong queues + number of elements in wrong queues. It will of course take at least that many steps to solve a position, so by tossing this in and using A*, you immediately do vastly better than raw brute force.

I spent a little time just now improving the lower bound provided by the heuristic. It's somewhat more complicated than the obvious one, but much stronger. It has a lot of checks for cases where an element must provably be dropped in the wrong spot, or will conflict with some other element, to try to strengthen the bound. The source code (C++) is attached with some comments, so you can take a look. Overall, the algorithm still takes an appreciable amount of time (several seconds) on the first puzzle, so it likely won't scale to significantly larger versions of the same puzzle, but it's not bad.