tonirv/constraint-satisfaction-notebook

Example lecture for Constraint Satisfaction Problems in an interactive jupyter notebook. With python code to solve CSPs, with visualization of Sudoku and NQueens problems.

constraint-satisfaction-notebook's Issues

Bucket Elimination

@sharanraja Deadline on Friday morning.

Conflict-directed Back Jumping (CBJ) 3.2

@sharanraja could work on 3.2, think of an example, I think that we can do it with NQueens.

Complete Table Of Contents

@sharanraja

I have updated the table of contents in the notebook with details on what we should have (copied below for convenience).

How do you want to divide the work?

• I would suggest that one of us works on:

  • Constraint Propagation in CSPs (let's say you do that).
  • while the other works on Search in CSPs for now (I do this).

• Then, for part 2.3 Elimination for Constraints in CSPs:

  • you could go for Bucket Elimination,
  • and I will explain Variable Elimination.

• For part 3. Appendix:

  • I can do 3.1 Constraint Optimization Problem where I will do a map-coloring visual demo.
  • You could work on 3.2, think of an example, I think that we can do it with NQueens.
  • Concerning 3.3, I think I can do it myself by re-using explanations of Search in CSPs.

For all parts, think of interactive ways to demonstrate the concepts, not just saying this works like this and that... Nikhil emphasized this part quite a bit.

In terms of work development
Checkout the projects tab to see what is to be done and to log what has been done.
In general:

1. I add issues in the issues tab for something that has to be done.
2. then I add it as a card in the projects tab
3. once I am tackling an issue I put it in progress in the Projects tab (you can see that this issue is actually in the "in progress" column of the current project "CSP todo list" (see on the right panel under Projects)
4. Once I have an issue done, you can close the issue, and it will move automatically to Done in the Projects tab.

Feel free to use this workflow, it works great for collaboration.

CONTENTS

1. Introduction to Constraint Propagation Problems (L13 & L14):

   1. Definition
   2. Examples

2. Solving CSPs (L14 & L 15):

   1. Constraint Propagation in CSPs:

      1. Arc-Consistency:

         1. Directed arc consistency
         2. Full arc consistency

      2. Propagation:

         1. AC-1:
            • Definition
            • Example: solving Sudoku with AC-1
            • Complexity Analysis
            • Soundness and Completeness
         2. AC-3:
            • Definition
            • Example: solving Sudoku with AC-3
            • Complexity Analysis
            • Soundness and Completeness

      3. Numerical constraints:

         1. Propagation for Integer Domains
         2. Pruning Integer Domains

      4. Global constraints:

         1. AllDiff
         2. Example: global vs local constraints NQueens

   2. Search in CSPs:

      1. Generic Search:
         • Formulating CSPs as a state space search problem
         • Complexity
         • Example: NQueens with generic search (5 Queens)
      2. Backtracking Search (BT):
         • Definition
         • Complexity
         • Example: solving NQueens (15 Queens)
      3. Backtracking Search with Forward Checking (BT-FC):
         • Definition
         • Complexity
         • Example: solving NQueens (30 Queens)
      4. Backtracking while Maintaining Arc Consistency (BT-MAC):
         • Definition
         • Complexity
         • Example: solving NQueens (X Queens)
      5. BT-DC with Dynamic Variable Ordering:
         • Definition
         • Complexity
         • Example: solving NQueens (1000 Queens)

   3. Elimination for Constraints in CSPs:

      1. Variable Elimination for Constraints:
         • Definition: join and project
         • Example
      2. Bucket elimination (Adaptive Consistency):
         • Definition
         • Example

3. Appendix:

   1. Constraint Optimization Problem:
      1. Branch-and-Bound
   2. Conflict-directed Back Jumping (CBJ)
      • Definition
      • Example
   3. Incremental Repair / Iterative Repair / Min-Conflict Heuristic
      • Definition
      • Example

MAC explanation

Search in CSPs

@ToniRV

• Generic Search

• BT

• BT-FC

• BT-MAC

• Display steps taken when doing BT and BT-FC

Constraint Optimization Problem

@ToniRV Deadline Friday morning

Add links in Table of Contents to actual content

@sharanraja let's try to have links from the table of contents(TOC) to the actual content in the notebook.
You can see some examples in the current TOC, I would suggest we follow that for the rest.

Variable Elimination

@ToniRV Deadline Friday morning

Fix bug with button Visualize

Move images inside folder

@sharanraja Move Algorithm images to images folder.
So everything looks clean.

Sudoku Visualization

Step-by-step visualization AC1-3

Constraint Propagation in CSPs

@sharanraja Deadline Wednesday morning after the lecture.

Create lib folder

• Create lib folder.
• Add libraries of code used by the notebook inside the folder.