SE547: Homework 7

Deadline: 5.30pm, Thursday 26 February 2004.

Homework

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.