Bottle Filling Problem

Problem Description

Given a grid (xsucc/2 specifies the successor relation of the X coordinates, ysucc/2 for Y coordinates, the second arguments are successors of the first arguments), a number of bottles on the grid (bottle/3, first argument is a bottle identifier, the last two X and Y coordinates), determine how filled each bottle is - each grid element in a bottle may contain liquid or not. For each row, xvalue/2 provides the number of filled grid elements (first argument is the coordinate, the second the number), and yvalue/2 analogously for columns. Gravity acts along the Y coordinate in the direction of the successor relation (i.e. larger Y coordinate is further down), which means that bottles can only either be empty or must have a consistent fill level, from the largest Y coordinate to the smallest filled Y coordinate in the bottle all grid elements in the bottle with such Y coordinates must be filled (note that this means that filled cells are not necessarily linked; requiring this and thereby allowing for different fill levels in different areas of the same bottle might be a future elaboration of this problem). Encodings should not assume bottles to be convex (i.e. they can have "holes"), but bottles can be assumed to be non-overlapping.

Predicates

• Input: xsucc/2, ysucc/2, xvalue/2, yvalue/2, bottle/3

• Output: filled/2

Input format

See Problem Description.

Output format

Example(s)

Given the input:

xsucc(1,2). ysucc(1,2).

bottle(1,1,1). bottle(1,1,2).

xvalue(1,1). xvalue(2,1).

yvalue(1,2). yvalue(2,0).

The output of the solver should look like:

filled(1,2). filled(1,1). 

Additional sample instances: download

Problem Peculiarities

Type: Search Competition: Both

This problem is based on a puzzle found in the 2012-08-11 issue of the Austrian newspaper "Die Presse" (where bottles had a fixed horizontal extension of 1 and were said to be filled with wine).

Notes and Updates

Author(s)

• Author: Wolfgang Faber
  • Affiliation: University of Calabria, Italy