# 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 of the row [note that this is a Y coordinate, as rows are characterized by their Y 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 * Note: new example instances as of 2013-02-18* (the previous ones were buggy)

## 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