[HN Gopher] Show HN: Swapple, a little daily puzzle on linear re...
___________________________________________________________________
Show HN: Swapple, a little daily puzzle on linear reversible
circuit synthesis
Author : fuglede_
Score : 66 points
Date : 2025-09-28 12:42 UTC (1 days ago)
(HTM) web link (swapple.fuglede.dk)
(TXT) w3m dump (swapple.fuglede.dk)
| arjvik wrote:
| Reminds me of the row-echelon form algorithm we learned in
| algebra!
| fuglede_ wrote:
| Heh, nice catch, I think you'll find that with a bit of work,
| you can make row reduction/Gaussian elimination work here as
| well. But that the resulting sequences of operations can get
| very long! One thing I personally like about the puzzle is that
| once you've played it for a few days, you start gaining some
| intuition about sequences of moves that are useful, but coming
| up with a good general algorithm (that also works for larger
| than 4x4 boards) is still a challenge.
| GistNoesis wrote:
| Have you tried some generic pathfinding algorithm like D star
| lite on the graph with heuristic being the hamming distance
| from current node to the start ?
|
| 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.
| vitus wrote:
| I tried implementing A* using pointwise Hamming distance,
| found that it was inadmissible (since it yielded a
| suboptimal result on par with my manual attempt), then
| tried again with row-wise Hamming distance but was pretty
| sure that's inadmissible too (although it did yield an
| optimal result). I then tried min(row-Hamming, column-
| Hamming) but I'm not convinced that's admissible either.
|
| 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.
| GistNoesis wrote:
| You may need to add some factor for the Hamming distance
| to make it admissible. On a 4x4 board each move change at
| most 4 bits. So 4 x the hamming distance should be OK.
|
| 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.
| fuglede_ wrote:
| Thanks for sharing your thoughts!
|
| 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 7x7 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 nxn 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.
| dooglius wrote:
| Hamming distance doesn't strike me as a useful metric
| here because how "close" two rows are is entirely
| dependent on what the other rows are. E.g. if you have a
| row of all 1's then two rows with maximal hamming
| distance are only one move away and if on average you
| have a bunch of n/2-weight rows then two rows different
| by 1 bit are not close. The best you can do is count the
| number of total rows matching the target I think?
| vitus wrote:
| Yeah, that was what I tried with row-Hamming / col-
| Hamming (namely: treat entire rows / cols as matches or
| not). I then used the min of the two to address those
| issues.
|
| 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.
| ollysb wrote:
| 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.
| fuglede_ wrote:
| Yep, I see what you're saying; let me try to clarify that part!
| hmokiguess wrote:
| I agree, to this point, my expectation was that it would
| animate for me the combination and updated result after my
| choice. I had to fill that gap and it confused me at first.
| d--b wrote:
| Oof, it's brutally hard!
| jxf wrote:
| On the other hand, if you find a way to make it easier (I
| believe the general case is O(n2) in gates), then you've
| improved a very hard computer science problem!
| nickcw wrote:
| Hmm, Gaussian elimination over GF(2). Let's go!
|
| ...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.
| jmkd wrote:
| 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?
| Chinjut wrote:
| 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.
| selimthegrim wrote:
| This implicitly relies on row and column rank being the same.
| Chinjut wrote:
| That's not a problem, as they are the same.
| selimthegrim wrote:
| Yes, I know. It was just what my thoughts went to.
| pekim wrote:
| 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.
| gus_massa wrote:
| 13 moves (I guess it's too inefficient :( )
|
| Feature request: I was expecting an animation (three stars and
| confeti!) or at least a congratulation message when I won.
| fuglede_ wrote:
| The confetti is currently there for when you find a shortest
| solution. I'd say 13 moves deserves at least a star or two, so
| I'll have to add that!
| dandanua wrote:
| 10 moves, still not optimal
| gaanbal wrote:
| me too and I absolutely cannot remember the steps I took
| merelysounds wrote:
| Spoiler warning, this comment contains a solution, this is your
| chance to stop reading, especially if you didn't have a chance to
| play yet.
|
| 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?
| PinkRidingHood wrote:
| I found one using a program: [('row', 0, 1), ('row', 1, 2),
| ('row', 2, 0), ('row', 0, 3), ('col', 2, 3), ('col', 1, 2),
| ('col', 0, 1)]. It says it's the optimal.
| merelysounds wrote:
| Thanks for sharing and congrats!
| dandanua wrote:
| You could use 7 row operations. row and col ops commute, and
| your last 3 col ops are equivalent to ('row', 1, 0), ('row',
| 2, 1), ('row', 3, 2) if acted on identity matrix. So, use
| them at first, and then your four row ops.
|
| 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).
| dooglius wrote:
| The 'i' has more background:
|
| > 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.
| MisterMusion wrote:
| 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): 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 922
___________________________________________________________________
(page generated 2025-09-29 23:01 UTC)