Constraint Satisfaction Problem
| Optimization | Python |
Constraint satisfaction problem is formulated with the following three sets
Where for i variables denoted by X with each respective domain in D, try to find one/the entire set of solutions that satisfy j constraints denoted by C.
One popular example of CSP is the n-queens problem, where for a chess board of n by n, one need to put n queens on the chessboard that no queen is in the immediate attack range of any other queen.
Graph searches are often a simple yet effective approach to the discrete set of constraint satisfaction problem. Here we explore four different levels of graph search algorithm for the n-queens problem:
- Depth First Search
- Back track Search
- Back track with forward checking
- Back track with forward checking and dynamic variable ordering
These algorithms differs by their level of reuse of existing search space and lookaheads. By putting more effort into the development of algorithm (from DFS to backtrack with dvo), memory usage and search time has been vastly decreased and enables operations for much larger problem.
