WorksComputer Science
Hardness of "Infinite Energy" Puzzles
Abstract
Infinite Energy (by Light Potato, 2025) is a single-player puzzle in which one wires a network of sockets so that, after every power source is unplugged, energy keeps circulating and leaves every board energized. We study several variants of the game and the complexity of deciding whether an instance can be won. The variants can be played at https://infinite-energy-peer-review.netlify.app, which also has worked examples of the reduction techniques. The colorless game, with connectability given by an arbitrary matrix, is NP-hard (by reduction from Hamiltonian Path) and lies in PSPACE. We give a seven-socket instance winnable only by charging a temporary battery loop and then breaking it, so the natural "charge and keep" strategy fails. We reduce NP-membership to one conjecture: that every winnable instance has a winning play in which no socket is charged twice. Two variants bound the complexity more tightly. The unconstrained variant, in which connectability is unrestricted, is -complete under Turing reductions (hence in L). The geometric variant, in which connectability is set by proximity of points in , stays NP-hard for every fixed via reduction from Hamiltonian Path over grid graphs. The one-dimensional case is open. The colored variant is NP-hard, though a matching upper bound remains open.
Introduction
Infinite Energy (by Light Potato, 2025) is a puzzle in which the player must assemble a circuit that stays powered after its power supply has been taken away. It was created for the 2025 GMTK Game Jam, an annual competition hosted by the game designer Mark Brown. Out of the 9,547 entries it ranked first as Brown’s personal favorite and tenth in the community vote for creativity. The original game can be played at https://lightpotato.itch.io/infinite-energy. We study it not only for this reception but also because its complexity sits in an unusual position among well-studied games, i.e., while a lower bound on hardness follows from reductions from known NP-hard problem, an upper bound on hardness remains elusive. To our knowledge, Infinite Energy does not fit cleanly into any family of puzzles whose complexity has been studied. We discuss this further, after providing an exposition of the game rules.
An instance is played on a collection of boards (the set ), each holding one or more circular sockets (collectively ) and displaying a cartoon face that smiles once the board is satisfied. Energy is supplied by external power sources (the set ), drawn as octagonal units, and travels along directed wires that the player draws between sockets. In the full game a board also carries a color requirement, shown by the eyes of its face. Color is a separate constraint that we isolate in Appendix E and ignore until then, so the main text studies the colorless game. Two rules govern the flow of energy:
The sockets on a board are intrinsically connected, so energizing any one of them energizes the whole board and makes the remaining sockets available as outgoing sources, and
each socket admits at most one wire, so that a socket either transmits energy or receives it, but never both.
The object of the game is to keep the boards powered after every source has been disconnected, which compels the player to route energy into directed cycles that circulate without external input. Figure 1 follows a single play through this mechanism, and Figure 3 (§ 2) contrasts a small winnable instance with one that cannot be won.
Figure 1. A play of INFINITE ENERGY on an instance with one red power source (the octagon on the left) and four boards, each carrying a red color requirement shown by the red eyes of its face. (a) The initial configuration: every board is unenergized and the source is detached. (b) The source is attached and emits its color along a wire into the upper socket of the left vertical board. Two of its three sockets are joined into a directed cycle (the third stays free to pass energy on), and the board becomes energized red so its face smiles. The right vertical board is wired into a cycle of the same shape but remains unenergized, drawn cold, since no energy has yet entered it. (c) The source is detached. The charged cycle continues to circulate energy without it, and because sockets sharing a board are joined for free, the energy propagates along cross-board wires to the remaining boards. Every board now displays its requirement met, and the instance is won with no source attached. The sustaining directed cycle from (b) is drawn schematically in Figure 2.

