Introduction

Every school faces it each year: fit dozens of classes into a grid of time slots and rooms so that nothing clashes. A teacher can't be in two rooms at once. A student group can't take two subjects in the same slot. A lab can't host two classes simultaneously.

For a handful of classes you can juggle it by hand. But the constraints tangle: solving one clash by moving a class creates another somewhere else, which forces a third move, and soon you're chasing your own tail across the whole grid.

That's timetabling — and beneath the everyday chore sits one of the hard problems. It's a close relative of graph coloring: each class is a node, clashing classes are connected, and a "color" is a time slot. Coloring without conflicts is NP-hard, and so is the timetable.

Build a Timetable

Try it. Each class needs a time slot, but classes that share a teacher or a group can't sit in the same slot. Click a class to cycle its slot; conflicting classes flash red. Try to make every class green at once.

<p class="hint">Six classes, three time slots. Classes that share a <b>teacher</b> or a <b>group</b> can't share a slot. Click a class to move it to the next slot; clashes flash <span class="r">red</span>. Get every class <span class="g">green</span> — or hit Auto-resolve.</p>
<div id="board" class="board"></div>
<p id="status" class="status"></p>
<div class="btns">
  <button id="auto" type="button">Auto-resolve</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<p class="legend" id="legend"></p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.hint .r { color: #c0392b; font-weight: 700; }
.hint .g { color: #0a7d33; font-weight: 700; }
.board { display: grid; grid-template-columns: repeat(3, 1fr); gap: .6rem; }
.col { background: #f6f8fa; border: 1px solid #e6e9ee; border-radius: 10px; padding: .5rem; min-height: 120px; }
.col h4 { margin: 0 0 .5rem; font: 700 13px system-ui; color: #1d3557; text-align: center; }
.tile { background: #fff; border: 2px solid #2a9d8f; border-radius: 8px; padding: .45rem .5rem; margin-bottom: .45rem; cursor: pointer; font: 600 13px system-ui; color: #1d3557; transition: all .12s; }
.tile small { display: block; color: #888; font-weight: 500; font-size: .82em; }
.tile.clash { border-color: #c0392b; background: #fdecea; color: #c0392b; animation: flash .5s; }
@keyframes flash { 0%,100% { background: #fdecea; } 50% { background: #f9c9c2; } }
.tile:hover { transform: translateY(-1px); }
.status { font-weight: 800; min-height: 1.3em; margin: .8rem 0 .5rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c0392b; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }
.legend { font-size: .82rem; color: #777; margin-top: .7rem; line-height: 1.5; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Timetabling = graph coloring. Each class is a node; two classes that share a teacher or a group are connected and must get different slots.
const SLOTS = ['Mon morning', 'Mon afternoon', 'Tue morning'];
// class: name, teacher, group
const CLASSES = [
  { id: 'M1', name: 'Math', teacher: 'Ada',  group: 'A' },
  { id: 'P1', name: 'Physics', teacher: 'Ada', group: 'B' },
  { id: 'C1', name: 'Chemistry', teacher: 'Bo', group: 'A' },
  { id: 'H1', name: 'History', teacher: 'Cy', group: 'A' },
  { id: 'E1', name: 'English', teacher: 'Bo', group: 'B' },
  { id: 'G1', name: 'Gym', teacher: 'Cy', group: 'B' }
];
// edge if same teacher or same group
function conflict(a, b) { return a.teacher === b.teacher || a.group === b.group; }
const N = CLASSES.length;
const EDGES = [];
for (let i = 0; i < N; i++) for (let j = i + 1; j < N; j++) if (conflict(CLASSES[i], CLASSES[j])) EDGES.push([i, j]);

let slot = new Array(N).fill(0); // every class starts Mon morning -> lots of clashes

function clashes() {
  const bad = new Set();
  for (const [i, j] of EDGES) if (slot[i] === slot[j]) { bad.add(i); bad.add(j); }
  return bad;
}

function render() {
  const bad = clashes();
  const board = document.getElementById('board');
  let html = '';
  for (let s = 0; s < SLOTS.length; s++) {
    html += '<div class="col"><h4>' + SLOTS[s] + '</h4>';
    for (let i = 0; i < N; i++) if (slot[i] === s) {
      const cls = bad.has(i) ? ' clash' : '';
      html += fmt('<div class="tile%cls%" data-i="%i%">%name%<small>%teacher% · group %group%</small></div>', { cls: cls, i: i, name: CLASSES[i].name, teacher: CLASSES[i].teacher, group: CLASSES[i].group });
    }
    html += '</div>';
  }
  board.innerHTML = html;
  board.querySelectorAll('.tile').forEach(t =>
    t.addEventListener('click', () => { const i = +t.dataset.i; slot[i] = (slot[i] + 1) % SLOTS.length; render(); }));
  const st = document.getElementById('status');
  if (bad.size === 0) { st.className = 'status ok'; st.textContent = '✓ No clashes — a valid timetable!'; }
  else { st.className = 'status bad'; st.textContent = fmt('%size% classes in conflict.', { size: bad.size }); }
}

// Auto-resolve by backtracking: greedy alone can paint itself into a corner (this conflict graph is a triangular prism — 3-colorable, but a naive left-to-right pass can fail). Backtracking always finds a valid assignment when one exists, undoing choices that lead to a dead end.
function neighbors(i) {
  const ns = [];
  for (const [a, b] of EDGES) { if (a === i) ns.push(b); if (b === i) ns.push(a); }
  return ns;
}
function solve(i, assign) {
  if (i === N) return true;
  for (let s = 0; s < SLOTS.length; s++) {
    if (neighbors(i).every(nb => assign[nb] !== s)) {
      assign[i] = s;
      if (solve(i + 1, assign)) return true;
      assign[i] = -1;
    }
  }
  return false;
}
function autoResolve() {
  const assign = new Array(N).fill(-1);
  if (solve(0, assign)) slot = assign;
  render();
}

document.getElementById('auto').addEventListener('click', autoResolve);
document.getElementById('reset').addEventListener('click', () => { slot = new Array(N).fill(0); render(); });
document.getElementById('legend').textContent = 'Each class lists its teacher and group. Two classes clash if they share either — exactly like edges in graph coloring, where slots are the colors.';
render();
Result
Console

Then hit Auto-resolve to watch a simple heuristic sweep through, recoloring conflicts one by one. It usually untangles this small instance — but notice how a single move can ripple. Scale this to a whole university and the ripples become a wall.

The Hard Part

Here's why timetables resist:

  • Checking a timetable is easy: scan for any two classes sharing a teacher, room or group in the same slot.
  • Brute force is hopeless: with s slots and c classes there are sᶜ assignments — exponential.
  • It's NP-hard. Timetabling generalizes graph-coloring (slots = colors, clashes = edges), which is already NP-complete. Add rooms, capacities and teacher preferences and it only gets harder.
  • It mixes hard and soft constraints. Hard: no clashes. Soft: minimize gaps, balance the week, respect preferences. So it's both a feasibility and an optimization problem.
  • Practice leans on solvers and heuristics. Integer programming (ILP) and constraint programming solve mid-size instances exactly; large ones use evolutionary algorithms, simulated annealing and local search like the demo's recoloring.

It sits beside scheduling (sequencing jobs in time) and graph coloring (avoiding conflicts) — three faces of the same combinatorial difficulty.

Where It Matters

Timetabling quietly runs a surprising amount of daily life:

  • Schools and universities: class schedules and exam timetables that avoid student and room clashes.
  • Transport: train, bus and airline timetables sharing tracks, gates and crews.
  • Healthcare: nurse and doctor rosters covering every shift without overworking anyone.
  • Sports leagues: fixture lists where no team plays twice at once and travel is fair.
  • Workforce planning: call centers and factories matching staff to demand across slots.

Because the problem is NP-hard, commercial timetabling software is a whole industry — pouring constraint solvers and heuristics into schedules we mostly take for granted.

Conclusion

The timetable is the perfect example of a problem that feels like busywork and turns out to be deep. Each constraint is simple, but together they interlock so tightly that fixing one breaks another — the hallmark of NP-hardness, dressed up as a school schedule.

That's why no one builds big timetables by hand anymore: the same constraint solvers and heuristics that tackle graph coloring and scheduling do the untangling. Next time a clash-free schedule lands in your inbox, remember there's a small combinatorial battle behind it — quietly won by an algorithm.

Share this article

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

Comments

Loading comments...

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