Introduction

In 1812, Governor Elbridge Gerry of Massachusetts signed off on a district so contorted it looked like a salamander. A newspaper fused the two words — "gerrymander" — and the name stuck. Two centuries later the trick is the same: keep every vote exactly as it is, and just redraw the boundaries so your side wins more seats.

The arithmetic is brutally simple. Suppose a region splits 50/50 between two parties. Group your opponents tightly into a few districts they win in landslides ("packing"), and spread your own voters thinly so they win many districts by small margins ("cracking"). Not a single person changed their mind, yet the seat count can swing from a tie to a rout.

That raises a precise question for a computer: given the voters and where they live, does a map exist that gives my party a majority of seats? It turns out this is not just politically thorny — it is among the computationally hardest problems we know.

Redraw the Lines

Below is a 5×5 grid of voters: each cell is blue or red. There are 13 blue and 12 red, so blue is the majority. The grid is carved into 5 districts of 5 cells each, and a district is won by whichever color holds the majority of its cells. Pick a preset and watch the seat totals.

<p class="hint">A 5×5 grid of voters: <b class="bl">blue</b> and <b class="rd">red</b>.
    There are 13 blue and 12 red — <b>blue is the majority</b>. The grid is cut into 5
    districts of 5 cells; each district goes to its majority color. The votes never
    change — only the borders do. Pick a map and watch the seats.</p>
<div class="presets">
  <button data-map="0" type="button" class="active">Fair map</button>
  <button data-map="1" type="button">Favor blue</button>
  <button data-map="2" type="button">Gerrymander for red</button>
</div>
<div id="grid" class="grid"></div>
<div class="tally">
  <div class="bar"><span id="seatBlue" class="seg seg-bl"></span><span id="seatRed" class="seg seg-rd"></span></div>
  <div id="score" class="score"></div>
