AI Spring 2009
Constraint Programming

1. Interim grade adjustments (approx)- A: 80, B+: 66, B: 50, C/C+: 30, D/D+: 20

   

   

2. AI Constraint Solvers web site

3. Data files
   • australia.csv
   • australia3Territories.csv
   • australia4Territories.csv

4. Lab 1, Brute force method of map coloring
   • Lab1Step1 Read the data file and convert to Python dictionary structure - the territories are keys, the associated values is a list of neighbors
   • Lab1Step2 Write "check" method, returns True/False whether a given solution (a color choice for each territory) is valid or not.
   • Lab1Step3 Write a recursive method that solves this map coloring problem. Find the possible solutions using three colors red, green, and blue. Choose a particular color for each territory, and use the constraint that no territory can have the same color as any of its neighbors.
   • What to hand in, example outputs, test cases, commented code.

5. Lab 2, Constraint programming - Degree heuristic, minimum remaining values, forward checking
   • Constraint programming slides from UC Irvine, Prof Smyth
   • Lab2Step1 - Sorting by number of neighbors
   • Lab2Step2 - Constraining by the degree heuristic
   • Lab2Step3 - Constraining by the degree heuristic and minimum remaining values
   • Try your solution on the data for US states
     -try your brute force method, can it work in a reasonable amount of time
     -try your Step2 and Step3 solutions for Lab2, do these work in reasonable time
     -make a colored graph of the US with your solutions, see Mr. Torbert
   • Another example run of steps 2 and 3 for AUSTRALIA, with explanations

6. Handouts for Lab 2
   • Example run of steps 2 and 3
   • Another example run of steps 2 and 3 for AUSTRALIA
   • Example run of steps 2 and 3 for US
   • TO HAND IN:
     • Step 1 to hand in
     • Steps 2 and 3 to hand in

7. Lab 3 - color the map of the US with several different versions of color lists.
   • drawOneShape.py starter program, colors one polygon, "PENTAGON1", using pentagonSample.csv

     

   • unitedstates.csv simpler US map ...Extension - try the more detailed map stateVisibilityBorders.csv
   • These data files are from our AI site

8. Sudoku Puzzle solver
   • Use the numbers 1-9 as "colors". Each square in one of the 3 by 3 sections are neighbors. Also each square is a neighbor of all squares in the same row and same column as the particular square.

   • SudokuLab

     

     sample easy puzzle from www.websudoku.com

     Partially solved version that is easier for initial backtracking:

     

   • Sample csv files of the above puzzle:
     • sudoku2.csv
     • sudoku2B.csv - partially solved version (easier initially for backtracking)
     • sample solution for sudoku2B.csv
9. Lab 4 - Solve the 8 Queens chess problem using your constraint programming algorithms from Labs 1-3
   • Lab 4 Version 2 - Solve the 8 Queens chess problem, a faster algorithm/version using your constraint programming

   

10. Lab 5 - Solve Crypto-arithmetic problems.
    • S E N D + M O R E = M O N E Y see slide 13 for constraints...
      • All the letters must be different
      • Each letter is one of 0..9
      • 1000*S + 100*E + 10*N + D etc
    • Also, this Prolog version with sample problems. Solve these in Python/Ruby. Try to magic square

      	A B C
      	D E F
      	G H I
      	

      • Constraints: A+B+C = D+E+F = G + H + I = A+D+G = B + E + H = C + F + I
        = A + E + I = C + E + G
      • Constraints: A < C, A < G, A < I, G < C

    • A N D + T O + A L L + A + G O O D = N I G H T