Skip to content
Tutorials Center
My learning

Topics

Lesson 62 of 68 ยท Projects

Project: Exam Scheduler with Graph Coloring

Turn exam conflicts into a graph, color it with greedy and backtracking algorithms to find the fewest time slots, and print a clean timetable.

A small college has nine exams and a student can only sit one at a time. Two exams that share a student cannot happen in the same time slot. Using as few slots as possible keeps the exam week short. This sounds like a scheduling puzzle, but it is a graph problem in disguise: draw one vertex per exam, join two vertices when the exams share a student, and a valid timetable is exactly a proper coloring of that graph, where colors are time slots and adjacent vertices must get different colors.

In this project you will build the conflict graph from enrollment data, color it greedily, improve the result with a smarter vertex order, find the true minimum with backtracking, and print a timetable that checks itself. The theory is in Graph Coloring and Planarity; here you put it to work.

From timetable to graph

Exam One vertex per exam.
Shared student An edge between two exams.
Time slot A color for each vertex.
Valid timetable No edge joins equal colors.
1 / 2

Step 1: build the conflict graph

The input is a table of students and the exams they take. We invert it: for each exam, the set of students; then two exams conflict when their sets intersect. Working with sets makes the test one line, and a sorted pair of names makes each conflict appear once.

We use fixed data so every run is identical. Twelve students each take two or three of nine courses.

Python Enrollment data to conflict graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are 9 exams and 23 conflicts out of a possible 36 pairs. Math is the busiest with 7 conflicts, Bio and Music have 6, and Chem, English and History have only 4. The number of conflicts per exam is the vertex's degree, and it is the key to a good ordering later. An exam with many conflicts is hard to place, so a smart scheduler handles it early.

Step 2: check a coloring

Before building solvers, build the judge. A function is_proper(graph, coloring) returns the list of violated edges, which is empty exactly when the timetable is valid. Every solver in this project will be judged by it, and we will also use it to confirm that a deliberately bad timetable is caught.

Writing the checker first has two benefits: it documents the rule precisely, and the solvers can never silently produce nonsense.

Python A coloring judge

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Putting every exam in one slot breaks every conflict, and giving each exam its own slot breaks none but needs nine slots. The aim is somewhere in between. The third check shows a classic bug: when an exam has no color at all, coloring.get returns None, and two missing exams look equal. A stricter judge would also demand that every exam has a slot.

Step 3: greedy coloring

Greedy coloring visits the vertices in some order and gives each one the smallest color not used by an already-colored neighbor. It is fast, simple and never fails, but the number of colors it uses depends on the order. It never needs more than ฮ” + 1 colors, where ฮ” is the largest degree, because a vertex has at most ฮ” neighbors and so at most ฮ” colors are blocked.

Two orders to compare are alphabetical (arbitrary) and largest degree first, the Welsh-Powell strategy. The second tends to give better results because high-degree vertices have the most constraints, so we color them while many colors are still free.

Python Greedy coloring with two orders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both orders produce a valid timetable (the assertion confirms it). The maximum degree is 7, so greedy could need up to 8 slots, but in practice alphabetical order uses 5 and largest-degree-first uses 4. The important lesson is that greedy gives an upper bound on the chromatic number but cannot promise the optimum.

Greedy coloring can be forced to use arbitrarily many colors on certain graphs with a bad vertex order, even though those graphs are bipartite and need only two. Order matters enormously in the worst case, which is why we look for a way to get the exact minimum.

Step 4: backtracking for the exact minimum

To find the true minimum, try k = 1, 2, 3, ... colors and ask whether a proper coloring with k colors exists. The first k that works is the chromatic number. Testing one k is a search problem: assign colors one vertex at a time; if no color is possible for the current vertex, backtrack and change an earlier choice.

Two cheap ideas make the search practical:

  • Order by degree, as before, so conflicts show up early and wrong branches are cut quickly.
  • Symmetry breaking: the colors are interchangeable names, so never use color c + 1 before color c has been used. Without this rule the search would explore every renaming of the same solution.

The code starts at k = 1 and prints each attempt. (A cleverer solver would start at the size of the largest clique, a set of mutually conflicting exams, because t exams that all clash need t different colors.)

Python Backtracking finds the minimum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The greedy bound is 4, and the trace shows that k = 1, 2 and 3 are all impossible (2, 3 and 5 recursive calls), while k = 4 succeeds after 10 calls. So 4 slots is the true minimum, matching greedy this time. The search stops at the first k that works, so earlier values are proven impossible: that is how a program proves a lower bound without any clever theory. Each "impossible" line means the whole search tree was exhausted. The final coloring is validated by the judge from step 2, so even a bug in the search could not hand back an invalid timetable.

Graph coloring is NP-hard. Backtracking is fine for a few dozen exams, but a university with thousands of courses needs heuristics, such as the greedy order above, or specialized solvers. Keep greedy as your fast baseline.

Step 5: print the timetable

The last step turns colors into a timetable. Each color becomes a time slot with a label. Slots are listed in order, exams in each slot are listed alphabetically, and we add a check line that counts the students: for every student we list their exam slots and verify that they are all different.

This last check is independent of the graph code. It goes back to the raw enrollment data, so it catches a bug in the conflict-building step too, which the graph-based judge could not. Verifying with the original data is a good habit whenever a pipeline transforms its input.

Python The final timetable and an independent check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output shows 4 slots: Art and Math on Monday morning, Bio, English and History on Monday afternoon, Music and Physics on Tuesday morning, Chem and Econ on Tuesday afternoon, followed by "students with a clash: 0". Because the check recomputes everything from the enrollment table, a zero here means every one of the twelve students can sit all their exams.

Ideas to extend the project

  • Limit the room capacity: no slot may hold more than five exams. Add the limit to the backtracking and see how the minimum changes.
  • Add student constraints such as "no student has three exams on the same day" by adding extra conflict edges.
  • Minimize the maximum exams per day rather than the number of slots, as a second objective, with a simple local search that swaps exams between slots.
  • Generate random enrollment data with a fixed seed and compare how often greedy hits the optimum.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the exam conflict graph, what do the colors represent?

    Each color is a time slot. A proper coloring gives different slots to exams that share a student.
  2. 2. Why does greedy coloring never need more than max degree + 1 colors?

    When coloring a vertex, at most ฮ” colors are blocked by its neighbors, so one of the colors 0 to ฮ” is always free.
  3. 3. What is the purpose of the symmetry-breaking rule in the backtracking search?

    Colors are interchangeable labels. Allowing a new color only after the previous ones were used cuts out all renamed copies of the same solution.
  4. 4. Why is the final timetable also checked against the raw enrollment data?

    If the conflict graph were built wrongly, a coloring could pass the graph check yet still put a student in two exams at once. The raw data is the ground truth.
  5. 5. How does the search prove that k = 2 slots are not enough?

    When place() returns False for k = 2 after trying every allowed branch, no proper 2-coloring exists, so the chromatic number is larger.

Summary

  • Exams are vertices, shared students are edges, time slots are colors, and a valid timetable is a proper coloring.
  • Write the validity checker first; check results against the raw data as well as against the graph.
  • Greedy coloring is fast and never needs more than max degree + 1 colors, but the vertex order changes the result; largest-degree-first is a strong default.
  • Backtracking with degree ordering and symmetry breaking finds the exact chromatic number for small instances, and failing for k โˆ’ 1 colors proves the lower bound.
  • Coloring is NP-hard in general, so real schedulers combine heuristics with exact methods for small parts.

Next: Common Mistakes and Pitfalls.