Course Map Generator

Question

My university lists the rotation of courses each semester/year. Therefore, it is possible to predict when every class will be taught.

I am trying to create a JavaScript (language is irrelevant, really) program that will have the user select all the courses they would like to take, for how many semesters, and the max (or maybe exact) number of classes they'd like to take during each one of those semesters.

So, for instance, my university offers: 12 courses in Fall (varies between even and odd years) 10 courses in Spring (varies between even and odd years) 6 courses in Summer (varies between even and odd years) essentially, 6 different semester patterns

Basically, the user will choose their preferred 16 or so courses, enter 6 semesters, the semester they would like to start in, and the max number of courses per semester. From there, I would like to generate all the possible course maps the user could take in order to graduate in 6 semesters. I want them to be able to vary the number of courses in each semester--like 3 courses one semester, 2 courses in another, etc. I also want to check previous classes to make sure classes aren't duplicated, as well as ensure that the classes meet their respective pre-requisites.

My instincts say to go with recursion in order to do this, but I'm not exactly sure how I would go about it.

So far, I have only been able to come up with: generate all the sets per semester based on home many courses the user would like in that semester (if the user picks 3 courses for the first semester, then create all the sets of 3 out of the 12 courses). Do this for each semester. Then, loop through all these combinations to see which ones work. Seems very inefficient and slow to me.

As this is Programmers SE, I'm not really looking for any code, but maybe an algorithm or a more efficient approach to this problem. Any help would be greatly appreciated. I can post a link to my university's course rotation if that would help.

Answer 1

You could do this by hand, in which case you will indeed need to backtrack during a recursive search. However, this sort of problem is very complex and you have a high risk that your implementation will not be robust against a lot of changes, which invariably will happen.

A more general approach to these problems is available in the form of constraint programming (CP). With CP you can reduce your problem to providing correctly formatted input and writing down the constraints, i.e. restrictions, that valid paths must adhere to.

So when you think about your problem, you can easily come up with several constraints:

1. All mandatory courses must be included in the solution.
2. No course time schedule (time, room,..) must overlap with any other from the solution.
3. The number of required semesters for taking all the courses of the solution must not exceed 6 semesters.
4. and so on, and so on

In a CP solution you would write down exactly these constraints as part of your code and provide the available courses as input, whereas the underlying constraint solver (several libraries in various languages are available for these) will perform the grunt work for you in very efficient ways.

In order to model things like "prefer to have only 2 courses in first semester" in such a way, that 3 or 4 courses would be possible too, you will need to look up so-called soft constraints.