School Timetabling with CP-SAT

from ortools.sat.python import cp_model

model = cp_model.CpModel()

teachers  = ["Ms. Arun", "Mr. Blake", "Dr. Chen"]
subjects  = ["Math", "English", "Science"]
classes   = ["Year 7", "Year 8", "Year 9"]
slots     = list(range(10))          # 10 time slots
rooms     = ["Room A", "Room B", "Lab 1"]

# One BoolVar per (teacher, subject, class, slot, room) combination
x = {}
for t in teachers:
    for s in subjects:
        for c in classes:
            for p in slots:
                for r in rooms:
                    x[t, s, c, p, r] = model.new_bool_var(
                        f"x_{t}_{s}_{c}_{p}_{r}"
                    )

solver = cp_model.CpSolver()

# Optional: set a time limit (seconds) so the solver doesn't run forever
solver.parameters.max_time_in_seconds = 30.0

status = solver.solve(model)

if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f"Solution status: {solver.status_name(status)}")
    print(f"Objective (penalty): {solver.objective_value:.0f}")

    # Decode: find every BoolVar the solver set to 1
    for t in teachers:
        for s in subjects:
            for c in classes:
                for p in slots:
                    for r in rooms:
                        if solver.value(x[t, s, c, p, r]) == 1:
                            print(f"  Slot {p:2d} | {r:8s} | {t:12s} | {s:10s} → {c}")

elif status == cp_model.INFEASIBLE:
    print("No solution exists — check for conflicting hard constraints.")
else:
    print(f"Solver stopped: {solver.status_name(status)}")

from ortools.sat.python import cp_model

# ── Data ─────────────────────────────────────────────────────────────────────

teachers = ["Ms. Arun", "Mr. Blake", "Dr. Chen"]
subjects  = ["Math", "English", "Science"]
classes   = ["Year 7", "Year 8", "Year 9"]
slots     = list(range(6))   # 6 time slots per week
rooms     = ["Room A", "Room B", "Lab 1"]
MORNING_SLOTS = {0, 1, 2}    # Slots 0–2 are morning

# ── Model ─────────────────────────────────────────────────────────────────────

model = cp_model.CpModel()

# Decision variable: x[t, s, c, p, r] = 1 iff teacher t teaches subject s
# to class c in slot p in room r.
x = {}
for t in teachers:
    for s in subjects:
        for c in classes:
            for p in slots:
                for r in rooms:
                    x[t, s, c, p, r] = model.new_bool_var(f"x_{t}_{s}_{c}_{p}_{r}")

# ── Hard constraints ──────────────────────────────────────────────────────────

# H1: Each (class, subject) pair is taught exactly once per week
for c in classes:
    for s in subjects:
        model.add_exactly_one(
            x[t, s, c, p, r]
            for t in teachers for p in slots for r in rooms
        )

# H2: No teacher teaches in two places at the same time
for t in teachers:
    for p in slots:
        model.add_at_most_one(
            x[t, s, c, p, r]
            for s in subjects for c in classes for r in rooms
        )

# H3: No class is in two rooms at the same time
for c in classes:
    for p in slots:
        model.add_at_most_one(
            x[t, s, c, p, r]
            for t in teachers for s in subjects for r in rooms
        )

# H4: No room is double-booked
for r in rooms:
    for p in slots:
        model.add_at_most_one(
            x[t, s, c, p, r]
            for t in teachers for s in subjects for c in classes
        )

# H5: Each teacher can only teach subjects they are qualified for
teacher_subjects = {
    "Ms. Arun":  {"Math", "Science"},
    "Mr. Blake": {"English", "Math"},
    "Dr. Chen":  {"Science", "English"},
}
for t in teachers:
    for s in subjects:
        if s not in teacher_subjects[t]:
            for c in classes:
                for p in slots:
                    for r in rooms:
                        model.add(x[t, s, c, p, r] == 0)

# ── Soft constraints (penalties) ──────────────────────────────────────────────

penalties = []

# S1: Ms. Arun prefers morning slots (penalty 2 per evening lesson)
for s in subjects:
    for c in classes:
        for p in slots:
            if p not in MORNING_SLOTS:
                for r in rooms:
                    penalties.append(x["Ms. Arun", s, c, p, r] * 2)

# S2: Avoid back-to-back lessons for any teacher (penalty 3)
for t in teachers:
    for p in range(len(slots) - 1):
        teaching_p  = [x[t, s, c, p,   r] for s in subjects for c in classes for r in rooms]
        teaching_p1 = [x[t, s, c, p+1, r] for s in subjects for c in classes for r in rooms]
        b2b = model.new_bool_var(f"b2b_{t}_{p}")
        model.add(sum(teaching_p)  >= b2b)
        model.add(sum(teaching_p1) >= b2b)
        penalties.append(b2b * 3)

model.minimize(sum(penalties))

# ── Solve ─────────────────────────────────────────────────────────────────────

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 30.0
status = solver.solve(model)

# ── Print solution ────────────────────────────────────────────────────────────

if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print(f"Status : {solver.status_name(status)}")
    print(f"Penalty: {solver.objective_value:.0f} points\n")

    header = f"{'Slot':>5}  {'Room':10}  {'Teacher':14}  {'Subject':10}  Class"
    print(header)
    print("-" * len(header))

    for p in slots:
        for r in rooms:
            for t in teachers:
                for s in subjects:
                    for c in classes:
                        if solver.value(x[t, s, c, p, r]) == 1:
                            print(f"  {p:3d}  {r:10}  {t:14}  {s:10}  {c}")

elif status == cp_model.INFEASIBLE:
    print("INFEASIBLE — no valid timetable exists with these constraints.")
    print("Hint: check that enough slots exist for all (class, subject) pairs,")
    print("and that teacher availability is not over-constrained.")
else:
    print(f"Solver stopped ({solver.status_name(status)}) — try increasing max_time_in_seconds.")