Futurama Puzzle Game

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
measure
Posts: 97
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Futurama Puzzle Game

Postby measure » Wed Mar 29, 2017 10:22 pm UTC

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

User avatar
jaap
Posts: 2068
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Futurama Puzzle Game

Postby jaap » Thu Mar 30, 2017 9:23 am UTC

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.

measure wrote: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
Posts: 943
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Futurama Puzzle Game

Postby mfb » Thu Mar 30, 2017 7:46 pm UTC

jaap wrote: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.

User avatar
measure
Posts: 97
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: Futurama Puzzle Game

Postby measure » Fri Mar 31, 2017 2:21 pm UTC

mfb wrote: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
Posts: 943
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Futurama Puzzle Game

Postby mfb » Wed Apr 05, 2017 6:17 pm UTC

measure wrote: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
Posts: 3
Joined: Fri Mar 10, 2017 6:43 am UTC

Re: Futurama Puzzle Game

Postby matchmakers » Sun Apr 16, 2017 3:35 pm UTC

mfb wrote:
measure wrote: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!


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests