welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

location: BottleFillingProblem

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