Deadline: 5.30pm, Thursday 26 February 2004.
1. The file IntPred.java contains a finished implementation of addition, but an unfinished implementation of subtraction. You should complete the implementation of subtraction, and test it by running:
java simplebdd.test.TestSubtraction number of bits
2. Extra credit:
A standard test example for BDDs and other SAT-solvers is the n-queens problem.
Consider an n-by-n chess board, the goal is to find a way to place
n queens on the chess board such that none of them can capture each other,
by moving horizontally, vertically or diagonally. Implement a solution using the
simplebdd package, using n2 boolean variables: the variable
is true whenever a queen is on the corresponding square. Define a predicate which is true
precisely when a solution the the n-queens problem is found; then run your program
to find and print a solution.
Submit your answers as Java source files using Courses On Line.