The more constraints one imposes, the more one frees oneself of the chains that shackle the spirit. — Igor Stravinsky, Poetics of Music, 1970

In this lab exercise, you’ll work with the AIMA Python implementations of Constraint Satisfaction Problems (CSPs). You start by applying specific algorithms to two specific problems and then reflect on the nature of CSPs and the algorithms used to solve them.

Sudoku

The implementation for Sudoku provided in this lab includes calls to the following four algorithms:

The code also provides the following predefined problem specifications:

4 8 3 | 9 2 1 | 6 5 7
9 6 7 | 3 4 5 | 8 2 1
2 5 1 | 8 7 6 | 4 9 3
------+-------+------
5 4 8 | 1 3 2 | 9 7 6
7 2 9 | 5 6 4 | 1 3 8
1 3 6 | 7 9 8 | 2 4 5
------+-------+------
3 7 2 | 6 8 9 | 5 1 4
8 1 4 | 2 5 3 | 7 6 9
6 9 5 | 4 1 7 | 3 8 2
 
. . 3 | . 2 . | 6 . .
9 . . | 3 . 5 | . . 1
. . 1 | 8 . 6 | 4 . .
------+-------+------
. . 8 | 1 . 2 | 9 . .
7 . . | . . . | . . 8
. . 6 | 7 . 8 | 2 . .
------+-------+------
. . 2 | 6 . 9 | 5 . .
8 . . | 2 . 3 | . . 9
. . 5 | . 1 . | 3 . .
 
4 1 7 | 3 6 9 | 8 . 5
. 3 . | . . . | . . .
. . . | 7 . . | . . .
------+-------+------
. 2 . | . . . | . 6 .
. . . | . 8 . | 4 . .
. . . | . 1 . | . . .
------+-------+------
. . . | 6 . 3 | . 7 .
5 . . | 2 . . | . . .
1 . 4 | . . . | . . .
 
1 . . | . . 7 | . 9 .
. 3 . | . 2 . | . . 8
. . 9 | 6 . . | 5 . .
------+-------+------
. . 5 | 3 . . | 9 . .
. 1 . | . 8 . | . . 2
6 . . | . . 4 | . . .
------+-------+------
3 . . | . . . | . 1 .
. 4 . | . . . | . . 7
. . 7 | . . . | 3 . .
solved - This is a solved puzzle taken from the AIMA text (see Figure 6.4.b). easy - This is an unsolved but relatively easy puzzle, also taken from the AIMA text (see Figure 6.4.a). harder - This is a harder puzzle taken from csp.py. hardest - This the hardest 9x9 puzzle according to this 2006 source. Anyone care to solve it manually?

Exercise 3.1

Pull sudoku.py and try running each of the algorithms on each of the predefined sudoku puzzles. Consider the following questions:

  1. Which algorithms work (in a timely manner) and which don’t? Explain your results in terms of the capabilities (and implementations) of the algorithms and nature of the problems.

  2. What effect does configuring the settings for backtracking have on the results? Try the following:

    1. Set the variable/value ordering (i.e., the select_unassigned_variable parameter) to first-unassigned-variable (the default) or minimum-remaining-values (i.e., mrv).
    2. Set the inference (i.e., the inference parameter) to forward-checking (i.e., forward_checking).

    Which, if any, of these settings should work best for sudoku? What combination of settings actually works the best?

Save the answers to these questions in lab.txt.

N-Queens

The implementation for n-queens provided in this lab includes calls to the same four algorithms given above and it allows you to specify n.

Exercise 3.2

Pull queens.py and try running each of the algorithms with various values for n. Answer the following questions:

  1. How large can n get for each of the algorithms? Why?
  2. What backtracking settings work the best? Why?
  3. How many steps does Min-Conflicts require to do its work? Why?

Save the answers to these questions in lab.txt.

Constraint Satisfaction Problems

Take some time now to reflect on the nature of constraint-based problems and algorithms. Constraint satisfaction works by taking advantage of constraints stated in terms of parts of the state representation. As you’ve seen, traditional strategies can be applied as well as local search.

Exercise 3.3

Review the AIMA Python implementation for constraint satisfaction problems (CSP) as needed to do the following:

  1. Compare and contrast the specifications for CSP (i.e., csp.CSP) and traditional problems (i.e., search.Problem). Be sure to consider the nature of states, domains, actions, results and goal tests.
  2. Compare and contrast the nature of the heuristics deployed in traditional and constraint-based problem solving.

Save the answers to these questions in lab.txt.

Checking in

We will grade your work according to the following criteria:

See the policies page for lab due-dates and times.