Figure 3. Two unconstrained instances (final configurations. No source attached. Shaded sockets are energized). (a) A winnable instance: has three sockets, so two of them form a self-sustaining 2-cycle (charged earlier through , then removed) and the third exports energy to the other board. (b) An unwinnable instance: two boards of two sockets each. Here , but no board has three sockets, so any loop would occupy both sockets of each board it meets and leave none off the loop to charge it (Lemma 8). Once is removed nothing stays energized.
The step from Figure 1b to Figure 1c is where the mechanism operates. While the source is present it charges the connected structure and after it is removed the boards stay charged because the energy is trapped in a self-sustaining cycle. The player must therefore reach a state in which energy keeps propagating to every board after the source is gone. § 1.1 defines energization as the least fixed point of a monotone propagation rule, i.e., an instance is won when its energized set remains a nonempty fixed point after the sources are deleted. We encourage readers to try the variants at https://infinite-energy-peer-review.netlify.app.
This requirement places INFINITE ENERGY between two families of previously analyzed games: the trajectory games, such as platformers and sliding-block puzzles, whose solutions are sequences of moves [ADGV15,For10,HD05], and the consistency puzzles, such as Minesweeper, whose solutions are static labelings checked against local constraints [dB12,Kay00].
INFINITE ENERGY shares with the trajectory games a winning condition defined over a process rather than a state, so the final configuration does not certify a win. The wire graph left behind once the sources are withdrawn is a union of paths and cycles, and it does not record whether its loops were ever charged. In Figure 1b the un-energized cycle on the right is structurally identical to the charged one on the left, so the terminal graph underdetermines the energized set. A frozen frame of generalized Super Mario Bros. is uninformative in the same way, certifying nothing about the legality of the play that produced it [ADGV15]. The two families diverge in the certificate their processes admit. For a trajectory game the certificate is irreducibly a sequence of moves, checked by forward simulation, and generalized instances need not admit any short certificate, which places the reconfiguration framework underlying many of them in PSPACE [Hea04,HD09]. For INFINITE ENERGY one might hope that charging is monotone, so a static witness suffices: the final loops, each with a route in the connectability graph from a source to a free socket on one of its boards. This hope fails. Some instances are winnable only by charging a temporary battery, a loop built and then broken to free its sockets (Proposition 26), so the final loops do not on their own certify a win. They must also be chargeable in some order, with batteries where needed and without the charging routes competing for socket capacity, and the final wiring has erased that schedule. We therefore take the certificate to be a short winning play, and reduce the existence of one to a single conjecture: that a winning play never needs to charge any socket twice (§ 5). Without this conjecture, the problem is NP-hard and in PSPACE.
The game layers two further constraints on this mechanic. Wires have bounded length, so not every pair of sockets may be joined. In the standard game this restriction comes from a maximum wire length, and only sockets closer than that length can be connected. We relax it by taking connectability to be arbitrary, given by a connectability matrix supplied with the instance, and we return to the geometric version in § 6.
The second restriction assigns a color to each source and a color requirement to each board, with colors mixing additively as energy flows. We describe only the colorless game and defer the colored variant to Appendix § 13. Since the game is NP-hard without color, the colored variant is NP-hard too, but a matching upper bound remains open.
Our results. We separate the combinatorics of the game from its geometry. When connectability is unrestricted ( all-ones), winnability reduces to two arithmetic conditions: at least sockets and some board with at least three sockets (Theorem 7), and the induced predicate is -complete, hence in L (Theorems 10, 12, Proposition 11). With given arbitrarily the problem becomes NP-hard by reduction from Hamiltonian Path (Theorem 14), and lies in PSPACE (Theorem 17). We reduce NP-membership to a conjecture that recharge-free plays suffice (Conjecture 29, § 5), which would give NP-completeness. This hardness is not an artifact of unrealizable matrices. Every symmetric is realizable as a distance-threshold graph in , where (Theorem 20), so the problem stays NP-hard under that geometric restriction (Corollary 21). In fixed dimension it remains NP-hard for every (Theorem 24). The one-dimensional case is open. Finally, the colored variant is NP-hard, though we do not settle a matching upper bound (Appendix § 13). Table 1 collects these results.
| Variant | Complexity | Reference |
| Unrestricted (all-ones) | -complete | Theorem 12 |
| Arbitrary | NP-hard, in PSPACE | Theorems 14, 17 |
| Geometric, | NP-hard, in PSPACE | Corollary 21 |
| Geometric, , | NP-hard, in PSPACE | Theorem 24 |
| Geometric, | open | — |
| Colored | NP-hard | Appendix § 13 |
Table 1. Complexity of Infinite Energy across variants. For the NP-hard rows, NP-completeness would follow from Conjecture 29 (recharge-free plays suffice), which we state and support but do not prove.
Graph-Theoretic Formalization
Definition 1 (Instance). A (colorless) game instance is a tuple where
is a finite set of sockets.
is a finite set of sources, with .
is a partition of into nonempty boards, with (the empty instance wins vacuously and is excluded). We write for the board containing socket .
is a symmetric connectability matrix, where means a wire may join and . We set for all : a wire between two sources could never carry energy (a source only supplies, never receives, by Definition 2), so forbidding such wires loses no plays and lets us treat every socket uniformly.
A wire carries energy in one direction, so we model a wiring as a directed graph.
Definition 2 (Configuration). A configuration for is a directed graph , where each edge is a wire oriented from the energy-supplying end to the receiving end, satisfying (with and being the out- and in-degree of in ):
One wire per part: for every .
Connectable: .
Sources only supply: for every (no wire points into a source).
Since the vertex set is fixed by , a configuration is determined by its wire set . We write the configuration as when only the wires matter.
Sockets on the same board pass energy without a wire. We record this with edges that do not count against the degree bound.
Definition 3 (Implicit edges and completion graph). The set of implicit edges is
(energy flows either way within a board). The completion graph of a configuration is .
Definition 4 (Loop). A loop is a directed cycle in whose edges alternate between wires (from ) and implicit edges (from ):
Two facts follow immediately from Definition 4. First, because the edge types alternate around the cycle, every loop has even length , using exactly wires and implicit edges. We call these wires the -edges of the loop . Each socket of carries exactly one of them. Second, every socket on a loop has one incoming and one outgoing cycle edge of which exactly one is a wire, so a loop never exceeds the one-wire-per-socket budget.
It remains to say how energy spreads and what it means to win.
Definition 5 (Energization). Fix a configuration . A socket is energized in if, in the completion graph , it is reachable from some energized socket or a power source by a directed path of wires and implicit edges. A board is energized if at least one of its sockets is energized (equivalently, because of the implicit edges, if one socket is energized all the sockets on the board are). A loop is said to be charged in if every socket on it is energized in .
The current wiring does not by itself determine energization: a charged loop keeps its sockets energized even after the source that charged it is unplugged (Figure 2). Energization is therefore relative to a play’s history, not to the current wiring alone. Appendix A makes this precise with a recurrence over the configurations a play traverses. Informally, a socket is energized at step when it is reachable, through wires and board edges, from a source or from a loop that was charged earlier and whose wires still stand. This persistence is the source of the problem’s difficulty.

