RoutineGen: High-Speed Backtracking and Constraint Satisfaction for Course Scheduling

Author: Md. Rakibul Hasan (@rxxeron)
Academic Affiliation: B.Sc. in Information and Communications Engineering (ICE), Dept. of Computer Science and Engineering, East West University
Architecture Pattern: Microservice, Constraint Satisfaction (CSP), Forward Checking Backtracking

1. Problem Formulation: Timetable Clash Resolution

Advising day schedule generation is fundamentally an NP-Hard Constraint Satisfaction Problem (CSP):

• Variables: Enrolled courses $C = {C_1, C_2, C_3, C_4, C_5}$.
• Domain: Available sections for each course $D(C_i) = {S_{i,1}, S_{i,2}, ..., S_{i,k}}$.
• Hard Constraints: No two assigned sections may occupy overlapping time intervals on any day of the week.
• Soft Constraints: Preferences for specific faculty instructors, minimization of gap hours between classes, and avoiding 8:30 AM early morning slots.

text
+--------------------------------------------------------------------------------------------------+
|                                  ROUTINEGEN PIPELINE                                             |
+--------------------------------------------------------------------------------------------------+
|   [HTTP API Request (FastAPI)] -> [Section Bitmask Encoder] -> [Recursive DFS Backtracking]     |
|                                                                             │                    |
|                                                                             ▼                    |
|   [Ranked Permutation Matrix]  <- [Soft Constraint Scorer]  <- [Branch-and-Bound Pruning Engine] |
+--------------------------------------------------------------------------------------------------+

2. Algorithmic Search Space Pruning

The brute-force evaluation of all section permutations across 5 courses yields over 200,000 combinations. RoutineGen applies Forward Checking Backtracking:

• Sections are sorted by popularity and faculty preference.
• As soon as a branch assigns Section $A$ of Course 1 and Section $B$ of Course 2 that share an overlapping time slot, the entire recursive subtree branching from $(A, B)$ is pruned immediately ($O(1)$ clash detection via bitmask AND operations).
• Average search time across 200,000 theoretical combinations is reduced from over 12 seconds to under 210 milliseconds on a standard single-core serverless instance.