Assignment round two

Objective

The goal is to solve two decision problems by encoding them as boolean constraint satisfaction problems which are then solved using the boolean circuits solver bczchaff taking as input boolean circuit satisfiability problems given in the described here.

For the first problem pick the decision version of one of the problems, Circuit Board Partitioning, Frequency Allocation or Spin Glass, which you did not use in the round one. Create a program that takes a problem instance (a graph file) and an integer bound K as input and prints a solution to the decision version of the problem as output in the format described in the problem page.

For the second problem consider the Round Robin Tournament problem. Create a program that takes a positive integer n as input and prints a schedule for an n team tournament as output in the format described in the problem page.

The recommended language for the programs is Java, as you can use the provided Graph-classes to load problem instances and the examples of doing encodings given here. However, you may use any program language available on the computers at the Computing Centre at TKK.

Deliverable

Return the commented source code and a small report describing your approach and results to airusane(at)tcs.hut.fi. For the first problem, consider both the problem of finding a solution and showing that it is an optimal solution. For the second problem, consider tournaments with an increasing number of teams n=6,8,10,... Measure the execution time.

Grading

For correct solution returned on first try: 2p
on second try: 1p
on third/subsequent tries: 0p