Introduction

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.

Build a Roster

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">Click a cell to toggle a nurse onto that shift. Build a roster where <b>every</b> rule is satisfied. Checking a roster is instant — finding a valid one is the hard part.</p>
<div class="grid-wrap">
  <table class="roster" id="roster"></table>
</div>
<ul class="rules" id="rules"></ul>
<div class="status" id="status">Assign nurses, then check.</div>
<div class="btns">
  <button id="check" type="button">Check roster</button>
  <button id="solve" type="button">Auto-solve</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Nurse rostering as a constraint problem. A roster assigns nurses to shift slots; we must satisfy every hard rule. Checking one roster is a quick scan. Finding a valid one in general is NP-hard — brute force tries every subset of nurses per slot.
const NURSES = ['A','B','C','D'];
const DAYS = 3;
const SHIFTS = ['Day','Night'];            // shift index 0 = day, 1 = night
// slot id = day*2 + shift  (0..5).  assign[slot] = Set of nurse letters on that slot.
const NS = DAYS * SHIFTS.length;
let assign = Array.from({length: NS}, () => new Set());

const slotId = (day, shift) => day * SHIFTS.length + shift;

// ---- the hard rules -------------------------------------------------------
// 1) every slot has exactly 2 nurses
// 2) nobody works a Night then the very next Day (morning)
// 3) nurse D is a trainee: may not be on any Night slot
// 4) nurse A requested day index 1 (the 2nd day) off: no slot on that day
const A_OFF_DAY = 1;
function violations(a){
  const v = { coverage:[], rest:[], skill:[], request:[] };
  // coverage
  for(let s=0;s<NS;s++) if(a[s].size!==2) v.coverage.push(s);
  // rest: night on day d, then day-shift on day d+1
  for(let d=0; d<DAYS-1; d++){
    const night = a[slotId(d,1)], morning = a[slotId(d+1,0)];
    for(const n of night) if(morning.has(n)) v.rest.push(n+'@'+d);
  }
  // skill: D on any night
  for(let d=0; d<DAYS; d++) if(a[slotId(d,1)].has('D')) v.skill.push('D@'+d);
  // request: A on the off day
  for(const sh of [0,1]) if(a[slotId(A_OFF_DAY,sh)].has('A')) v.request.push('A@'+A_OFF_DAY);
  return v;
}
function isValid(a){ const v=violations(a); return !v.coverage.length && !v.rest.length && !v.skill.length && !v.request.length; }

// ---- rendering ------------------------------------------------------------
function render(){
  const t = document.getElementById('roster'); t.innerHTML='';
  const head = document.createElement('tr');
  head.innerHTML = '<th></th>' + Array.from({length:DAYS},(_,d)=>fmt('<th>Day %d%%v%</th>', { d: d, v: 1 })).join('');
  t.appendChild(head);
  SHIFTS.forEach((sh, si)=>{
    const tr = document.createElement('tr');
    const lab = document.createElement('td'); lab.className='lab'; lab.textContent=sh; tr.appendChild(lab);
    for(let d=0; d<DAYS; d++){
      const td = document.createElement('td');
      const cell = document.createElement('div'); cell.className='cell';
      NURSES.forEach(n=>{
        const chip=document.createElement('span');
        const on = assign[slotId(d,si)].has(n);
        chip.className='chip'+(on?' on':''); chip.textContent=n;
        chip.addEventListener('click',()=>{ const set=assign[slotId(d,si)];
          set.has(n)?set.delete(n):set.add(n); render(); setStatus('Assign nurses, then check.',''); });
        cell.appendChild(chip);
      });
      td.appendChild(cell); td.dataset.slot=slotId(d,si); tr.appendChild(td);
    }
    t.appendChild(tr);
  });
  paintRules();
}
function paintRules(){
  const v = violations(assign);
  const items = [
    ['Every shift has exactly 2 nurses', v.coverage.length===0],
    ['No night followed by next morning', v.rest.length===0],
    ['Trainee D never on a night shift', v.skill.length===0],
    ['Nurse A is off on Day 2', v.request.length===0],
  ];
  document.getElementById('rules').innerHTML =
    items.map(([txt,ok])=>'<li class="'+(ok?'ok':'')+'">'+txt+'</li>').join('');
  // mark bad slots (coverage only — visually obvious)
  document.querySelectorAll('td[data-slot]').forEach(td=>{
    td.classList.toggle('bad', v.coverage.includes(+td.dataset.slot));
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function check(){
  if(isValid(assign)) setStatus('✓ Every rule is satisfied — valid roster!','ok');
  else setStatus('✗ Some rule is broken. Keep adjusting.','bad');
}

// ---- brute-force solver: pick 2 nurses per slot, try every combination -----
function combos2(arr){ const r=[]; for(let i=0;i<arr.length;i++)for(let j=i+1;j<arr.length;j++) r.push([arr[i],arr[j]]); return r; }
function solve(){
  const slotChoices = [];
  for(let s=0;s<NS;s++) slotChoices.push(combos2(NURSES));   // 6 pairs each
  let tried=0, found=null;
  // odometer over slot choices
  const idx = new Array(NS).fill(0);
  const total = slotChoices.reduce((p,c)=>p*c.length,1);
  for(let k=0;k<total;k++){
    tried++;
    const cand = slotChoices.map((ch,s)=> new Set(ch[idx[s]]));
    if(isValid(cand)){ found=cand; break; }
    // increment odometer
    for(let s=0;s<NS;s++){ if(++idx[s]<slotChoices[s].length) break; idx[s]=0; }
  }
  if(found){ assign=found; render();
    setStatus(fmt('Found a valid roster after trying %tried% of %total% combinations.', { tried: tried, total: total }),'ok');
    console.log('Valid roster found; combinations tried:', tried, 'of', total); }
  else setStatus('No roster satisfies all the rules.','bad');
}
document.getElementById('check').addEventListener('click',check);
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ assign=Array.from({length:NS},()=>new Set()); render(); setStatus('Assign nurses, then check.',''); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

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