Figure 2. The two smallest loops (Definition 4), drawn as directed cycles. Solid arrows are wires of . Dashed arrows are implicit board edges of , which cost no wire slot. Edge types alternate, so a loop of length uses wires and implicit edges. The 2-cycle is the loop drawn as the red wires with both ends on the same board in Figure 1c.
Definition 6 (Move and play). A move is a pair where is a directed edge with and . Applied to a configuration , the move yields
and is legal at if is a valid configuration (Definition 2) and, additionally, when and when .
A play is a finite sequence of moves such that, writing and , each is legal at . We call the configurations traversed by the play.
Problem (Infinite Energy). Given an instance , is there a play whose final configuration connects no source yet leaves every board energized at (Appendix A)?
Unconstrained Infinite Energy is in P
The unconstrained variant Unconstrained-Infinite Energy is the special case in which the connectability matrix imposes no restriction: for every socket–socket and source–socket pair (only source–source wires remain forbidden). The input is then only with , and we ask whether the instance is winnable, and we give a linear time algorithm.
Theorem 7. An unconstrained instance with is winnable if and only if
(i) , and
(ii) some board has at least 3 sockets.
Both conditions are checkable in time, so Unconstrained-Infinite Energy . Figure 3 shows a small winnable and a small unwinnable instance. The construction behind sufficiency is illustrated in Figure 5 (Appendix B).
Figure 5. The construction behind sufficiency in Theorem 7. The boards fall into three groups: the single bootstrap board (green, any board with at least three sockets), the boards with (blue), and the singleton boards (orange). Here is the running pool of free energized sockets. (a) The initial instance, with . (b) Step 1 bootstraps a self-sustaining loop on . (c) Step 2 chains every board with , each net adding sockets to . (d) Step 3 spends one socket of per singleton, which never runs out exactly when .
Sufficiency
Proof (sketch). Fix a board with and bootstrap a self-sustaining 2-cycle on two of its sockets (charge through a source, then disconnect it). Maintain a pool of free energized sockets. Energizing a board nets to , so processing boards in non-increasing size keeps nonempty exactly when
Full proof in Appendix B.
Necessity
Both necessity proofs start from a winning final configuration , which by definition has no source connected yet every board energized. Since the base case of energization is empty without sources, all energy in originates from loops.
Lemma 8. If every board has at most 2 sockets, the instance is not winnable.
Proof (sketch). A charged loop’s sockets are all wire-saturated, so it can have been charged only through an implicit edge from an off-loop socket on a board it meets. Because implicit edges only exist within the same board, that board then has at least three sockets. Full proof in Appendix B.
Lemma 9. If , the instance is not winnable.
Proof (sketch). Contract each board to a node. Every energized board has in-degree at least one, so there are at least socket–socket wires and each uses two of the socket slots, so . Full proof in Appendix B.
Together, Lemmas 8 and 9 give the necessary direction of Theorem 7.
Hardness Lower Bound for Unconstrained Infinite Energy
Theorem 7 reduces Unconstrained-Infinite Energy to checking two arithmetic conditions on : that and that some board has at least three sockets. We pin down the exact complexity of this predicate, which turns out to be far below P.
Membership in P already shows the unconstrained game is easy, but not how easy. The size test is a comparison of two counts, and we show below that this counting is not only sufficient but necessary. We use the standard circuit classes (see [AB09,Vol99]). is the class of languages decided by families of constant-depth, polynomial-size Boolean circuits over unbounded fan-in gates. is the same with unbounded fan-in threshold (equivalently majority) gates also allowed. Hence , and Majority [AB09,Vol99], so the inclusion is strict. Locating the predicate in but outside (under the encodings, uniformity, and reductions fixed below) is the sense in which its only difficulty is counting.
Theorem 10. Unconstrained-Infinite Energy .
Proof. Scan the input once, maintaining three quantities: a running count of boards (), a running count of sockets (), and a single bit recording whether any board seen so far has more than two sockets. At the end, accept iff the bit is set and . Each counter holds a number at most the input size , so uses bits. The comparison is computable in the same space. Hence the procedure runs in deterministic logspace.
The predicate is also constant-depth: is one threshold over the input, and “some board exceeds two sockets” is a disjunction of local checks. This gives us the following proposition:
Proposition 11. Unconstrained-Infinite Energy .
We complement this with a matching lower bound: the problem is as hard as counting, so it cannot lie in [AB09,Vol99].
Theorem 12. Majority reduces to Unconstrained-Infinite Energy by a projection, in particular by a many-one reduction. Since Majority is -complete under Turing reductions [Vol99], Unconstrained-Infinite Energy is -complete under Turing reductions.
Proof (sketch). Map to one board per bit: a three-socket board when and a singleton when . Then and with , so , and a 1-bit supplies the required three-socket board. Thus the instance accepts iff is majority-1. Each output board depends on one input bit, so the map is a projection, and a projection is an reduction. Full proof in Appendix B.
Two conventions make the completeness statement precise. We take the standard encoding in which the boards are listed in input order in fixed-width records, so the -th board is the one-bit projection above (later output positions do not depend on earlier bits), and we read and as dlogtime-uniform, under which Majority is complete and hold. Majority accepts on ties (at least ones), matching the size test. A projection gives only many-one Majority-hardness, which already places Unconstrained-Infinite Energy outside , whereas the preceding completeness uses that Majority is -complete under Turing reductions. Summarizing, Unconstrained-Infinite Energy sits at , a sharp drop from the NP-hardness of the full game.
Infinite Energy is NP-Hard
We reduce from Hamiltonian Path.
Definition 13 (Hamiltonian Path). Given an undirected graph , decide whether has a Hamiltonian path: an ordering of all vertices such that for every .
Hamiltonian Path is NP-complete [GJ79].
Theorem 14. Infinite Energy is NP-hard.
Construction. Given with , build an instance as follows.
Node boards. For each a board with two sockets.
Anchor board. One board with three sockets.
Source. A single source , so .
Thus and . The connectability matrix permits exactly the following wires (and their symmetric entries):
(a) (the two anchor sockets, only to each other).
(b) and for every and .
(c) whenever (, ).
All other entries of are 0. The construction is polynomial: sockets and an matrix filled directly from the adjacency relation of . See Figure 4.
Correctness
Lemma 15 (Completeness). If has a Hamiltonian path, then is winnable.
Proof (sketch). Wire , form the anchor loop , disconnect , then follow the Hamiltonian path, wiring board by board. Full proof in Appendix § 8.

Figure 4. (a) Given an arbitrary graph (on the left), we construct a game instance (on the right) where the connectability conditions correspond to the edges of the graph. (b) A HamPath on the graph corresponds to a winning final configuration and vice-versa. The anchor board is energized by connecting to the power source and then creating a loop of size 2 to sustain the energy.
Lemma 16 (Soundness). If is winnable, then has a Hamiltonian path.
Proof (sketch). Only has three sockets, so the sole charged loop is . Energy leaves only through , and the degree-two node boards force the energized region to be a single simple path visiting every one, i.e. a Hamiltonian path. Full proof in Appendix § 8.
Lemmas 15 and 16 prove Theorem 14.
Upper bounds: PSPACE, and NP modulo a conjecture
A win is defined by a play, a sequence of moves, not by a static picture: the same final wiring can be a win or a dead position, depending on whether its loops were ever charged. A game state is captured by the pair (current wiring, currently energized set), which takes polynomially many bits, and the next state is a function of the state and the move (Appendix § 7). Deciding whether a winning state is reachable from the empty wiring is therefore a reachability question over a state graph whose states have polynomial size.
Theorem 17. Infinite Energy PSPACE.
For NP the certificate is a winning play, and two facts would suffice (Appendix § 7): a play is verifiable in time polynomial in its length (Proposition 25), and every winnable instance has a short winning play (Theorem 30). The obstacle to the second is that a win can require temporary batteries, loops charged only to be broken again. A seven-socket instance is winnable yet has no play that never breaks a charged loop (Proposition 26), so the natural “charge and keep” strategy fails outright. However, no socket ever needs its loop charged twice. Plays with this property, which we call recharge-free, have only charged loops (Lemma 28), and we conjecture that one of polynomial length always exists (Conjecture 29).
Theorem 18. Infinite Energy is NP-hard (Theorem 14) and lies in PSPACE (Theorem 17). If Conjecture 29 holds, then Infinite Energy is NP-complete.
Geometric Realizability of Connectability Matrices
The connectability matrix abstracts a physical layout. In the real game two sockets are joinable when they lie within a fixed wire length. We ask whether requiring to come from points in weakens the hardness of Infinite Energy. In high dimension, geometry imposes no restriction, and hardness survives even in fixed, small dimension.
Definition 19 (k-realizable matrix). Let . A symmetric matrix with zero diagonal is -realizable if there exist a map and a threshold such that, for all distinct ,
Equivalently, is the adjacency matrix of a distance-threshold graph in .
Universal realizability in
Theorem 20. Every symmetric with zero diagonal is -realizable.
The proof is in Appendix C. The reduction of Section 4 produces an arbitrary connectability matrix, and Theorem 20 places the sockets and sources of that matrix at points of whose pairwise distances put a wire exactly between the pairs allows. The hardness of Infinite Energy therefore persists under this geometric restriction.
Corollary 21. Infinite Energy is NP-hard, and NP-complete if Conjecture 29 holds, even when is required to be realizable in .
Hardness in fixed dimension
Corollary 21 leaves open whether hardness needs growing dimension. It does not. The reduction of Section 4 does not transfer directly: there the anchor socket is connectable to every node socket, which is what lets a Hamiltonian path begin at any vertex. In a fixed-dimensional realization a single socket cannot sit within the threshold of arbitrarily many node boards spread across the lattice. We remove this requirement by fixing the start of the path, so that the anchor need only reach one node board.
Definition 22 (Anchored Hamiltonian Path). Given a graph and a vertex , decide whether has a Hamiltonian path with as an endpoint.
Lemma 23. Anchored Hamiltonian Path is NP-complete even when comes with a grid embedding in which the endpoint has degree one and is the strictly highest vertex, so no other vertex lies in the row of or above it.
Proof (sketch). Reduce from Hamiltonian path between two specified boundary terminals of a grid graph [IPS82]. Attach to an arm of new degree-two grid vertices that leaves the bounding box through empty exterior cells and ends, above the whole figure, in a degree-one tip . Attach a similar arm to ending in . The arms force to be the path’s endpoints, and is placed as the highest vertex. Full proof in Appendix § 8.
Theorem 24. For every fixed , no-color Infinite Energy is NP-hard (and NP-complete if Conjecture 29 holds) even when is realizable in .
Proof (idea). Place each grid vertex’s two-socket board at its lattice point (sockets at ), so boards are connectable iff the vertices are grid-adjacent, and put the anchor and source in the empty half-plane above the graph, reaching only the degree-one terminal . The reduction of § 4 then applies with the path forced to start at . Full construction in Appendix § 8, with a worked example in Appendix § 12.
Membership: verification, PSPACE, and recharge-free plays
Fix an instance , with implicit edges and completion graph (Definition 3). A plug wire joins two sockets. A source wire has its tail in . A loop is an alternating directed cycle of (Definition 4), which uses at least one plug wire.
Energization is history-dependent
A charged loop keeps its sockets energized after its source is gone, so which sockets are energized depends on the play so far, not on the current wiring alone. Fix a play (Definition 6). Put and, for , let be the sockets lying on some directed cycle of that uses a plug wire and all of whose sockets are in . Let be the least with closed under flow ( and imply ). A board is energized at if it meets . The play wins at if carries no source wire and every board is energized at , i.e., the instance is winnable if some play wins.
This agrees with Definition 4. A directed cycle using a plug wire and lying in contains an alternating loop through that wire, so is the flow-closure of the charged alternating loops’ sockets. The extra sockets it may name (coboard sockets carrying no wire) are energized anyway, so is unchanged. A loop, once all its sockets are in while its wires stand, remains in thereafter, which is the self-sustaining property of Figure 2.
Proposition 25. Whether a play of length wins is decidable in time polynomial in and .
Proof. Compute in order. Given , restrict to and take its strongly connected components. A socket lies in iff its component contains a plug wire, since then it sits on a directed cycle through that wire inside . Then is the set reachable from in , by one graph search. Each step costs , and there are . Finally check that has no source wire and every board meets .
A polynomial-space bound
Proof (of Theorem 17). A configuration is a wire set with each node on at most one wire, hence at most plug wires and source wires, described in bits. A state is a pair with , again of polynomial size. By §A.1 the successor of under a legal move is , where is a function of and computable in polynomial time. Winning states (no source wire, every board in ) are recognizable in polynomial time. Deciding whether a winning state is reachable from in this graph of states is in .
A win can require temporary batteries
A win may charge a loop only to break it later, using the loop as a battery that keeps a board energized while other sockets are rewired. Batteries are not a convenience: some instances cannot be won without one. Call a play monotone if , that is, if no charged loop is ever broken.
Proposition 26. Some winnable instance has no monotone winning play.
Proof. Let , with these three sets as the boards, a single source , and
The source reaches board only at and board only at . Writing for a disconnect, the play
wins: it lights from the source at , charges the battery loop , unplugs the source, relays energy through the freed socket by to charge the loop , dismantles the battery to free , installs the delivery , and relights from the now self-sustaining board by . The final wiring carries no source wire and energizes all three boards.
No monotone play wins. To close , board must be energized with free, so energy must enter at the spare . The only wire at is , so it arrives from , and must be energized yet free to carry . Board must therefore be lit while is free. The source meets that board only at , so it cannot light it without holding , and , still uncharged at this point, cannot deliver into it. So the board is lit by one of its own loops, and only avoids . Thus every win charges the loop , which uses . The only wire into board is , so the win must also deliver through . A monotone play never breaks , so stays occupied and can never be installed. Hence the instance is winnable but not monotone-winnable, and the battery is unavoidable.
Recharge-free plays and membership
The winning play above breaks a loop but never rebuilds one: each socket enters at most once. Call a play recharge-free if for every socket the set of steps with is an interval, so that once a loop through is broken, no loop through is ever charged again. Recharge-freeness is strictly weaker than monotonicity: it allows the discharges that Proposition 26 forces, but forbids charging any socket twice.
The charging macro. Let be a charged wiring we will not disturb and a loop with a chosen closing wire . A support witness for over is a simple directed path with a valid wiring, both endpoints of free in it, and running from a source or a socket energized by to a socket off but on a board of .
Lemma 27 (Charging macro). If is charged and is a support witness over , then can be charged in moves without disturbing .
Proof. Add the wires of and of . The witness makes this valid. Energy from ’s origin reaches its endpoint, and the arc carries it around every board of , so all their sockets are energized while both endpoints of stay free. Add : the cycle is present with all its sockets energized at the previous step, so it becomes sustaining by the recurrence of §A.1. Remove . The wires of remain, so stays charged. A simple path and a loop use wires.
Lemma 28. In a recharge-free play the loops that ever become charged are pairwise socket-disjoint. Hence at most loops are charged in all.
Proof. A socket carries at most one wire, so it lies on at most one loop at any step. If two loops charged at different steps shared a socket , then would leave sus when the first loop broke and re-enter it when the second charged, which recharge-freeness forbids. So the charged loops are pairwise socket-disjoint, and each uses at least two sockets.
Conjecture 29 (Recharge-free suffices). Every winnable instance has a recharge-free winning play of length polynomial in .
Theorem 30. If Conjecture 29 holds, then Infinite Energy .
Proof. A play of polynomial length is verified in polynomial time (Proposition 25), so it is an NP certificate.
By Lemma 28 a recharge-free play charges only loops, each by an macro (Lemma 27). The content of Conjecture 29 is that the routes and discharges between these charges stay short, equivalently that a forced discharge never has to be undone. Across all instances with and several million further instances up to , every winnable instance had a recharge-free winning play, and no shortest winning play ever recharged a socket. Whether some family instead forces a recharge, and with it a superpolynomial minimal play, is open. Such a family would place Infinite Energy above NP and make the PSPACE bound of Theorem 17 close to tight.
Omitted proofs
Proof of Sufficiency in Theorem 7
Proof (of sufficiency). Fix a source and a board with , labelling its sockets
Bootstrap. Wire (energizing ), then wire . The pair now forms a loop (wire , implicit edge ), and it is charged because is energized. Disconnect . The loop persists, so stays energized, and its remaining sockets are free and energized.
Chaining. Maintain a pool of free energized sockets, initialized to the leftover sockets of . Process the remaining boards in order of non-increasing size. To energize a board , draw a wire from some to a socket . This consumes and but energizes all of , returning its other sockets to . The net increase to is .
Processing larger boards first means every board with (net change ) is handled before any singleton (net change ). When the first singleton is processed the pool has size , and the number of singletons is exactly . Their difference is by (i). Hence never empties prematurely, every board ends up energized, and no source is connected.
Proof of Lemma 8
Proof. contains at least one loop . Each socket of is incident to exactly one wire and one implicit edge, and the implicit edge joins it to its loop-neighbour on the same board. Hence every board meeting contributes at least two sockets to it. The sockets of are all wire-saturated, so for ever to have been charged, energy must have entered it through an implicit edge from a socket not on , lying on a board that also contains -sockets. That board has at least two -sockets plus this extra one, so , contradicting the assumption.
Proof of Lemma 9
Proof. In all remaining wires are socket–socket. Let be their number. Each wire uses two socket slots and each socket holds at most one, so .
Contract each board to a single node, turning each wire into a directed edge between board-nodes (an intra-board wire becomes a self-loop). Call the result , with exactly edges. Energy enters a board only through a wire into one of its sockets (implicit edges stay within a board), so every energized board has in-degree at least 1 in . As all boards are energized, . Combining, , i.e. .
Proof of Lemma 15 (Completeness)
Proof. Let be a Hamiltonian path. Wire , energizing , then wire to form a charged loop, and disconnect . Now is self-sustaining and is free and energized.
Wire , energizing . For , the edge permits the wire , which energizes the next board. No source is connected and every board is energized, so is winnable.
Proof of Lemma 16 (Soundness)
Proof. Consider a winning final configuration : no source is connected, yet every board is energized. With no sources, all energy originates from charged loops. Recall (proof of Lemma 8) that any charged loop must contain a board with at least three sockets. The only such board is , so every charged loop uses an anchor socket. Since is not connectable to or , the only loop on is . Hence it is the sole source of energy, and the node boards carry no loop of their own.
Every node board is therefore energized by a directed path of wires and implicit edges starting at . The only wire leaving goes from (its single free socket) to one node board. Each node board has exactly two sockets, each holding at most one wire, so once energy enters a board through one socket it can leave only through the other. The energized region is thus a single simple path
visiting distinct node boards. As all boards are energized, the path visits every one, so is a permutation of . Each step uses a wire, which exists only when . Hence is a Hamiltonian path in .
Proof of Lemma 23
Proof. Membership is immediate (a path is a certificate). For hardness we reduce from the following form of grid-graph Hamiltonian path, which is NP-complete [IPS82]: given a grid graph and two vertices on the outer boundary of its embedding, decide whether has a Hamiltonian – path. Boundary terminals are what the standard construction produces. The only feature of the instance we use is that and each have an empty orthogonally adjacent exterior cell. Let sit inside a bounding box. From route a self-avoiding path of new grid vertices: step first into that empty neighbour, then move through exterior cells that stay at least two cells away from every vertex of , out of the bounding box and up, ending in a tip strictly above the box. Staying two cells clear makes the new vertices adjacent only to one another (and to at the first step), so the arm is a chain of degree- vertices with a degree-one tip and creates no other adjacency with . Routing it above the box makes the strictly highest vertex. Attach a like arm to ending in a tip , routed through the exterior on the opposite side and kept two cells clear of the first arm so the two do not interfere. The augmented graph is a grid graph. Because each arm is a chain of degree- vertices, any Hamiltonian path of must traverse each arm end to end, and since have degree one they are forced to be the two endpoints. Deleting the arms turns a Hamiltonian path of into a Hamiltonian – path of , and conversely any such path extends through the arms. Hence , with highest and of degree one, has a Hamiltonian path with endpoint iff has one from to .
Proof of Theorem 24
Proof (sketch). It suffices to treat , since any realization embeds in by padding with zeros. We reduce from Anchored Hamiltonian Path on a grid graph with (Lemma 23). Fix and threshold .
Node boards. For each grid vertex create a board . For adjacent vertices, horizontal or vertical, every socket pair is within : the farthest such pair is at distance . For diagonal vertices the nearest pair is at distance , and farther pairs are larger. Thus two node boards are connectable iff their vertices are grid-adjacent, and, as in Section 4, all four socket pairings between adjacent boards are available, so a Hamiltonian path can use distinct incoming and outgoing sockets at every internal board. (Intra-board pairings are immaterial: by Lemma 8 no two-socket board can sustain a charged loop.) Every node board has diameter .
Anchor and source. By Lemma 23 embed with its strictly highest vertex and place at the origin, so every other vertex has and the region is empty. Put , , , , with anchor board and source . One checks: (the anchor’s loop). , so connects to , while and are both and , so is not wireable to and reaches only . Every other node board lies at , at distance from all four points.
This matrix is realized in and matches the construction of § 4 with the single change that is wireable only to . Hence the only anchor loop is , energy leaves only through into , and the degree-two node boards force a single simple path covering them all. The completeness and soundness arguments of Theorem 14 then go through, now with the path forced to start at : is winnable iff has a Hamiltonian path with endpoint . See Figure 6 for an example reduction.

