Hint active
Deploy Sentinel Beacons within your energy budget to achieve 100% network coverage with zero interference between beacons.
In graph theory, a Dominating Set for a graph G = (V, E) is a subset of vertices D \subseteq V such that every vertex not in D is adjacent to at least one vertex in D. The smallest possible size of such a set is the domination number, denoted \gamma(G).
An Independent Set requires that no two vertices in D share an edge. In SentinelLeft, adjacent beacons interfere with each other's radar frequencies. A set that is both dominating and independent is an Independent Dominating Set (or maximal independent set).
As missions advance, critical command sectors (marked with [2] or [3] and shield segments) require more than one independent direct sentinel link (≥ 2) to be fully secured, synthesizing the classic Japanese puzzle Hashiwokakero (Hashi/Bridges) with k-Dominating Set Theory:
Fortified sectors cannot host beacons. Each must receive its marked number of direct links from separate neighboring sentinels, and those sentinels must not share an edge with each other.
Starting with 16-node maps, some well-connected ordinary zones cost more to occupy. Plain zones cost 1 energy; labels E2 and E3 cost 2 and 3. Cover every zone without exceeding the energy budget. A wider network of cheap beacons can beat a few expensive hubs. Remove a beacon to recover its full cost.
Maps with 20 or more nodes introduce sectors requiring three independent neighboring beacons. Every map is checked for a legal solution within its budget. Endless missions keep combining these constraints on fresh maps.
Finding the minimum dominating set is one of Richard Karp's classic NP-complete problems (1972). It has practical applications in sensor network coverage, facility location, and military defense perimeter optimization.
Left Gaming • Free & Open Source Software
Licensed under the Strong Copyleft GNU General Public License v3.0 (GPL-3.0-or-later)
Every zone secured within budget, with zero beacon interference.