Adapted from the 2014 ASP Model & Solve competition.
Consider a grid puzzle as shown below on the left-hand side:
The
task is to construct non-crossing and non-overlapping paths that start
from given numbered grid cells, having coordinates (1,1), (2,1), and
(3,3) in this example, and meet each other in a single cell. The paths
can make horizontal and vertical transitions between neighboring cells
but must not pass numbered grid cells (except for their origins). Most
importantly, for each path, the number in its origin cell prescribes
the number of turns, that is, alternation between horizontal and
vertical transition or vice versa, the path has to make. A
corresponding solution is displayed on the right-hand side above.
Observe that the paths from cell (1,1) and (2,1) make one turn each at
cell (1,2) or (3,1), respectively, while the path from (3,3) makes no
turn on its way to the common meeting point (3,2).
Input Formats
An
instance file for LP systems contains one fact of the form board(N)
that represents the grid board size, and facts of the form
number(Row,Col,Turns) that represent the numbered cells.
An
instance file for Minizinc specifies the grid board size n, the
number of numbered cells s, and three arrays, named row, col, and turn,
that represent the numbered cells. Output Format The output gives satisfactory transitions of all paths as facts of the form link(X1,Y1,X2,Y2).
