Research and design CSP search algorithm

User Story

As a developer of the CSP implementation I would like to know the strategies and algorithms that I should be using to find a scheduling solution before I begin implementation.

Description

After formulating the constraint satisfaction variables, domains, and constraints, a search needs to be performed to find a solution. It is critical that this search is performed with optimal runtime complexity in mind, as this step has the potential to run for extremely long periods of time.

The textbook "Artificial Intelligence - A Modern Approach by Stuart Russell" has a section (chapter 6) which details CSP, search algorithms, and optimizations.

Some possible algorithms and optimizations include the following:

Recursive Backtracking Search (traversing down the tree of assignments while checking constraints and backtracking when a constraint is violated)
Forward Checking (when a variable is assigned a value all remaining unassigned variable have their domains reduced as a result of any inconsistencies or conflicts with the last assigned variable)
Conflict Directed Backjumping (when a constraint is violated the algorithm calculates a set of variables known as a conflict set which cause the violation and then backtracking is performed until the set is unassigned)
Least Constraining Value assignment (assigning values to variables based on how little an assignment will constrain the remaining assignments)
Minimum Remaining Values MRV heuristic (choosing the next variable to assign based on how many values a variable has remaining, in other words choosing the variable to assign next which is most likely to cause a constraint violation sooner)

Related Issues

Blocks #11 Parent of #23, #24, #25

Acceptance Criteria

[x] A search algorithm is chosen
[x] A list of the optimizations and methods to be used is established (to be used in #11)
[x] The optimizations are prioritized in order of impact and ease of implementation
[x] Tickets are created for each optimization

Additional Resources

Add attachments, external links, etc here.

seng499-company2 / algorithm1