The desert wells have run dry and the palm groves are withering. You carry only a handful of norias — great water wheels that flood the ground around them.
Cover the most palms you can — then watch a real optimizer prove the best possible placement.
Five oases, five coverage puzzles — here's how your irrigation compares to the proven best.
You have a few norias, each watering every palm inside a circular radius. There are never enough wheels for every grove, so you must choose where to put them to revive the most palms.
That is exactly the Maximal Covering Location Problem — a classic in Operations Research: place a limited number of facilities to cover as much demand as possible.
Even a small oasis has a huge number of ways to position the wheels — far too many to try one by one.
So instead of guessing, we describe the choice precisely. For every candidate tile j a yes/no variable yj is 1 when a noria sits there. For every palm i, zi is 1 when at least one chosen noria reaches it.
The whole puzzle becomes a compact 0/1 integer linear program:
maximize Σ zᵢ (palms watered)
subject to
zᵢ ≤ Σⱼ∈Nᵢ yⱼ a palm counts only if a noria reaches it
Σⱼ yⱼ ≤ p you have only p norias
zᵢ ∈ {0, 1}
yⱼ ∈ {0, 1}
Water the most palms · respect each palm's set of reaching tiles Ni · never place more than p wheels.
HiGHS — a state-of-the-art open-source optimizer, here compiled to WebAssembly and running live in your browser — searches with branch-and-bound and cutting planes, and proves the coverage is the best possible, not merely a good one.
The same maths places ambulance stations, cell towers, EV chargers and warehouses — only with thousands of sites instead of a handful of water wheels.
Use case: facility & warehouse location ▸ Follow me for more games ▸