</div>
<div id="note" class="note"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.bl { color: #2a6fdb; } .rd { color: #d23b4e; }
.presets { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
.presets button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
  background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }
.presets button.active { background: #1d3557; color: #fff; }
.grid { display: grid; grid-template-columns: repeat(5, 52px); grid-template-rows: repeat(5, 52px);
  gap: 0; width: max-content; margin: 0 auto; }
.cell { width: 52px; height: 52px; display: flex; align-items: center; justify-content: center;
  font: 700 16px ui-monospace, monospace; color: rgba(255,255,255,.9); position: relative; }
.cell.b { background: #4a86e8; } .cell.r { background: #e8616f; }
/* thick district borders are drawn where neighbouring districts differ */
.cell.t { border-top: 3px solid #16233a; } .cell.l { border-left: 3px solid #16233a; }
.cell.rt { border-right: 3px solid #16233a; } .cell.bm { border-bottom: 3px solid #16233a; }
.tally { margin: .9rem auto 0; max-width: 320px; }
.bar { display: flex; height: 26px; border-radius: 6px; overflow: hidden; border: 1px solid #cdd9e3; }
.seg { display: flex; align-items: center; justify-content: center; color: #fff; font: 700 13px system-ui; transition: flex-grow .35s; }
.seg-bl { background: #2a6fdb; } .seg-rd { background: #d23b4e; }
.score { text-align: center; font: 700 1.05rem system-ui; margin-top: .5rem; }
.note { text-align: center; font-size: .9rem; color: #555; margin-top: .5rem; min-height: 2.8em; line-height: 1.4; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Gerrymandering demo. The voters are FIXED: 13 blue (1) and 12 red (0).
    Three maps partition the same 25 cells into 5 connected districts of 5 cells
    each. A district's seat goes to its majority color. Same votes, different
    borders, different seat totals — the core of why districting is manipulable
    (and why finding the optimal map is NP-hard). Every map below is verified:
    5 equal connected districts, no ties. */
const N = 5;
// 1 = blue, 0 = red. Row-major, 25 cells, exactly 13 ones.
const VOTES = [
  1,0,1,1,1,
  0,0,1,0,1,
  1,0,1,1,1,
  0,0,0,1,0,
  0,1,0,1,0
];
const idx = (r,c) => r*N + c;

/* Each map gives the district id (0..4) of every cell. All three are connected
    and split the 25 cells into five groups of five. */
// MAP 0 — a fair-looking map: blue’s majority yields a proportional 3–2.
const MAP_FAIR = [
  3,3,3,3,1,
  0,0,3,1,1,
  0,2,2,2,1,
  0,4,2,2,1,
  0,4,4,4,4
];
// MAP 1 — drawn to favor blue: blue takes 4 of 5 seats.
const MAP_BLUE = [
  3,3,3,4,4,
  3,2,1,4,4,
  3,2,1,0,4,
  2,2,1,0,0,
  2,1,1,0,0
];
/* MAP 2 — gerrymandered: red, the MINORITY of voters, wins 3 of 5 seats by
    packing blue into a couple of landslide districts and cracking the rest. */
const MAP_GERRY = [
  4,4,4,4,4,
  1,1,1,2,2,
  1,1,2,2,2,
  3,3,0,0,0,
  3,3,3,0,0
];
const MAPS = [MAP_FAIR, MAP_BLUE, MAP_GERRY];

function tally(map){
  const cells = [[],[],[],[],[]];
  for(let i=0;i<25;i++) cells[map[i]].push(i);
  let blue=0, red=0; const per=[];
  for(const ds of cells){
    const b = ds.filter(i=>VOTES[i]===1).length;
    const w = b > ds.length - b ? 'b' : 'r'; // 5 cells => never a tie
    if(w==='b') blue++; else red++;
    per.push(w);
  }
  return {blue, red, per};
}

function render(mapId){
  const map = MAPS[mapId];
  const g = document.getElementById('grid'); g.innerHTML='';
  for(let r=0;r<N;r++)for(let c=0;c<N;c++){
    const i = idx(r,c);
    const d = document.createElement('div');
    d.className = 'cell ' + (VOTES[i]===1?'b':'r');
    if(r===0   || map[idx(r-1,c)]!==map[i]) d.classList.add('t');
    if(c===0   || map[idx(r,c-1)]!==map[i]) d.classList.add('l');
    if(c===N-1 || map[idx(r,c+1)]!==map[i]) d.classList.add('rt');
    if(r===N-1 || map[idx(r+1,c)]!==map[i]) d.classList.add('bm');
    d.textContent = VOTES[i]===1 ? `B` : `R`;
    g.appendChild(d);
  }
  const t = tally(map);
  const sb = document.getElementById('seatBlue'), sr = document.getElementById('seatRed');
  sb.style.flexGrow = t.blue || 0.001; sr.style.flexGrow = t.red || 0.001;
  sb.textContent = t.blue ? t.blue : ''; sr.textContent = t.red ? t.red : '';
  document.getElementById('score').innerHTML =
    fmt(`<span class="bl">Blue %blue%</span> &nbsp;–&nbsp; <span class="rd">Red %red%</span> seats`, { blue: t.blue, red: t.red });
  const notes = [
    `Fair map: blue’s narrow majority of voters earns a proportional 3–2 majority of seats.`,
    `Favor blue: same votes, but careful lines give blue 4 of 5 seats — its majority is amplified.`,
    `Gerrymander: red is the MINORITY of voters, yet wins 3 of 5 seats by packing blue into landslide districts and cracking the rest.`
  ];
  document.getElementById('note').textContent = notes[mapId];
  console.log(`Map`, mapId, `-> Blue`, t.blue, `Red`, t.red, `| winners`, t.per.join(','));
}

document.querySelectorAll('.presets button').forEach(btn=>{
  btn.addEventListener('click', ()=>{
    document.querySelectorAll('.presets button').forEach(b=>b.classList.remove('active'));
    btn.classList.add('active');
    render(Number(btn.dataset.map));
  });
});
render(0);
Result
Console

The votes never change — only the district borders do. A fair map turns blue's narrow voter majority into a 3–2 seat majority; one map stretches it to 4–1; and a gerrymander hands the minority red voters 3 of 5 seats. That swing is the whole game. Checking a finished map is instant: count colors per district. Finding a map that hits a target seat count, while keeping districts equal-sized and connected, is the hard part — and the number of possible maps explodes far faster than any computer can enumerate.

The Real Complexity

How hard is it to draw the best map? Not for a few cells — at the scale of real states.

  • Checking a proposed map is trivial: count the voters of each color in each district and tally the seats.
  • Brute force would enumerate every legal partition of the precincts into equal, connected districts. The number of such partitions grows super-exponentially; even a modest state has astronomically many.
  • It's NP-hard. Formulating "is there a districting that wins party A at least k seats, with districts of equal population and connected on the precinct map?" is an optimization problem that has been proven NP-hard. The connectivity-and-balance constraints let you encode classic hard problems (graph partition, set-packing-style choices) directly into the map.
  • So even deciding whether a target outcome is achievable sits with the SAT-and-friends NP-complete family — and finding the optimal map is at least as hard.

That is the uncomfortable punchline: there is no known efficient algorithm that, in general, finds the map maximizing one party's seats — and unless P vs NP is resolved in the surprising direction, there may be none. Mapmakers don't search all maps; they use heuristics, and so do the courts and watchdogs trying to catch them.

Where It Matters

"Cut this network into balanced, connected pieces to hit some objective" is a shape that shows up far beyond elections:

  • Fair redistricting: because finding the optimal map is intractable, analysts generate huge ensembles of random valid maps (via Markov-chain sampling) and flag an enacted map as a likely gerrymander if its outcome is an outlier.
  • Courtroom evidence: these sampled ensembles have been used in real redistricting lawsuits to argue a map is statistically extreme.
  • Graph partitioning: splitting a circuit, a social network, or a dataset into balanced clusters with few cross-links is the same NP-hard partition core.
  • Logistics and territories: dividing a sales region or delivery zones into balanced, contiguous areas is districting by another name.

Understand why fair maps are hard to find and you've met constrained graph partitioning — the same intractable core behind graph coloring and countless balance-and-connect problems.

Conclusion

Gerrymandering is a vivid reminder that how you slice the data can matter as much as the data itself. The same voters, untouched, can deliver a landslide or a defeat depending only on where the lines fall — and deciding whether a winning map exists is NP-hard.

That hardness cuts both ways. It is why a determined mapmaker can hide an unfair plan among millions of plausible ones, and why reformers fight back not by computing the one fair map — that is intractable — but by sampling the space and spotting the outliers. Behind a salamander-shaped district lies P vs NP, quietly shaping who gets to govern.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/gerrymandering/Content licensed under CC BY-NC 4.0.