Figure 6. (a) Arbitrary grid graph on which a Hamiltonian Path must begin at the highlighted node. An edge exists between adjacent nodes on the grid. (b) Corresponding game instance, where the dotted lines denote connectability governed by a distance threshold. The reduction of Theorem 24, drawn schematically. (a) A grid graph whose Hamiltonian path must end at the highlighted degree-one terminal . (b) The game instance: each vertex becomes a two-socket board at its lattice point, so two boards are connectable (dotted lines, distance ) iff the vertices are grid-adjacent. The anchor board and source sit in an empty region beside and reach only ’s board. In the reduction proper (Theorem 24) is placed as the highest vertex with the anchor in the empty half-plane above it. Further examples are at https://infinite-energy-peer-review.netlify.app.
Proof of Theorem 12
Proof. Let with ones. Map to the instance with one board per bit:
Here and , giving
Moreover, when and some bit is 1, so some board has three sockets and the second condition of Theorem 7 holds automatically. When the size condition already fails. Thus the instance is accepted iff has a majority of ones. Each output board depends on a single input bit, so the map is a projection, and every projection is an reduction. Since Majority is -complete under Turing reductions [Vol99], and Unconstrained-Infinite Energy (Proposition 11), the problem is -complete under Turing reductions.
Proof of Theorem 20
Proof. Write and pick , so that is positive semidefinite. Then is a Gram matrix: there are vectors with . Hence for all , and for , so
Choosing threshold separates the two cases: .
It remains to reduce the dimension. Translate by anchoring : set , so and for all . The threshold graph is unchanged. The lie in , a space of dimension at most . Identifying it with via an orthonormal basis realizes in . For further background, see standard sources such as [HK01,LLR95].
Remark 31. Theorem 20 is an existence statement about the matrix, so Corollary 21 classifies the variant whose input is a matrix promised to be realizable. The coordinates it produces are real and need not have polynomial bit-length. The fixed-dimension reduction of Theorem 24 is different: it outputs explicit rational coordinates (lattice points offset by , threshold ) of polynomial precision, so it is a reduction to the explicit-coordinate problem.
Example of the reduction
Extension: the color-constrained variant, and open directions
This appendix records the colored extension and the questions it raises. The only complexity result here is an easy inherited hardness, and the more interesting questions are open. We give the model, note NP-hardness, and explain why the colorless membership argument does not carry over.
We extend the colorless game of § 1 with colors. The mechanic is the additive mixing of light: combining colored beams only ever adds primaries, never removes them, so mixing is modeled by union and named colors are abbreviations for subsets of primaries.
Color algebra. Fix a finite set of primary colors . The figures use the three additive primaries red, green, and blue. A color is a nonempty subset of , and . Colors mix by union, , an operation that is commutative, associative, and idempotent. The familiar names label elements of :
We adjoin a distinguished symbol denoting the any-color requirement.
Instance. Extending Definition 1, a colored instance adds to a colorless instance two maps:
assigns a color to each power source.
assigns a color requirement to each board.
Configurations, wires, implicit edges, loops, and the energized sets are exactly as in Section 1 and Appendix A. Colors are on top of energization and do not affect which sockets are energized.
Color propagation. Fix a play (energization is as in Appendix A). Color accumulates along the play by the same flow, and transmission is gated by energization: a socket passes its color along an edge only while it is energized. For a socket , its color is the least solution of
i.e. the union of the colors of every source whose energy has reached at any point, propagated forward through wires, implicit edges, and around charged loops. We take this permanent-memory model: a socket keeps every primary it has ever received, so never shrinks, but by the gate it passes color on only while energized. For definiteness for a source , and for a socket never energized by step . Retaining a color while dark thus differs from transmitting one: on two singleton boards , wiring a red source to , unplugging it, then adding leaves colorless, because is dark when is present. A reset-on-de-energization variant is a different model with a different recurrence. The effective color of an energized board at time is
See Figure 7 and Figure 8 for examples.
Figure 7. A colored play. (a) The initial configuration. The rectangle on the top right of each board shows its color requirement , and the source cannot reach the lower one-socket board because forbids the wire (too far away). (b) In step 1 the source is wired into the board whose requirement is blue. In step 2 a loop is formed on that board. (c) In step 3 (dotted) the source is disconnected and in step 4 the now self-sustaining board energizes the lower board through a cross-board wire. Every board meets its requirement, so the instance is won.

