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