Constraints and logic
Constraint satisfaction with backtracking, MRV, forward checking and AC-3, then propositional logic, model checking, SAT solving, chaining and unification.
About 6 hours of study
Learning objectives
- Model and solve constraint satisfaction problems
- Decide entailment and satisfiability
- Apply forward chaining, backward chaining and unification
Lessons
- 1
Constraint satisfaction problems Intermediate
Describe problems as variables, domains and constraints, then solve them with backtracking search. Make the search much faster with the minimum-remaining-values heuristic and forward checking, on map colouring and Sudoku.
- 2
Constraint propagation and AC-3 Advanced
Shrink domains before and during search by removing values that cannot be part of any solution. Learn arc consistency, run the AC-3 algorithm, and see what propagation can and cannot decide on its own.
- 3
Propositional logic Intermediate
Represent facts as logical sentences, give them meaning with truth tables, and decide whether a conclusion follows from a knowledge base by checking every model. Learn validity, satisfiability and the classic equivalences.
- 4
Inference: chaining, resolution and unification Advanced
Derive new facts from rules without listing every model. Use forward chaining and backward chaining with if-then rules, prove things by resolution, and match patterns with variables using unification, the step towards first-order logic.
Module practice
- AI: Check a map colouringEasy
- AI: Colour a map by backtrackingMedium
- AI: A Sudoku solverHard
- AI: Revise one arcEasy
- AI: The AC-3 algorithmMedium
- AI: Solve a Futoshiki puzzleHard
- AI: Print a truth tableEasy
- AI: Decide entailment by model checkingMedium
- AI: A SAT solverHard
- AI: Forward chainingEasy
- AI: Backward chaining with a proofMedium
- AI: UnificationHard