The Impossible Timetable

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.

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">{{hint}}</p>
<div id="board" class="board"></div>
<p id="status" class="status"></p>
<div class="btns">
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

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.

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.