Class Tree
Description The weighted latin-square problem is a variant of the latin-square problem.
In the weighted latin-square problem, we are given an n x n weights
wt(i,j). We are also given a bound w.

A weighted latin-sequre is an n x n array a such that
a. each entry contains an integer from {1,2,...,n}
b. no row contains the same integer twice
c. no column contains the same integer twice
d. for every row i, 1<=i<=n,
a(i,1)*wt(i,1) + a(i,2)*wt(i,2) + a(i,n)*wt(i,n) <= w

The goal in the problem is to find a weighted latin square.

Input Format
============

Input data are stored in a plain text file,

a. The file starts with n lines

num(1).
num(2).
...
num(n).

which specify the number of rows and columns in the square and the
rannge of integers to use.

b. Then there are n^2 lines, each of the form

weight wt(i,j)=v.

c. Then there is a single line

bound(w).

Example:
num(1).
num(2).
num(3).
num(4).
weight wt(1,1)=1.
weight wt(1,2)=2.
weight wt(1,3)=1.
weight wt(1,4)=2.
weight wt(2,1)=1.
weight wt(2,2)=2.
weight wt(2,3)=1.
weight wt(2,4)=2.
weight wt(3,1)=1.
weight wt(3,2)=2.
weight wt(3,3)=1.
weight wt(3,4)=2.
weight wt(4,1)=1.
weight wt(4,2)=2.
weight wt(4,3)=1.
weight wt(4,4)=2.
bound(15).

Output Requirement
==================
A solution must be specified in terms of a 3-ary predicate "square",
with the meaning of "square(i,j,k)": "square (i,j) contains integer k".

For the input given above, the following is a valid weighted latin square:
square(4,4,4)
square(2,3,4)
square(1,2,4)
square(3,1,4)
square(2,4,3)
square(1,3,3)
square(3,2,3)
square(4,1,3)
square(3,4,2)
square(4,3,2)
square(2,2,2)
square(1,1,2)
square(1,4,1)
square(3,3,1)
square(4,2,1)
square(2,1,1)

Thus, the output produced by the solver, when displaying the
corresponding answer set must show these and only these atoms of
the type "square" (and possibly some other atoms based on other
predicates).

Authors: Gayathri Namasivayam and Miroslaw Truszczynski
Affiliation: University of Kentucky
Email: {gayathri, mirek}@cs.uky.edu
Encodings
1 - 5 of 5