Monday, November 8, 2021

Solutions

 Been working through ther exam scheduling problem.  One needs to

upgrade pip and install the constraint module for all the code:



                                                            *     *     *

An example of aconstraint satisfaction problem. Courses A to G need to be

schedules so that no one has two exams at the same time...


Backtracking manually to find one solution:


Doing it with difficult to write code:


doing it with simple code that calls the constraint module:


Voilà, there is more than one solution.

                                                              *     *     *

A simple constraint satisfaction problem:



Our approach uses nodes and edges:



The nodes represent the exams.There are only edges between them if there

is a constraint, here, same student. Each is called an arc.

As a rule, one looks for node consistency first; that would be whether all courses have

exams, not a problem in this case.

Then one looks for arc consistency: can one remove domains from a variable - here, a 

possible exam day - and keep going. 





If not, one reports a failiure and backtracks to start again with another variable.


The algorithm as a whole is called AC-3, Arc Consistency -3.









No comments: