Description

Objectives:

Constraint Programming: Constraint Propagation and Backtracking Search

Requirements and Submissions:

This is a programming assignment. Submit your source code via Connect. T

There are two tasks in this assignment. The first task is to implement two functions to support the two constraint propagation methods, forward checking, and arc-consistency checking, for a CSP solver. The second task is to use your fully-implemented CSP solver to solve a variant of the eight queen problem. The source code of the partially implemented CSP solver is provided to you.

Task 1: Forward Checking and AC-3 Algorithm for Maintaining Arc Consistency

Download the source code of the partially-implemented CSP solver cosc322-csp-solver-src-2017.zip. The package consists of a collection of Java classes. Note that the solver is prepared specifically for this course, and its performance is not as good as industrial-strength solvers. You are required to complete two functions in the partially-completed Java classConstraintPropagator.java:

ConstraintPropagator.forwardChecking(CSPInstance csp, int current level, int currentValue)and

ConstraintPropagator.consistency(CSPInstance csp, int current level)

These two functions implement respectively the forward-checking algorithm and the arc-consistency algorithm (AC-3), and are used in the CSP solver implemented in the class CSPSolver.java. Please read the detailed comments in the following source files to see how the program works and what needs to be done:

CSPSolver.java---- the class for CSP solver. It contains a fully-implemented backtracking search procedure.

ConstraintPropagator.java--- It contains static methods that implement various propagation algorithms. Not fully-implemented. Your task is to complete the two methods that support forward checking and arc consistency.

CSPInstance.java--- the class for CSP instances

Constraint.java--- a not-equal constraint for the graph coloring problem and the Sudoku problem.

CSP322.java--- contains two testing code to illustrate how to use the solver. Also used for testing your implementation.

You do not need to touch the first and the last three Java classes at all, but reading them will give you a better understanding of how things work. The CSP solver provided to you, though not fully-completed, can be compiled and run using the command: java CSP322 or as an Eclipse project. You will see some outputs like: failed to verify the solution, which is of course expected.

Forward-Checking (30 points)If implemented correctly, the first testing case used in CSP322.java should be "unsatisfiable" with some backtrackings, while the second testing case should be solved by your solver without any backtracking. You do not have to wait until you have implemented the second method for arc consistency. Instead, once you are done with forward-checking, you shall have a fully-functioning, but of course less efficient, CSP solver.

Enforcing Arc-consistency with AC-3 You should implement the method consistency(CSPInstance csp, int current level). If implemented correctly, your solver shall be able to solve the first testing case without backtracking as well.

Task 2: Solving a Variant of the Eight Queen Problem Using the Implemented Solver

See the testing methods in the class 322CSP.java for examples on how to set up a CSP instance for the CSP solver. Please note that our solver can only handle binary constraints, and as a consequence, the CSP formulation discussed in lecture 6 has t be used: one variable for each column, and there is a constraint between each pair of columns, giving us a total of 28 constraints.

To make the problem more interesting, let's add an additional requirement for a solution: the sum of the row numbers of the two queens in any adjacent columns must be at least 7.