Figure 8. Color mixing and propagation on a loop. (a) A socket on a board sustained by a purple loop exports purple. (b) A blue loop spanning four sockets on two boards. (c) Disconnecting the blue source and then connecting a red source turns the loop purple (blue red), and the new color propagates to all four sockets and both boards’ colors gets updated. Panel (c) shows why the order of source connections and disconnections matters in the colored game.
Board satisfaction and the decision problem. A board is satisfied at if it is energized in and its requirement is met exactly:
Colored Infinite Energy Given a colored instance , does there exist a play whose final configuration connects no source yet leaves every board satisfied?
Hardness.
Proposition 32. Colored Infinite Energy is NP-hard.
Proof. Colorless Infinite Energy is the special case in which color is vacuous. Given a colorless instance , take a single primary , set for every , and for every . Then every energized board is satisfied, so the colored instance is winnable iff the colorless one is. The map is identity on and constant on , hence a polynomial-time (indeed projection) reduction. NP-hardness follows from Theorem 14.
Open problems. The upper bound is open, and for a sharper reason than in the colorless case. There, whether a board is energized does not depend on the order in which sources are used, which is what the short-play route (Theorem 30, itself conditional) exploits. With colors the requirement is an exact match while color only accumulates (Figure 8), so a board can be over-colored and never corrected. Meeting every requirement at once then constrains the order in which sources are connected and disconnected across the whole play, which the final configuration does not record. We leave three questions. (i) Is colored Infinite Energy in NP? (ii) Is it hard for a class above NP? It is in PSPACE by the state-space bound of Theorem 17, which applies verbatim once colors are added to the state. (iii) Does the reset-on-de-energization model differ in complexity from the permanent-memory one above?
References
- [1]S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
- [2]G. Aloupis, E. D. Demaine, A. Guo, and G. Viglietta. Classic Nintendo games are (computationally) hard. Theoretical Computer Science, 586:135–160, 2015.arxiv.org/abs/1203.1895
- [3]M. de Bondt. The computational complexity of Minesweeper, 2012. arXiv preprint arXiv:1204.4659.arxiv.org/abs/1204.4659
- [4]M. Forísek. Computational complexity of two-dimensional platform games. In P. Boldi and L. Gargano, editors, Fun with Algorithms (FUN 2010), volume 6099 of LNCS, pages 214–227. Springer, 2010.DOI
- [5]M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- [6]R. A. Hearn and E. D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1–2):72–96, 2005.DOI
- [7]R. A. Hearn and E. D. Demaine. Games, Puzzles, and Computation. A K Peters, 2009.DOI
- [8]R. A. Hearn. The complexity of sliding-block puzzles and plank puzzles. In B. Cipra, E. D. Demaine, M. L. Demaine, and T. Rodgers, editors, Tribute to a Mathematician. A K Peters, 2004.
- [9]P. Hliněný and J. Kratochvíl. Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Mathematics, 229(1–3):101–124, 2001.DOI
- [10]A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676–686, 1982.DOI
- [11]R. Kaye. Minesweeper is NP-complete. The Mathematical Intelligencer, 22(2):9–15, 2000.DOI
- [12]N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.
- [13]H. Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999.


