ComputerScienceExpert

(11)

$18/per page/

About ComputerScienceExpert

Levels Tought:
Elementary,Middle School,High School,College,University,PHD

Expertise:
Applied Sciences,Calculus See all
Applied Sciences,Calculus,Chemistry,Computer Science,Environmental science,Information Systems,Science Hide all
Teaching Since: Apr 2017
Last Sign in: 103 Weeks Ago, 3 Days Ago
Questions Answered: 4870
Tutorials Posted: 4863

Education

  • MBA IT, Mater in Science and Technology
    Devry
    Jul-1996 - Jul-2000

Experience

  • Professor
    Devry University
    Mar-2010 - Oct-2016

Category > Programming Posted 28 Apr 2017 My Price 11.00

Constraint Propagation and Backtracking

Objectives:

Constraint Programming: Constraint Propagation and Backtracking Search

Requirements and Submissions:

This is a programming assignment. Submit your source code via Connect. This assignment is worth 40% of the total assignment marks. Programs due on 23:55pm, Monday, March 9th.
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 currentLevel, int currentValue)and
  • ConstraintPropagator.arcConsistency(CSPInstance csp, int currentLevel)

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. Contains a fully-implemented backtracking search procedure.
  • ConstraintPropagator.java--- 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 about 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.
  1. 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.
  2. Enforcing Arc-consistency with AC-3 You should implement the method arcConsistency(CSPInstance csp, int currentLevel). 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 the 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.

Attachments:

Answers

ComputerScienceExpert
(11)
Status NEW Posted 28 Apr 2017 08:04 AM My Price 11.00

-----------

Not Rated(0)