Futurama Puzzle Game

[measure]

Okay, so seeing a particular episode of the show Futurama inspired me to make a puzzle game based on the mind-switching machine featured in the episode. Basically, the machine can swap two people's minds into each other's bodies {Aa, Bb} -> {Ab, Ba}, but cannot switch between the same two bodies more than once (because of "immune response" or something).

For the game, I will be representing the "bodies" as an ordered list of variables, each of which has an integer value representing the "mind" that body contains. There will also be an array of "swap" objects each connected to two "bodies" that represent a potential swap between those to objects' values. During the game, the player will be presented with a mixed-up list and a set of available swap objects and will have to perform swaps to sort the list without running out of available swaps. For example, consider the following configuration with 4 variables ('X' represents an available swap, the A-B and A-C swaps are unavailable):

Code: Select all

(c) (a) (b) (d)  |  (a) (b) (c) (d)
 A   B   C   D   |   A   B   C   D
   -   X   X     |     -   2   4
     -   X       |       -   1
       X         |         3


This puzzle could be solved by performing swaps B-D, B-C, A-D, C-D in order (which happens to use all available swaps, but this is not required).

Call a particular board state "solvable" if it can be transformed to any sorted state using some number of the available swaps. Call a state "reachable" if the starting state (sorted list, all swaps available) can be transformed into it by some series of valid moves. I know I can create a solvable puzzle state by starting from the end condition (sorted list, no swaps available) and working backwards by swapping two values and adding the swap object that would undo that move (I can also add random swap objects that won't be used in the solution). Then the user just has to do the same moves in reverse order to solve the puzzle.

My problem though is that I'd like my puzzles to also be reachable (so the puzzle represents a group of people who have already swapped several times among themselves but are still able to be swapped back to normal without adding anyone new), so I need a way to find states that are both solvable and reachable. My pencil-and-paper analysis indicates that N=3 has no complete paths (other than the trivial zero-move path), and I found a few non-trivial solutions like the one above for N=4. Some simple Python code found additional solutions for N=5, but the solution space grows too quickly to search much higher using brute force. It looks like there's some parity rule that forces complete paths to have an even number of steps, but I'm not sure.

Can anyone help me find an algorithm to generate states for an N-variable board that are both solvable and reachable? Preferably with an appropriate proportion of available swaps remaining for maximal difficulty (I suspect somewhere around a 50-50 mix is optimal).

[jaap]

That is an interesting question. Of course, in the episode the problem was fixed by adding two people who hadn't swapped yet, which adds enough available swaps to always make it solvable.

It looks like there's some parity rule that forces complete paths to have an even number of steps, but I'm not sure.

Yes, the parity of the permutation is a well-defined concept, which means that the number of swaps needed to solve/generate a particular permutation is always odd or always even. A complete path must therefore be of even length.

I'll have to think about your actual problem further.

[mfb]

That is an interesting question. Of course, in the episode the problem was fixed by adding two people who hadn't swapped yet, which adds enough available swaps to always make it solvable.

That could be an approach. Make some random arrangement using only N-2 people, then find a solution using all N people, execute a few steps of the solution. Give the user the all swaps used in the solution, plus a few other swaps, but none of the swaps used to generate the problem.

[measure]

That could be an approach. Make some random arrangement using only N-2 people, then find a solution using all N people, execute a few steps of the solution. Give the user the all swaps used in the solution, plus a few other swaps, but none of the swaps used to generate the problem.

Thanks for the input both of you. I could also do it by working backward from the end to ensure a solvable position and just add two (correctly sorted) people who have no swaps available. That would be sufficient to ensure that the setup could have been reached without having to actually find a solution.

[mfb]

Thanks for the input both of you. I could also do it by working backward from the end to ensure a solvable position and just add two (correctly sorted) people who have no swaps available. That would be sufficient to ensure that the setup could have been reached without having to actually find a solution.

That is brilliant.

[matchmakers]

Thanks for the input both of you. I could also do it by working backward from the end to ensure a solvable position and just add two (correctly sorted) people who have no swaps available. That would be sufficient to ensure that the setup could have been reached without having to actually find a solution.

That is brilliant.

Wow!