Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis(swapple.fuglede.dk) |
Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis(swapple.fuglede.dk) |
> 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.
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.
- 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):
C3→2 R2→3 0
C3→1 R2→1 82
C2→0 R3→0 93
C0→3 R0→2 163
C2→1 R3→1 342
C1→3 R1→2 426
C1→2 R1→3 558
C3→0 R2→0 614
C2→3 R3→2 640
C1→0 R1→0 726
C0→1 R0→1 810
C0→2 R0→3 922One 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.
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?
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?
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?
Alternatively, you could use 7 col. Your 4 row ops are equivalent to ('col', 3, 0), ('col', 0, 2), ('col', 2, 1), ('col', 1, 0).
Feature request: I was expecting an animation (three stars and confeti!) or at least a congratulation message when I won.
For the 4x4 board there is only 2^16 nodes, and 8*2^16 edges, so you can materialize the graph and get away with brute-forcing the whole graph.
But for bigger boards you won't be able to materialize the whole graph.
Maybe there are better heuristics to be found than the simple hamming distance. You should try have an AI look for them, by comparing the performance of a RL path planning vs the basic heuristic.
...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.
I then switched to pure Dijkstra which ended up being faster because evaluation was much cheaper at each step, and despite these heuristics being inadmissible, they didn't result in substantially fewer nodes expanded.
That's almost certainly a function of the problem size -- if it were 5x5, this approach would not have been as successful.
Edit: I 'm maybe getting this wrong confusing lower bound and upper bound. Sorry I'm a little rusty.
Edit2: For 4x4 one lower bound is hamming distance/4 , because you need at least these many moves to reach the goal. For 5x5 hamming distance / 5 and so on... But not sure how much this will reduce the need to graph.
I know of some work on trying out various heuristics for A*; Section 5 of https://arxiv.org/pdf/2201.06508 gives some examples of what works and what doesn't. I don't think D* Lite specifically has ever featured. There's plenty of room for trying to come up with other heuristics, and just for other takes in general.
> But for bigger boards you won't be able to materialize the whole graph.
If we restrict to boards corresponding to solvable puzzles, the number of vertices is https://oeis.org/A002884 (1, 1, 6, 168, 20160, 9999360, 20158709760, …) and indeed grows quickly. It's possible to manipulate the 7×7 case (https://arxiv.org/abs/2503.01467, shameless plug) but anything bigger than that seems hard.
One can ask, for example, how many moves are needed for the hardest n×n Swapple. For n = 1, …, 7 the answers are 0, 3, 6, 9, 12, 15, 18 respectively, but we don't know what the answer is for n = 8.
Either way, I guess my implementation had a bug -- A* does yield a significant speedup, but adding the 0.25x scaling factor to ensure that the heuristic is admissible loses almost all of those gains.
For some concrete numbers: with the bug that basically reduced to BFS, it ran in about 7s; with the bug fixed but a wildly inadmissible heuristic, it ran in about 0.01s; with the heuristic scaled down by 4x to guarantee its admissibility, it ran in about 5s.
I think scaling it down by 2x would be sufficient: that lower bound would be tight if the problem is one row move and one column move away from the goal state, but potentially all four rows and columns would not match. In that case, it ran in about 1.6s.