Programming Assignment 2 - Constraint Satisfaction

Intelligent Systems, Spring 2015

Due Date
Introduction
The Assignment

Due Date

This assignment is due by Thursday, 26 February, at 11:50 p.m. and cannot be submitted after Saturday, 28 February, at 11:50 p.m.. See the turn-in page (last modified on 2015 February 7) for information about turning in your assignment.

Introduction

The circle placement problem involves placing circles of various radii in a rectangle R such that 1) each circle lays entirely within R and 2) no two circles overlap. The example on the left shows a correct solution to a circle placement problem; the example on the right shows an incorrect solution because a circle is placed so that a portion of the circle is outside the rectangle (X₁), and because a circle is placed to overlap another circle (X₂).

The Assignment

Write a Java class that uses constraint satisfaction to solve an instance of the circle placement problem, or indicates that the problem instance has no solution. The solution should involve formulating constraints for the problem instance, then satisfying the constraints using a constraint satisfaction technique of your choosing.

Input

Input comes from the parameters of the solve() method defined in the CirclePlacement interface. Your Java solver class should implement the CirclePlacement interface. For more details, see the CirclePlacement interface CirclePlacement.java in the /export/home/class/mucs520/pa2 assignment directory.

Output

As the result of the solve() call your solver returns either a solution to the given instance of circle placement problem or an indication that the problem instance has no solution. For more details, see the CirclePlacement interface CirclePlacement.java in the /export/home/class/mucs520/pa2 assignment directory.

Running the Solver

Once you've written your solver class, and other classes you may need, you can run your solver by typing

$ java -cp /export/home/class/mucs520/pa2/pa2.jar:. main

in the directory containing your class files. The jar file can be found in the assignment directory /export/home/class/mucs520/pa2, or you may have a copy stashed elsewhere. If you do make a copy, make sure you keep it up-to-date with the copy in the assignment directory.

This page last modified on 2015 February 19.