Schur Numbers

Problem description

The Schur number problem is to partition n (positive) integers into m sets such that all of the sets are sum-free. By sum-free, we mean that, if x and y (x = y is possible) are assigned to the same set, then x+y is not in the set. In our version of the Schur number problem, we permit an extra input that specifies the assignment of some numbers to sets. The task then is to check whether the given partial assignment can be extended to a full sum-free assignment.

Input format

An input consists of the following parts:

a. The n positive integers to partition are given by instances of "number". For example:

number(1). ... number(130).

b. The m sets to which numbers can be assigned are given by instances of "part". For example:

part(1). part(2). part(3). part(4). part(5).

c. Finally, a partial assignment can be specified by instances of "assigned" as follows:

assigned(1,1). assigned(2,1). assigned(3,1). ...

For further illustration, compare the instances available at asparagus.

Output format

A solution is represented by means of predicate "assigned". An instance of the form assigned(x,y) means that integer x belongs to set y. The solution must extend the partial assignment given in the input, and it must correspond to a sum-free partition for the numbers and parts of the input.

Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser
Affiliation: University of Kentucky and University of Potsdam