Meeting Point

(Main file name: meeting)

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

Sample

LP Input | Minizinc Input | Output |

boardl(3). number(1,1,1). number(2,1,1). number(3,3,0). | n = 3; s = 3; row = [1,1,3]; col = [1,2,3]; turn = [1,1,0]; | link(1,1,1,2). link(1,2,2,2). link(2,2,3,2). link(2,1,3,1). link(3,1,3,2). link(3,3,3,2). |