The project was developed as part of the Introduction to Artificial Intelligence (CSC384) at the University of Toronto, Department of Computer Science.
Role
Developer
Tools
Python
Focus Areas
Artificial Intelligence, Constraint Propagation & Inference, Constraint Satisfaction Modeling, Search Optimization, Algorithm Implementation
Timeline
March 2025
Overview
Built a constraint satisfaction engine to solve Futoshiki, a logic puzzle requiring row/column uniqueness and inequality constraints to be satisfied simultaneously.
What I Built
Constraint Propagation Algorithms
- Implemented Forward Checking (FC) to prune domains when constraints contain a single unassigned variable.
- Implemented Generalized Arc Consistency (GAC) to enforce consistency across all constraints and aggressively reduce the search space.
- Designed propagation routines that track and restore pruned values during backtracking.
- Integrated early dead-end detection via domain wipe-out checks.
Search Optimization
- Implemented the Minimum Remaining Values (MRV) heuristic to dynamically select the most constrained variable.
- Reduced branching factor and improved backtracking efficiency through intelligent variable ordering.
- Analyzed how propagation strength impacts search depth and runtime performance.
CSP Modeling
- Compared the space/time tradeoffs between binary and global constraint modeling.
- Encoded Futoshiki as a formal Constraint Satisfaction Problem with:
- Variables representing grid cells
- Domains {1 … n}
- Binary inequality constraints
- Row and column uniqueness constraints
- Built two distinct CSP models:
- Binary Model: Pairwise not-equal constraints for rows and columns
- n-ary Model: All-different constraints for rows and columns
Built two distinct CSP models:
- Binary Model: Pairwise not-equal constraints for rows and columns
- n-ary Model: All-different constraints for rows and columns
- compared the space/time tradeoffs between binary and global constraint modeling.
Skills Demonstrated
- Constraint Satisfaction Problems (CSPs)
- Arc Consistency (GAC)
- Forward Checking
- Variable Ordering Heuristics (MRV)
- Backtracking Search Optimization
- Domain Pruning & Inference
- Combinatorial Complexity Management
- Python Algorithm Implementation