Graph_Space: a puzzle about untangling graph isomorphisms

A while back I built a tiny libGDX game called Graph_Space. No menu, no instructions screen, just one single mechanic. I found it again while going through old projects and thought it deserved a proper writeup, same as I did for PrimalityGame.

Play it first, the rest of the post will make more sense once you've poked at it for a minute.

Play it right here

What am I even looking at

You'll see a grid of squares with numbers along the left edge and the bottom edge (0, 1, 2, 3...). That grid is an adjacency matrix. Row i, column j lit up means "vertex i and vertex j are connected." It's a graph, just drawn as a table instead of circles and lines.

Here's the setup: the game secretly generates a random graph (the target), then takes that exact same graph and randomly swaps some vertex labels around to produce the current matrix you start with. Same graph, different labeling. Your job is to swap vertices back until current matches target again.

Colors:

• Green — an edge that's correct (present in both current and target).
• Red — an edge the target wants but current doesn't have yet (missing).
• Yellow — an edge current has that the target doesn't want (extra, needs to go).
• Dark background — no edge, correctly.
• Purple — the selection highlight.

Win condition: get rid of every red and yellow cell. When the whole grid is green-or-background, you've matched the graph, and after two seconds the next level loads with the grid one size bigger.

How to play

Click any cell. The entire row and column through it light up purple. That's the set of valid second clicks.

Click a second cell somewhere in that purple cross. If your two clicks share a column, the two rows swap. If they share a row, the two columns swap. Either way what's actually happening is a vertex relabel: the row and column for those two indices swap together, which is the only way to rename a vertex in an adjacency matrix without changing the graph itself.

Click two cells that don't share a row or column and nothing happens, the selection just clears. A single click only ever tells you one row and one column, so a swap needs the second click to line up with one of them.

That's the entire ruleset. No scoring, no timer, no penalty for a bad swap, just you versus a permutation.

Why this is graph isomorphism

Two graphs are called isomorphic if one can be turned into the other purely by renaming vertices, no edges added or removed. Swapping a vertex's row and column together in the matrix is exactly a rename: the graph's structure doesn't change, only which number refers to which vertex.

That's also exactly how each level gets scrambled in the first place: start from the target, apply a handful of these same row/column swaps in random pairs, and you get the puzzle you start with. So the puzzle is always solvable, you're just running the scrambling process in reverse, without knowing which swaps were originally used.

The reason this is a genuinely fun mechanic and not just busywork: the moment you swap two vertices, every row and column touching either of them changes at once. Fixing one red cell can turn three green cells red. There's no local, greedy way to solve it column by column, you have to think about the whole permutation.

A demo: same graph, two labelings

Before touching the interactive puzzle, it helps to see the underlying fact in isolation: relabeling vertices does not change the graph, even though the matrix looks completely different.

Both grids below encode the same random graph. The right one has had a random permutation applied to its rows and columns, exactly like a fresh level does.

Hit the button a few times. The right-hand matrix always looks structurally unrelated to the left one at a glance, different cells lit up, different visual pattern, but the edge count and the degree sequence (how many edges touch each vertex, sorted) always match exactly. That invariance is not a coincidence, it's why it's the same graph. Any property that only depends on the graph's structure and not on how you happened to number the vertices has to be identical on both sides. That's also, incidentally, the standard first move for disproving two graphs are isomorphic: if the degree sequences differ, you're done, they can't be isomorphic. If they match (like here), it doesn't prove isomorphism, but it's a necessary condition.

Try the actual mechanic

Here's a small standalone version of the swap mechanic itself, separate from the game above, so you can try it without waiting for anything to load. Click two cells that share a row or column to swap, same rules as the real game. Green means correct, red means a missing edge, yellow means an extra one you need to remove.

Five vertices solves in a handful of moves once you get the hang of it. The real game starts you on a 5x5 grid and grows by one dimension per win, so it ramps up from "a bit of thought" to "actually hard" fairly quickly, a 9x9 or 10x10 grid has a lot more ways to be almost-but-not-quite right.

What I learned digging this back up

The thing that stuck with me is how little it takes to turn a real, unsolved-in-general computer science problem into a game. Graph isomorphism is a genuinely famous problem, it sits in a weird complexity-theory limbo where nobody's proven it's NP-complete, nobody's proven it's in P either, and the best known general algorithm (László Babai, 2015) runs in quasipolynomial time, an "almost polynomial but we can't quite say polynomial" category that barely has any other residents. And here it is, running as a browser toy.

Obviously the version in this game is nowhere near that hard, small graphs, and you know a solution exists because you can see the process that scrambled it. The real graph isomorphism problem is "here are two graphs from nowhere, are they secretly the same." But the click-two-cells-to-swap mechanic is exactly the naive search strategy you'd reach for by hand: try a swap, see if it helped, try another. It's a nice, small, physical way to feel why the problem is hard: at n=10 the number of possible permutations is 10! = 3,628,800, and there's no obvious way to know locally whether a given swap is progress until you've made it.

If I were to revisit this one, I'd add a move counter and a "shortest known solution" par, the way golf scores work, since right now there's no feedback on whether you solved it efficiently or flailed your way there in three times as many swaps as necessary.