Task 1 - Version 2

This is the amended version of Task 1. You can do either Task 1 or this version. This version is based on CSP-N Solver in csp-n.lisp that more easily supports n-ary constraints. Read the instructions in Task 1, then the modifications below.

Set Up

See the CSP Setup Instructions for details on installing and testing the CSP Solver, but instead of csp.lisp, compile and load csp-n.lisp. The other search code is unchanged.

The key difference in CSP-N is that instead of one constraint function, you create one or more constraint objects. Each constraint object can test one or more variables. The comments at the start of csp-n.lisp explain how constraints work in this code and how to create them. The main function is create-csp-constraint.

(create-csp-constraint :vars var-list :function function)

will make a constraint that will apply function to the values of the variables listed in vaxr-list. This constraint will be evaluated only when all the variables have been assigned values. Thus, the constraint that A = B + C can be specified with

(create-csp-constraint :vars '(a b c)
      :function #'(lambda (a b c) (= a (+ b c))))

A convenience function for this is make-csp-constraint. (make-csp-constraint vars form) will make form a constraint function on the variables listed. The above would be

(make-csp-constraint '(a b c) '(= a (+ b c)))

This creates the function #'(lambda (a b c) (= a (+ b c)), so the variables have to be legal Lisp variables, i.e., symbols and not constants like T or NIL.

nqueens-csp-n.lisp and map-csp-n.lisp show how to do N queens and map coloring using CSP-N.

Toy Problem

Do cryptarithmetic problems with the CSP-N Solver, including SEND + MORE = MONEY but not just that problem. A very simple example to use for testing is A + B = AC. This has a solution. Another example is DO + IT = NOW. This is also solvable. Note that you have to replace T with another letter, e.g., X, because T is not a legal Lisp variable. Make up at least one more example with at least one solution.

A Real Problem

Puzzles are fine for testing and exploring, but in real life we need programs to solve real problems, like assigning resources to tasks, choosing parts for computers, and so on. Find a real world task that seems appropriate for CSP, represent one or two examples, and apply the CSP Solver to it.

Improving the Solver

The CSP-N Solver is very simple code. It's intended to have lots of room for improvement. At the start of the file, the comments describe a number of ways in which it can be made more efficient. Implement one or more of these improvements. If you notice another possibility, do that, but check with me first! Some changes are either of little value or even wrong.

Do not change csp-n.lisp. Create a file with the code you need to extend and redefine csp-n.lisp. This will be the file you send in.

Experiments

Gather data on how the CSP-N Problem Solver runs for the different problems, with different combinations of the flags and search functions. Draw some conclusions.

Note that the Solver code already gathers some statistics, and there's example code in test-search.lisp that shows how to generate comparative output. Use that and/or improve it.

The Report

Put your report in a Word document (or RTF file if you use something other than Word). Separate the document into clearly labeled sections based on the above, i.e., a section on how you changed the CSP-N Solver, a section on how you implemented the cryptarithmetic problem, a section on the experiments and results, and so on.

Create the following files:

Send the Zip file as an attachment in an email to c-riesbeck@northwestern.edu, with the Subject line: CS 348 Task 1 Version 2.

Comments? comment image Send mail to Chris Riesbeck.