I found the instructions pretty confusing because you're not actually moving anything. You're combining the first selected row/column with the second selected row/column and replacing the second with the result of the combination.
Neither the instructions nor the interface helped me to understand what I was doing or how to achieve it, for example I don't understand why if I click a row I can't click a column next, and vice versa. From which I can only conclude that it's just not for my sort of brain.
However I'm sure there is a diverting puzzle game in here somewhere. I wonder if you used narrative language and symbolism unrelated to linear reversible circuit synthesis (but kept whatever mechanic is important) an average player might be able to grasp it more easily?
Note that two matrices (of the same dimensions) can be transformed into each other if and only if they have the same rank.
A (non-optimal, but straightforward) procedure for doing so is like so: First, use Gaussian elimination row-wise to put any matrix into reduced row echelon form. One can now use Gaussian elimination column-wise to transform the matrix into a 2x2 block matrix whose upper-left block is an identity matrix (of size corresponding to the rank) and whose other blocks are zero. Since all moves are invertible, any two matrices of the same rank are thus connected via the same such block matrix.
In general, it is necessary to use both row and column moves. However, if both matrices are square with full rank (as in today's puzzle), one can just use row moves (or just as well, just use column moves), using just Gaussian elimination. More generally, one can just use row moves iff both matrices have the same row space, and similarly for columns.
So if I'm understanding it correctly, it applies an xor operation on the pairs of cells. For example, click column A then column B. For each of the pairs of cells in the two columns, it performs B = A xor B.
> The game is inspired by the synthesis of linear reversible circuits; a problem in reversible and quantum computation. Here, the goal is to construct a target operation, the target pattern in Swapple, using a sequence of simpler operations, specifically controlled NOT (CNOT) gates, which flip the state of a target bit if and only if a control bit is set. In Swapple, each row and column operation corresponds to applying a CNOT gate. Your task is to find a sequence of these gates, i.e. a circuit, that transform the initial configuration, corresponding to an empty circuit, into the target configuration. Moreover, finding one of the shortest sequences of moves to achieve this goal corresponds to finding one of the most efficient circuits that implements the desired operation.
Enumerating all 7-Move solutions of today's puzzle, I expected some kind simple pattern, like some key moves with a few permutations. I found that it is far more complex:
- there are 1536 solutions
- almost all moves are useful, non are required
- for every row-xoring move there is exactly one column-xoring move that appears in the same number of solutions (and no move appears twice in a solution)
Here is the number of solutions a move appears in (0-based indices):
That's nifty! There's a lot of symmetry that can help to boil it down. For example, you actually only need row moves, and any solution with column moves can canonically be turned into one with row moves; post-composing with Ci→j is pre-composing with Rj→i.
One can think of the set of all possible board configurations as the vertices as a graph, with edges indicating how to move between configurations. Then your 1536 solutions are the 1536 distinct shortest paths between the starting and target configuration.
Then, you can also choose to consider not just board configurations, but board configurations up to simultaneous permutation of rows and columns; that will also reduce the number of unique solutions.
Seems interesting but for some reason on Chrome on my iPhone 13 mini the page is too big for the screen: I have to pinch zoom out to see the X that dismisses the instructions, and can't scroll the about page.
Did you make some assumptions about the minimum window / screen size based on oversized modern smartphones, forgetting that lots of us still cling to more reasonably sized older devices?
Hm, yeah, tested it down to about 500 px width, and the low-resolution devices in Chromium but that was too optimistic then. The modals should of course be closeable, and both game boards simultaneously visible. Played around with the modals a bit, so maybe it works better now?
16 comments
[ 2.7 ms ] story [ 39.2 ms ] thread...Some time later... This is quite hard!
I think thinking about this puzzle as Gaussian elimination is not helpful!
I think the controls would work better if you dragged the row/column onto the one want to change.
However I'm sure there is a diverting puzzle game in here somewhere. I wonder if you used narrative language and symbolism unrelated to linear reversible circuit synthesis (but kept whatever mechanic is important) an average player might be able to grasp it more easily?
A (non-optimal, but straightforward) procedure for doing so is like so: First, use Gaussian elimination row-wise to put any matrix into reduced row echelon form. One can now use Gaussian elimination column-wise to transform the matrix into a 2x2 block matrix whose upper-left block is an identity matrix (of size corresponding to the rank) and whose other blocks are zero. Since all moves are invertible, any two matrices of the same rank are thus connected via the same such block matrix.
In general, it is necessary to use both row and column moves. However, if both matrices are square with full rank (as in today's puzzle), one can just use row moves (or just as well, just use column moves), using just Gaussian elimination. More generally, one can just use row moves iff both matrices have the same row space, and similarly for columns.
Feature request: I was expecting an animation (three stars and confeti!) or at least a congratulation message when I won.
With 8 moves and rows only: 2->1, 1->2, 2->1, 3->2, 2->3, 4->3, 4->1, 1->4.
A more efficient solution should be possible; did anyone find any?
> The game is inspired by the synthesis of linear reversible circuits; a problem in reversible and quantum computation. Here, the goal is to construct a target operation, the target pattern in Swapple, using a sequence of simpler operations, specifically controlled NOT (CNOT) gates, which flip the state of a target bit if and only if a control bit is set. In Swapple, each row and column operation corresponds to applying a CNOT gate. Your task is to find a sequence of these gates, i.e. a circuit, that transform the initial configuration, corresponding to an empty circuit, into the target configuration. Moreover, finding one of the shortest sequences of moves to achieve this goal corresponds to finding one of the most efficient circuits that implements the desired operation.
- there are 1536 solutions
- almost all moves are useful, non are required
- for every row-xoring move there is exactly one column-xoring move that appears in the same number of solutions (and no move appears twice in a solution)
Here is the number of solutions a move appears in (0-based indices):
One can think of the set of all possible board configurations as the vertices as a graph, with edges indicating how to move between configurations. Then your 1536 solutions are the 1536 distinct shortest paths between the starting and target configuration.
Then, you can also choose to consider not just board configurations, but board configurations up to simultaneous permutation of rows and columns; that will also reduce the number of unique solutions.
Did you make some assumptions about the minimum window / screen size based on oversized modern smartphones, forgetting that lots of us still cling to more reasonably sized older devices?