Bottle Filling Problem
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.
Input: xsucc/2, ysucc/2, xvalue/2, yvalue/2, bottle/3
See Problem Description.
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:
Additional sample instances: download Note: new example instances as of 2013-02-18 (the previous ones were buggy)
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: Wolfgang Faber
- Affiliation: University of Calabria, Italy