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.
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
(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
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.
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
A + B = AC. This has a solution. Another example is
+ IT = NOW. This is also solvable. Note that you have to replace
with another letter, e.g.,
T is not a legal
Lisp variable. Make up at least one more example with at least one solution.
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.
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
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
test-search.lisp that shows how to generate comparative
output. Use that and/or improve it.
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:
name-task1.doc, where name is your last name.
Send the Zip file as an attachment in an email to
with the Subject line:
CS 348 Task 1 Version 2.