Nurse Rostering

Every week, in every hospital on Earth, someone has to build a roster: a grid that says which nurse works which shift. It looks like clerical work — drop names into boxes — but it is a knot of rules pulling in opposite directions.

Each shift needs enough nurses, and the right skills on hand (you can't staff an intensive-care night with only trainees). Nobody may work a night shift followed by a morning shift — the law and basic safety forbid it. People have days off, training, and preferences they would like honored. Satisfy one rule and you often break another.

Doing this by hand eats a head nurse's entire afternoon, every week. And the reason it is so painful is not bad luck or bad software. It is that nurse rostering belongs to the family of problems that, as far as anyone knows, have no fast solution at all.

Below is a tiny ward: 4 nurses and a 3-day plan with a day and a night shift each day. Click a cell to put a nurse on that shift; click again to remove them. As you go, every broken rule lights up.

The rules are: each shift needs exactly 2 nurses; no nurse may work a night then the next morning; nurse D is a trainee and cannot cover a night alone-skilled slot; and nurse A has requested day 2 off.

<p class="hint">{{hint}}</p>
<div class="grid-wrap">
  <table class="roster" id="roster"></table>
</div>
<ul class="rules" id="rules"></ul>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</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; }
.grid-wrap { overflow-x: auto; }
table.roster { border-collapse: collapse; margin: .2rem 0 .6rem; }
.roster th, .roster td { border: 1px solid #cdd9e3; text-align: center; padding: 0; }
.roster th { background: #e8eef3; color: #1d3557; font: 700 13px system-ui; padding: .35rem .5rem; }
.roster td.lab { background: #f3f6f9; color: #1d3557; font: 700 13px system-ui; padding: .35rem .6rem; white-space: nowrap; }
.cell { width: 64px; height: 40px; display: flex; flex-wrap: wrap; gap: 2px;
        align-items: center; justify-content: center; cursor: pointer; }
.chip { font: 700 12px ui-monospace, monospace; padding: 1px 5px; border-radius: 6px;
        background: #c9ccd1; color: #333; }
.chip.on { background: #1d3557; color: #fff; }
td.bad { background: #fdeaec; }
.rules { list-style: none; padding: 0; margin: .4rem 0; font-size: .85rem; }
.rules li { padding: 2px 0 2px 22px; position: relative; color: #555; }
.rules li::before { content: "•"; position: absolute; left: 6px; color: #c92f3c; font-weight: 700; }
.rules li.ok { color: #0a7d33; }
.rules li.ok::before { content: "✓"; color: #0a7d33; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking a finished roster is effortless: scan each rule and count. Finding an assignment that breaks no rule — and ideally honors preferences too — is the hard part. Press Auto-solve and the computer simply tries layouts until one fits. With a handful of cells that's already thousands of combinations; add nurses and days and the count explodes.

How hard is nurse rostering, really? Not the typing — the solving.

• Checking a candidate roster is trivial: walk over each rule and verify coverage, rest gaps, skills and requests. This is polynomial time.
• Brute force tries every way to assign nurses to shifts. With n nurses, s shifts and per-shift choices, the number of rosters grows exponentially — hopeless once a real ward has dozens of staff and a month of shifts.
• It's NP-hard. The decision version — "is there any roster that satisfies all the hard constraints?" — is NP-complete, and the real goal (the best roster under preferences and costs) is the NP-hard optimization on top. You can encode classic NP-complete problems such as graph coloring and constraint satisfaction directly into rostering rules, so a fast rostering algorithm would crack them all.
• So even deciding is-this-ward-staffable is as hard as anything in NP. There is no known method that beats exponential search in the worst case.

That is the punchline: nurse rostering isn't tedious because hospitals are disorganized. It is a genuine instance of the same wall behind P vs NP — the line between problems we can check quickly and problems we can actually solve quickly.

"Cover all the demand while breaking none of the rules" is one of the most common shapes a real problem can take, and nurse rostering is its human face:

• Crew scheduling: airlines and railways assign pilots, attendants and drivers under rest laws and qualifications — the same constraints, higher stakes.
• Workforce shifts: call centers, factories and retail stores all build rotas that must cover demand without overworking anyone.
• Timetabling: school and university timetabling is the same problem with rooms and teachers instead of wards and nurses.
• Real solvers: hospitals don't brute-force. They use integer programming, constraint solvers and metaheuristics that find good enough rosters fast, even when optimal is out of reach.

Understand why rostering is hard and you've met the whole world of scheduling — and why "the schedule could always be a little better" is not laziness but mathematics.

Nurse rostering hides a hard truth in plain sight: the same grid a head nurse fills in by hand encodes constraint satisfaction, graph coloring and an optimization problem that is NP-hard. Checking a roster stays instant; finding the best one — or even any one that fits every rule — is as hard as anything in computer science.

So the next time a shift plan feels like it could be just a little fairer, take comfort: it's not that nobody tried hard enough. You've run into P vs NP wearing scrubs, and the best real schedulers settle for good enough precisely because perfect may be forever out of reach.